DIMACS Workshop on New Directions in Algorithms, Combinatorics and Optimization:
A Conference Honoring the 65th Birthday of William T. Trotter

May 5 - 9, 2008
Georgia Institute of Technology

Organizers:
Graham Brightwell, London School of Economics, G.R.Brightwell at lse.ac.uk
Dwight Duffus, Emory University, dwight at mathcs.emory.edu
Stefan Felsner,Technische Universität Berlin, lastname at domain-math.tu-berlin.de
Hal Kierstead, Arizona State University, kierstead at asu.edu
Prasad Tetali, Georgia Institute of Technology, lastname at math dot gatech dot edu
Robin Thomas, Georgia Institute of Technology, thomas at math.gatech.edu
Peter Winkler, Dartmouth College, firstname dot lastname at dartmouth dot edu
Xingxing Yu, Georgia Institute of Technology, yu at math.gatech.edu

Abstracts:


Imre Barany, Alfred Renyi Mathematical Institute
Title: Extremal Problems for Convex Lattice Polytopes

In this survey I will present several extremal problems, and some solutions, concerning lattice polytopes. A typical example is to determine the smallest area that a convex lattice polygon with at most n vertices can have.


Béla Bollobás, University of Cambridge and University of Memphis
Title: Random Graphs and Branching Processes

For the past decade or so, much work has been done on constructing and analyzing random graphs that resemble large-scale real-world graphs. Unlike the classical binomial or Erdos-Rényi random graphs, these graphs are Title: inhomogeneous in the sense that different small sets of vertices may play very different roles. A little while ago, Janson, Riordan and I constructed a very general model of inhomogeneous random graphs which contains most earlier models Title: precisely , and studied it with the aid of branching processes. Recently, Riordan and I have used the same method to reprove in a very simple way the precise results of Bollobás and Luczak about the phase transition in the binomial model. The main aim of this talk is to present this proof. his is joint work with Oliver Riordan from Oxford.


Graham Brightwell, London School of Economics

Title: Random Linear Extensions of Infinite Posets

In 1988, the speaker showed that, in an infinite poset P such that every element is incomparable with at most k others, there is a unique sensible notion of a random linear extension of P.

In a more general setting, there may be more (or fewer) than one suitable probability measure on the set of linear extensions of a poset. We will make these notions precise, give some examples, state a few results, and raise some questions.

The new work is joint with Malwina Luczak.


William Cook, Georgia Institute of Technology

Title: Numerically Accurate Solutions in Linear and Integer Programming

Numerous practical computational problems are formulated as instances of linear or mixed-integer programming. These models are typically described with rational data, while solution software uses floating-point arithmetic and inexact linear algebra to obtain approximate results. Although such solutions are satisfactory in applications, accuracy can be important in many practical and theoretical settings. An important example is the heavy use of linear programming in Hales' proof of the Kepler Conjecture concerning the packing of spheres in three dimensions.

In this talk we treat the problem of finding exact rational solutions to linear and mixed-integer programming models. We describe computational results for benchmark instances, Kepler models, coding-theory bounds, factoring integers, and the traveling salesman problem. This talk is based on joint work with David Applegate, Sanjeeb Dash, Daniel Espinoza, Ricardo Fukasawa, Marcos Goycoolea, and Dan Steffy.


Stefan Felsner, Technische Universität Berlin, Germany

Title: ULD-Lattices, Instances and Applications

We provide a characterization of upper locally distributive lattices (ULD-lattices) in terms of edge colorings of their Hasse diagrams. In many instances where a set of combinatorial objects carries the order structure of a lattice this characterization yields a slick proof of distributivity or UL-distributivity. This is exemplified by proving a distributive lattice structure on pseudo-flows with invariant circular flow-difference. This example generalizes several previously studied lattice structures, in particular, c-orientations (Propp), α-orientations of planar graphs (Felsner/de Mendez) and planar flows (Khuller, Naor and Klein). The characterization also applies to other instances, e.g. to chip-firing games. (joint with Kolja Knauer).


Fan Chung Graham, University of California, San Diego

Title: The PageRank of a Graph

PageRank is one of the main ways for determining the ranking of webpages by Web search engines. Based on relations in an interconnected network, PageRank has become a major tool for addressing fundamental problems arising in general graphs, especially for large information networks with hundreds of millions of nodes.

The study of PageRank involves a vigorous interplay between numerous areas including spectral graph theory, random walks, probability and approximation algorithms, to name a few. The applications of PageRank have grown far beyond its original scope of ranking webpages. In addition to finding hot spots and identifying hidden patterns in social and biological networks, PageRank also sheds light and provides mathematical insight to the vast world of information networks that surround us.


Jerrold Griggs, University of South Carolina, Columbia

Title: Large Families of Subsets Avoiding a given Configuration

Translating Turán-type questions to ordered sets, we are interested in the maximum size La(n,H) of a family {\cal F} of subsets of the set {1,2,...,n}, subject to the condition that a certain configuration (subposet H) is excluded. For instance, Sperner's Theorem solves the problem for H being a two-element chain.

We survey results of this kind, including bounds when H is the four-element N poset (joint with Gyula O.H. Katona) or a more general height two poset (joint with Linyuan Lincoln Lu).


Penny Haxell, University of Waterloo

Title: On Sperner's Lemma and Scarf's Lemma

We describe Scarf's Lemma and how it is related to Sperner's Lemma. We also discuss applications of these two results, to combinatorial problems and to a problem concerning internet routing protocols.


Jeffry Kahn, Rutgers University

Title: Correlation Questions

We may also mention a few results but mainly want to focus on some of the "annoying" problems in this area.


Hal Kierstead, Arizona State University

Title: On-line Partitioning

I will discuss on-line partitioning with special emphasis on joint results with Trotter and new directions.


Dan Kleitman, Massachusetts Institute of Technology

Title: Some Problems from the Past and Some Speculation about the Future


Kamal Jain, Microsoft Research

Title: Iterative Rounding in Graph Connectivity Problems


Jan Kratochvil, Charles University, Prague

Title: Geometric Representations of Graphs

Intersection graphs of geometrical objects are studied both for their practical motivation and applications, and for their interesting theoretical properties. Among these are elegant characterization theorems, polynomial algorithms for problems NP-hard in general graphs, questions about representability of planar graphs or problems from the area surrounding perfect graphs. Often the recognition problem is NP-hard, but for several classes membership to NP is not known (e.g., for intersection graphs of straight line segments in the plane) or comes as a surprise (for the so called string graphs). We will survey recent results and comment on old problems in the area (and vice versa).


Dhruv Mubayi, Carnegie-Mellon University and University of Illinois at Chicago

Title: Three Problems in Extremal Set Theory

A d-simplex is a collection of d+1 sets such that every d of them have nonempty intersection and the common intersection of all of them is empty. A d-cluster of k-sets is a collection of d+1 sets with union of size at most 2k and empty intersection. A 2-regular subsystem is a collection of sets that cover each point in their union exactly twice. Suppose that G is a collection of k-element subsets of an n-element set. What is the maximum number of sets that G can have subject to the following restrictions?

  1. G contains no d-dimplex
  2. G contains no d-cluster
  3. G contains no 2-regular subsystem.

For a large range of the parameters d,k,n, we show that the answers to these three questions are the same.


Jaroslav Nesetril, Charles University Prague

Title: On Line Embeddings of Posets and Structures

We present recent results related to universal posets, graphs and metric spaces with the aim to find a concise (finitely presented) representations. (Joint work with J. Hubicka.)


Janos Pach, City College and Courant Institute, New York

Title: String Graphs and Partial Orders

Any graph that can be represented as the intersection graph of a collection of curves in the plane is called a Title: string graph . It is well known and easy to see that every incomparability graph is a string graph. A graph of n vertices is Title: dense if its number of edges is at least \varepsilon n^2, for a fixed \varepsilon>0. In a joint work with Jacob Fox, we proved that every dense string graph has a dense subgraph which is an incomparability graph. Using the intimate relationship between geometric arrangements and partially ordered sets, together with Fox and Csaba Tóth, we have also established some Ramsey-type results on collections of curves. These problems led to Turán-type questions on comparability and incomparability graphs, interesting in their own right.


Michael Saks, Rutgers University

Title: Distributed Monotonicity Reconstruction

Suppose we have a large data set, i.e., a function f on some enormous finite domain D. The data set ideally should have some specified structural property P, i.e., a list of numbers that should be sorted, a list of points that should be in convex position, or a list of ordered pairs that should define a tree. However, the property may not hold to to inherent errors in the data.

We wish to design an efficient online algorithm that constructs from f a new function g that satisfies property P, and is "close" to f (the Hamming distance of f and g is within a constant fraction of the minimum Hamming distance of f to a function that has property P). The algorithm has access to a single short random string (of size polylogarithmic in |D|) and when presented with an element x of the domain, should make a small (polylogarithic in |D|) number of probes to the function f, and should then output g(x). Such an algorithm is called a "distributed reconstruction algorithm" for the property P.

In this talk, I'll motivate and further describe the above general problem, and discuss recent work of Seshadhri Comandur and myself showing how to construct such a reconstruction algorithm in the case that the function is a multidimensional array and the property to be reconstructed is monotonicity: being sorted along every line of the array.


Carla Savage, North Carolina State University

Title: Lattice Point Enumeration, Linear Extensions, and the Theory of Partitions

This talk will focus on enumeration problems at the intersection of the areas in the title. We share our experiences with techniques and software designed to address them: MacMahon's partition analysis and the Omega package (Andrews, Paule, and Riese); Barvinok's algorithm and LattE (De Loera, Haws, Hemmecke, Huggins, Tauzer, Yoshida); Stanley's P-partitions and the "posets" package (Stembridge), and some special purpose methods.

Can these tools be combined to give new results and insights? We examine some recent successes and challenges.


Paul Seymour, Princeton University

Title: Perfect Matchings in Planar Cubic Graphs

A well-known conjecture of Lovasz and Plummer from the 1970's asserts that for every 2-edge-connected cubic graph G with n vertices, the number of perfect matchings in G is exponential in n. This seems to be wide open still, and currently the best lower bound is n/2, due to Dan Kral.

In this talk we sketch a proof of the Lovasz-Plummer conjecture for PLANAR cubic graphs. In this case the problem is more tractable, because we can use the four-colour theorem as a source of 3-edge-colourings and hence of perfect matchings.


Miklos Simonovits, Mathematical Institute of Eötvös University

Title: On the Number of High Multiplicity Points for 1-Parameter Families of Curves

Considering n plane curves at random, the number of double points will often be quadratic but sometimes no points will belong to three distinct curves. On the other hand, families of straight lines can easily have quadratic number of triple points. The aim of this paper is to provide very general sufficient conditions for one--parameter families of curves not to have n members with "too many" (i.e. a near-quadratic number of) triple points of intersections. As a special case, a combinatorial distinction between straight lines and unit circles will be established. (Actually, originally this motivated our research.) The research is also connected to the Szemerédi-Trotter theorem on the number of incidences of points and lines.

Joint work with György Elekes (Eötvös University, Budapest) and Endre Szabó (Renyi Institute, Budapest)


Angelika Steger, ETH Zurich

Title: On Boltzmann Samplers and Properties of Combinatorial Structures

In the past decades the Gn,p model of random graphs, introduced by Erdos and Renyi~in the 60's, has led to numerous beautiful and deep theorems. A key feature that is used in basically all proofs is that edges in Gn,p appear independently. This situation changes dramatically if one considers graph classes with structural side constraints. For example, in a random planar graph Rn (a graph drawn uniformly at random from the class of all labeled planar graphs on n vertices) the edges are obviously far from being independent. In this talk we show that recent progress in the construction of so-called Boltzmann samplers can be used to reduce the study of properties of combinatorial objects to properties of sequences of independent and identically distributed random variables -- to which we can then again apply the well known machinery from random graph theory.


Benny Sudakov, University of California, Los Angeles

Title: Ramsey Numbers of Sparse Graphs and Hypergraphs

The Ramsey number r(G) of a graph G is the minimum N such that every red-blue coloring of the edges of the complete graph on N vertices contains a monochromatic copy of G. Determining or estimating these numbers is one of the main problems in Ramsey theory. In 1975, Burr and Erdos initiated the study of Ramsey numbers of sparse graphs, which since then has played a central role in the development of graph Ramsey theory. In this talk we will discuss recent progress in this area.


Endre Szemeredi, Rutgers University

Title: A Dirac-Type Theorem for 3-Uniform Hypergraphs

A 3-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every 3 consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an analogous result for uniform hypergraphs: For all n large enough, a sufficient condition for an n-vertex 3-uniform hypergraph to be hamiltonian is that each 2-element set of vertices is contained in at least n/2 edges.

Joint work with Vojtech Rodl and Andrzej Rucinski.


Jacques Verstraete, University of California, San Diego

Title: Cycles in Sparse Graphs

In this talk I will discuss three conjectures of Erdos on cycles in sparse graphs. The first conjecture says that if C(G) is the set of cycle lengths in a graph G of average degree d and girth g, then |C(G)| is always roughly at least the number of vertices in a smallest graph of average degree d and girth g. We give a short proof of this conjecture. The second conjecture states that a graph of large enough average degree must contain a cycle of length a power of two. This conjecture remains open, but we provide some progress towards it by showing that a graph of average degree exp(8log*n) on n vertices contains a cycle of length a power of two, and much more besides. Finally, we discuss a related conjecture of Erdos and Hajnal for graphs of large chromatic number.


Van Vu, Rutgers University

Title: Some Recent Results on Random Matrices

I will discuss a few recent results concerning random Bernoulli matrices, concerning the singular probability, determinant and permanent.


Peter Winkler, Dartmouth College

Title: Branched Polymers

Combinatorics has played a huge role, in recent years, in the understanding of models in statistical physics---usually after the model is moved to a discrete grid. The big surprise with branched polymers (connected sets of non-overlapping unit balls in space) is that no grid is necessary. Interpreting and generalizing the work of David Brydges and John Imbrie, we use elementary combinatorics and calculus to compute the partition function in the plane and in 3-space. Results include algorithms for growing uniformly random polymers, a diameter estimate and an easy proof of Rayleigh's notorious "random flight" theorem. Joint work with Rick Kenyon, Brown University.


Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on May 2, 2008.