Imre Barany, Alfred Renyi Mathematical Institute
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.
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 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 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. This is joint work with Oliver Riordan from Oxford.
Graham Brightwell, London School of Economics
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.
Maria Chudnovsky, Columbia University
K2,t Minors in Dense Graphs
Abstract
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
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).
Zoltan Furedi, University of Illinois at Urbana-Champaign
Looking for 14-Cycles in the Cube
Abstract
Fan Chung Graham, University of California, San Diego
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.
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
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
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
On-line Partitioning
I will discuss on-line partitioning with special emphasis on joint results with Trotter and new directions.
Kamal Jain, Microsoft Research
Iterative Rounding in Graph Connectivity Problems
Abstract
Jan Kratochvil, Charles University, Prague
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).
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?For a large range of the parameters d,k,n, we show that the answers to these three questions are the same.
- G contains no d-dimplex
- G contains no d-cluster
- G contains no 2-regular subsystem.
Jaroslav Nesetril, Charles University Prague
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
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 string graph. It is well known and easy to see that every incomparability graph is a string graph. A graph of n vertices is 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
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.
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
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.
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)
Joel Spencer, Courant Institute, New York University
The Erdos-Renyi Phase Transition
Abstract
Angelika Steger, ETH Zurich
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
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
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
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
Some Recent Results on Random Matrices
I will discuss a few recent results concerning random Bernoulli matrices, concerning the singular probability, determinant and permanent.
Abstract
Peter Winkler, Dartmouth College
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.
