Combinatorial Theory Seminar

We study random (simple) graphs with given vertex degrees, in the sparse case where the average degree is bounded. Assume also that the second moment of the vertex degree is bounded. The standard method then is to use the configuration model to construct a random multigraph and condition it on
being simple.

This works well for results of the type that something holds with high probability, or that something converges in probability, but it does not immediately apply to convergence in distribution, for example asymptotic normality. (Although this has been done by special arguments in a couple of cases, by Janson and Luczak and by Riordan.) A typical example is the recent result by Barbour and Röllin on asymptotic normality of the size of the giant component of the multigraph (in the supercritical case); it is an obvious conjecture that the same results hold for the random simple graph.

We discuss two new approaches to this, both based on old methods. Both apply to the size of the giant component, using rather minor special arguments.

One approach uses the method of moments to obtain joint convergence of the variable of interest together with the numbers of loops and multiple edges
in the  multigraph.

The other approach uses switchings to modify the multigraph and construct a simple graph. This simple random graph will not have a uniform distribution,
but almost, and this is good enough.

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings of a graph G on n vertices with maximum degree \Delta is rapidly mixing for k \ge \Delta+2. In 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper k-colorings for k > (11/6)\Delta, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the (11/6)\Delta barrier for general graphs by showing rapid mixing for k > (11/6 - \eta)\Delta for some positive constant \eta. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda’s 2007 survey paper on Glauber dynamics for colorings. 

This is joint work with Michelle Delcourt and Luke Postle.

There was major progress on perfect graphs in the early 2000's: Chudnovsky, Robertson, Thomas and I proved the ``strong perfect graph theorem'' that a graph is perfect if and only if it has no odd hole or odd antihole; and Chudnovsky, Cornuejols, Liu, Vuscovic and I found a polynomial-time algorithm to test whether a graph has an odd hole or odd antihole, and thereby test if it is perfect. (A ``hole'' is an induced cycle of length at least four, and an ``antihole'' is a hole in the complement graph.)

What we couldn't do then was test whether a graph has an odd hole, and this has stayed open for the last fifteen years, despite some intensive effort. I am happy to report that in fact it can be done in poly-time (in time O(|G|^{12}) at the last count), and in this talk we explain how.

Joint work with Maria Chudnovsky, Alex Scott, and Sophie Spirkl.

The Erdos-Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph H, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of r-uniform hypergraphs.

1. A theorem of R\"odl asserts that if an n-vertex graph is non-universal then it contains an almost homogeneous set (i.e one with edge density either very close to 0 or 1) of size \Omega(n). We prove that if a 3-uniform hypergraph is non-universal then it contains an almost homogeneous set of size \Omega(log n). An example of R\"odl from 1986 shows that this bound is tight.

2. Let R_r(t) denote the size of the largest non-universal r-graph G so that neither G nor its complement contain a complete r-partite subgraph with parts of size t. We prove an Erd\H{o}s--Hajnal-type stepping-up lemma, showing how to transform a lower bound for R_r(t) into a lower bound for R_{r+1}(t). As an application of this lemma, we improve a bound of Conlon-Fox-Sudakov by showing that R_3(t) \geq t^{ct).

Joint work with M. Amir and A. Shapira

We continue the study by Melo and Winter [arXiv:1712.01763, 2017] on the possible intersection sizes of a $k$-dimensional subspace with the vertices of the $n$-dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than $2^{k-1}$ (the “large” sizes) are of the form $2^{k-1} + 2^i$. We show that this is almost true: the large intersection sizes are either of this form or of the form $35\cdot2^{k-6}$ . We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing.

The classical theory of Erdős–Rényi random graphs is concerned primarily with random subgraphs of $K_n$ or $K_{n,n}$. Lately, there has been much interest in understanding random subgraphs of other graph families, such as regular graphs.

We study the following problem: Let $G$ be a $k$-regular bipartite graph with $2n$ vertices. Consider the random process where, beginning with $2n$ isolated vertices, $G$ is reconstructed by adding its edges one by one in a uniformly random order. An early result in the theory of random graphs states that if $G=K_{n,n}$, then with high probability a perfect matching appears at the same moment that the last isolated vertex disappears. We show that if $k = Ω(n)$, then this holds for any $k$-regular bipartite graph $G$. This improves on a result of Goel, Kapralov, and Khanna, who showed that with high probability a perfect matching appears after $O(n \log(n))$ edges have been added to the graph. On the other hand, if $k = o(n / (\log(n) \log (\log(n)))$, we construct a family of $k$-regular bipartite graphs in which isolated vertices disappear long before the appearance of perfect matchings.

Joint work with Roman Glebov and Zur Luria.