The ACO Seminar (2008-2009)

Consider the following random graph process. We begin with the empty graph on n vertices and add edges chosen at random one at a time. Each edge is chosen uniformly at random from the collection of pairs of vertices that do not form triangles when added as edges to the existing graph. In this talk I discuss an analysis of the triangle-free process using the so-called differential equations method for random graph processes. It turns out that with high probability the triangle-free process produces a Ramsey R(3,t) graph, a triangle-free graph whose independence number is within a multiplicative constant factor of the smallest possible.

I present an attempt to understand how the recently developed theory of graph limits may apply to finite problem of extremal graph theory. We formulate the notion of a stable problem (meaning, roughly speaking, that almost extremal graphs have structure close to that of an extremal graph) and give an equivalent characterization in terms of graph limits. As an application, we present a new proof of the Erdos-Simonovits stability theorem.

We show that the minimum degree arborescence problem admits a plus 2 approximation algorithm. This is then extended to a large class of "intersecting supermodular" connectivity problems on digraphs, to obtain additive approximations for the degree-bounded variants. As a byproduct of these results, we also obtain a short proof of the recent "plus 1" approximation result for bounded-degree minimum spanning tree.

A partial Steiner (k,l)-system is a k-uniform hypergraph G=(V,E) with the property that every l-element subset of V is contained in at most one edge of G. In this talk we show that for given k, l and t there exists a partial Steiner (k,l)-system such that whenever an l-element subset from every edge is chosen, the resulting l-uniform hypergraph contains a clique of size t. We also establish asymptotic lower and upper bounds on the size of such cliques with respect to the order of Steiner triple systems.

This is joint work with Franti\v{s}ek Fran\v{e}k and Vojta R\"odl.

A starting point of the theory of random matrices is Wigner's semi-circle law obtained in the 1950s, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random hermitian matrix with iid (upper diagonal) entries follows the semi-circle law. The non-hermitian case is the famous Circular Law Conjecture, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random matrix with iid entries is uniform in the unit circle. Despite several important partial results (Ginibre-Mehta, Girko, Bai, Edelman, Gotze-Tykhomirov, Pan-Zhu etc) the conjecture remained open for more than 50 years. This summer, with T. Tao we confirmed the conjecture in full generality. I am going to give an overview of this proof, which relies on rather surprising connections between various fields: combinatorics, probability, number theory and theoretical computer science. In particular, tools from additive combinatorics and Hardy-Littlewood circle method from analytic number theory play crucial roles.

The Erdos-Heilbronn Conjecture states that for any two nonempty subsets A and B of Z/pZ we have |A \dot{+} B| \ge min(p, |A|+|B|-3), where A \dot{+} B is the set of sums a+b mod p with a in A and b \in B and a \neq b. Dias da Silva and Hamidounne established the result for the case A = B in 1994, while Alon, Nathanson, and Ruzsa established the more general result in 1995. We further generalize this result by extending it from Z/pZ to arbitrary finite (including non-abelian) groups.

In recent years, constraint programming has emerged as a powerful technology to model and solve combinatorial optimization problems. It combines an expressive modeling language with powerful inference techniques and advanced search strategies.

One of the most important driving forces behind succesful commercial constraint programming solvers (such as ILOG CP Optimizer) are so-called domain filtering algorithms for global constraints. In this talk I will discuss domain filtering algorithms for several global constraints, including the (soft-)alldifferent constraint, the sequence constraint, and constraints over set variables.

Motivated by the analysis of the Pollard Rho algorithm for the discrete logarithm problem, we develop a birthday theorem regarding self-intersections of Markov chains with uniform stationary distribution. As an application we show that a collision occurs in \Theta(\sqrt{|G|}) steps of the Rho algorithm for finding the discrete log in a cyclic group G. Time permitting, I will describe current work on extensions to the more practically relevant Kangaroo algorithm. This is based on joint papers with Jeong Han Kim, Ravi Montenegro, and Yuval Peres.

The cutoff phenomenon describes a sharp transition in the convergence of a family of ergodic finite Markov chains to equilibrium. Many natural families of chains are conjectured to exhibit cutoff, yet establishing this fact is often extremely challenging. An important such family of chains is the random walk on G(n,d), a random d-regular graph on n vertices. It is well known that the spectral gap of this class of chains for d fixed is constant, implying a mixing-time of O(log n). According to a conjecture of Peres, the simple random walk on G(n,d) for any fixed d should then exhibit cutoff whp. As a special case of this, Durrett conjectured that the mixing time of the lazy random walk on a random 3-regular graph is whp (6+o(1))log₂ n.

In this work we confirm the above conjectures, and establish cutoff in total-variation, its location and its optimal window, both for simple and for non-backtracking random walks on G(n,d). Namely, for any fixed d, the simple random walk on G(n,d) whp has cutoff at [d/(d-2)]log_d-1 n with window order sqrt{log n}. Surprisingly, the non-backtracking random walk on G(n,d) whp has cutoff already at log_d-1 n with constant window order.

We further extend these results to G(n,d) for any d=n^o(1) (beyond which the mixing time is O(1)), provide efficient algorithms for testing cutoff, as well as give explicit constructions where cutoff occurs.

Joint work with Allan Sly.

We introduce a "Polya choice" urn model combining elements of the well known "power of two choices" model and the "rich get richer" model. From a set of $k$ urns, randomly choose $c$ distinct urns with probability proportional to the product of a power $\gamma>0$ of their occupancies, and increment one with the smallest occupancy. The model has an interesting phase transition. If $\gamma \leq 1$, the urn occupancies are asymptotically equal with probability 1. For $\gamma>1$, this still occurs with positive probability, but there is also positive probability that some urns get only finitely many balls while others get infinitely many.

A matching in a graph is a collection of edges no two of which share a vertex. An independent set is a collection of vertices no two of which are spanned by an edge. Both matchings and independent sets arise as configurations in well-studied studied statistical physics models, namely the dimer model and the hard-core model. A theorem of Bregman implies that among all $d$-regular, $N$-vertex bipartite graphs, the one with the most matchings of size $N/2$ (the maximum possible size) is the graph $K(N,d)$ composed of the disjoint union of $N/2d$ complete $d$-regular bipartite graphs. Recently Friedland has conjectured that among $d$-regular, $N$-vertex bipartite graphs, $K(N,d)$ admits the most matchings of size $k$ for any $0 \leq k \leq N/2$. In this talk we report on work in progress using methods from information theory to provide asymptotic evidence for Friedland's conjecture, and its natural analog for independent sets. Joint work with Teena Carroll (Norbert College) and Prasad Tetali (Georgia Tech)

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. We study the problem of bounding t(G) for graphs which do not contain a complete graph K_r on r vertices. This problem was posed twenty years ago by Erdos, Saks, and Sos. Substantially improving earlier results of various researchers, we prove that every connected triangle-free graph on n vertices contains an induced tree of order sqrt(n). When r > 3, we also show that t(G) > (log n)/(4 log r) for every connected K_r-free graph G of order n. Both of these bounds are tight up to small multiplicative constants, and the first one disproves a recent conjecture of Matousek and Samal. Joint work with Jacob Fox and Benny Sudakov.

Given a probability distribution over a set of n words to be transmitted, the Huffman Coding problem is to find a minimal-cost prefix free code for transmitting those words. The basic Huffman coding problem can be solved in O (n log n) time but variations are more difficult. One of the standard techniques for solving these variations utilizes a top-down dynamic programming approach. In this paper we show that this approach is amenable to dynamic programming speedup techniques, permitting a speedup of an order of magnitude for many algorithms in the literature for such variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.

For a graph G, let F(G,r,k) be the number of distinct r-colorings of its edges which contain no monochromatic copy of a k-clique. A natural question is to determine F(n,r,k), the maximum of F(G,r,k) taken over all graphs of order n. A conjecture by Erdos and Rothschild that $F(n,2,3) = 2^\lfloor n^2/4 \rfloor$ was proved by Yuster who further conjectured that the k-1 partite Turan graph achieves the optima for F(n,2,k) for all k. Alon, Balogh, Keevash and Sudakov confirmed this while also showing it remains true for $r=3$. However, for r > 3, they prove one can do significantly better. We show that the 4-partite and 9-partite Turan graphs are the unique graphs achieving the optima for F(n,4,3) and F(n,4,4), respectively.

We discuss some (not so recent) combinatorial results concerning the asymptotic list decoding properties of *linear* codes. We will show the best known existential bounds on the trade-off between list-decodability and rate, which amounts to the following packing question: What is the largest size of a subspace C of the hypercube such that every Hamming ball of a certain radius contains at most L vectors of C? We will also briefly discuss the relation to the code's minimum distance: If every pair of vectors differ in at least a fraction \delta of coordinates, what is the largest radius for which every Hamming ball of that radius is *guaranteed* to have a small (polynomially bounded) number of vectors in it? The talk will be self-contained, and one of its principal objectives is to present some basic (and approachable) open questions in this topic.

In 1998 Duffus, Luczak and Rodl posed the following question: Is there an integer K such that for all graphs G with chromatic number at least K, Maker has a strategy to choose an odd cycle in the game, where Maker chooses one edge and Breaker two, in each round? (Actually, the DLR question was about the vertex claiming version of the game, but the edge claiming version stated above is somewhat more natural and at least equally interesting.)

The above problem is one (yet quite challenging!) example of a general setting of a two player biased game. The game is between Maker and Breaker, who take turns in claiming unoccupied edges of a graph G, the board of the game; Maker takes one edge at a time, while Breaker claims b>=1 edges. The graph G is assumed to be far from a monotone property P, in some well defined quantitative sense, and Maker wins iff by the end of the game his edges form a graph M that does not possess P.

In this talk I will discuss several problems and results of this sort. The aim of the talk is two-fold: to popularize the DLR problem and its relatives, and also to acquaint the audience with the circle of ideas and techniques surrounding this subject.

Joint work with Noga Alon (Tel Aviv) and Dan Hefetz (ETH Zurich).

Correlation inequalities are statements about how events in a probability space positively or negatively reinforce each other. After briefly discussing the better-understood theory of positive correlation, I will talk about some negative correlation inequalities and a potential relationship to celebrated conjectures of J. Mason about log-concavity properties of certain sequences arising from graphs and matroids. Along the way, I'll mention several interesting open problems.

Let $\epsilon$ be a positive number less than $1$. Answering a question of Paul Erdos, Kostochka and Pyber (1988) showed that for large $n$, every $n$-vertex graph with at least $4^{t^2}n^{1+\epsilon}$ edges contains a subdivision of $K_t$ in which each edge of $K_t$ is subdivided at most $c\log t/\epsilon$ times, where $c$ is an absolute constant. Here we prove a complementary (and in some sense stronger) result by eliminating the dependency on $t$. For each $t$ and sufficiently large $n$, we show that every $n$-vertex graph with at least $a(t) n^{1+\epsilon}$ edges, where $a(t)$ is a constant depending on $t$, contains a subdivision of $K_t$ in which each edge of $K_t$ is subdivided at most $c\log (1/\epsilon)/\epsilon$ times, where $c$ is an absolute constant. Note that the number of times each edge is subdivided depends only on $\epsilon$ and does not depend on $t$.