Past Combinatorial Theory Seminar

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.
 

How long a monotone path can one always find in any edge-ordering of the complete graph $K_n$? This appealing question was first asked by Chvatal and Komlos in 1971, and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was $n^{2/3−o(1)}$, which was proved by Milans. This talk will be
about nearly closing this gap, proving that any edge-ordering of the complete graph contains a monotone path of length $n^{1−o(1)}$. This is joint work with Bucic, Kwan, Sudakov, Tran, and Wagner.

Let $G$ be a regular graph of degree $d$ and let $A\subset V(G)$. Say that $A$ is $\eta$-closed if the average degree of the subgraph induced by $A$ is at least $\eta d$. This says that if we choose a random vertex $x\in A$ and a random neighbour $y$ of $x$, then the probability that $y\in A$ is at least $\eta$. In recent joint work with Tim Gowers, we were aiming to obtain a qualitative description of closed subsets of the Cayley graph $\Gamma$ whose vertex set is $\mathbb{F}_2^{n_1}\otimes \dots \otimes \mathbb{F}_2^{n_d}$ with two vertices joined by an edge if their difference is of the form $u_1\otimes \cdots \otimes u_d$. For the matrix case (that is, when $d=2$), such a description was obtained by Khot, Minzer and Safra, a breakthrough that completed the proof of the 2-to-2 conjecture. We have formulated a conjecture for higher dimensions, and proved it in an important special case. In this talk, I will sketch this proof. Also, we have identified a statement about $\eta$-closed sets in Cayley graphs on arbitrary finite Abelian groups that implies the conjecture and can be considered as a "highly asymmetric Balog-Szemerédi-Gowers theorem" when it holds. I will present an example to show that this statement is not true for an arbitrary Cayley graph. It remains to decide whether the statement can be proved for the Cayley graph $\Gamma$.

The last remaining open problem from Erdős and Rényi's original paper on random graphs is the following: for q at least 3, what is the largest d so that the random graph G(n,d/n) is q-colorable with high probability?  A lot of interesting work in probabilistic combinatorics has gone into proving better and better bounds on this q-coloring threshold, but the full answer remains elusive.  However, a non-rigorous method from the statistical physics of glasses - the cavity method - gives a precise prediction for the threshold.  I will give an introduction to the cavity method, with random graph coloring as the running example, and describe recent progress in making parts of the method rigorous, emphasizing the role played by tools from extremal combinatorics.  Based on joint work with Amin Coja-Oghlan, Florent Krzakala, and Lenka Zdeborová.

It is difficult to determine when a graph G can be edge-covered by edge-disjoint copies of a fixed graph F. That is, when it has an F-decomposition. However, if G is large and has a high minimum degree then it has an F-decomposition, as long as some simple divisibility conditions hold. Recent research allows us to prove bounds on the necessary minimum degree by studying a relaxation of this problem, where a fractional decomposition is sought.

I will show how a relatively simple random process can give a good approximation to a fractional decomposition of a dense graph, and how it can then be made exact. This improves the best known bounds for this problem.
 

Consider a family of k-element subsets of an n-element set, and assume that the family does not contain s pairwise disjoint sets. The well-known Erdos Matching Conjecture suggests the maximum size of such a family. Finding the maximum is trivial for n<(s+1)k and is relatively easy for n large in comparison to s,k. There was a splash of activity around the conjecture in the recent years, and, as far as the original question is concerned, the best result is due to Peter Frankl, who verified the conjecture for all n>2sk. In this work, we improve the bound of Frankl for any k and large enough s. We also discuss the connection of the problem to an old question on deviations of sums of random variables going back to the work of Hoeffding and Shrikhande.
 

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an 'enlarged' copy H^+ of a fixed hypergraph H. These include well-known  problems such as the Erdős-Sós 'forbidding one intersection' problem and the Frankl-Füredi 'special simplex' problem.

In this talk we present a general approach to such problems, using a 'junta approximation method' that originates from analysis of Boolean functions. We prove that any (H^+)-free hypergraph is essentially contained in a 'junta' -- a hypergraph determined by a small number of vertices -- that is also (H^+)-free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all C<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes  the aforementioned problems, and solves them for a large new set of parameters.

Based on joint works with David Ellis and Nathan Keller
 

We prove that the dimension of every poset whose comparability graph has maximum degree $\Delta$ is at most $\Delta\log^{1+o(1)} \Delta$. This result improves on a 30-year old bound of F\"uredi and Kahn, and is within a $\log^{o(1)}\Delta$ factor of optimal. We prove this result via the notion of boxicity. The boxicity of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $\Delta$ has boxicity at most $\Delta\log^{1+o(1)} \Delta$, which is also within a $\log^{o(1)}\Delta$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $\Theta(\sqrt{g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor. This is joint work with Alex Scott (arXiv:1804.03271).

We generalise the existence of combinatorial designs to the setting of subset sums in lattices with coordinates indexed by labelled faces of simplicial complexes. This general framework includes the problem of decomposing hypergraphs with extra edge data, such as colours and orders, and so incorporates a wide range of variations on the basic design problem, notably Baranyai-type generalisations, such as resolvable hypergraph designs, large sets of hypergraph designs and decompositions of designs by designs. Our method also gives approximate counting results, which is new for many structures whose existence was previously known, such as high dimensional permutations or Sudoku squares.

We give an alternative, statistical physics based proof of the Ω(d2^{-d}) lower bound for the maximum sphere packing density in dimension d by showing that a random configuration from the hard sphere model has this density in expectation. While the leading constant we achieve is not the best known, we do obtain additional geometric information: we prove a lower bound on the entropy density of sphere packings at this density, a measure of how plentiful such packings are. This is joint work with Felix Joos and Will Perkins.

We characterise the embeddability of simply connected 2-dimensional simplicial complexes in 3-space in a way analogous to Kuratowski’s characterisation of graph planarity, by excluded minors. This answers questions of Lovász, Pardon and Wagner.

 

The Gyárfás-Sumner conjecture says that every graph with huge (enough) chromatic number and bounded clique number contains any given forest as an induced subgraph. The Erdős-Hajnal conjecture says that for every graph H, all graphs not containing H as an induced subgraph have a clique or stable set of polynomial size. This talk is about a third problem related to both of these, the following. Say an n-vertex graph is "c-coherent" if every vertex has degree <cn, and every two disjoint vertex subsets of size at least cn have an edge between them. To prove a given graph H satisfies the Erdős-Hajnal conjecture, it is enough to prove H satisfies the conjecture in all c-coherent graphs and their complements, where c>0 is fixed and as small as we like. But for some graphs H, all c-coherent graphs contain H if c is small enough, so half of the task is done for free. Which graphs H have this property? Paths do (a theorem of Bousquet, Lagoutte, and Thomassé), and non-forests don't. Maybe all forests do? In other words, do all c-coherent graphs with c small enough contain any given forest as an induced subgraph? That question is the topic of the talk. It looks much like the Gyárfás-Sumner conjecture, but it seems easier, and there are already several pretty results. For instance the conjecture is true for all subdivided caterpillars (which is more than we know for Gyárfás-Sumner), and all trees of radius two. Joint work with Maria Chudnovsky, Jacob Fox, Anita Liebenau, Marcin Pilipczuk, Alex Scott and Sophie Spirkl.

A famous theorem of Mantel from 1907 states that every n-vertex graph with more than n^2/4 edges contains at least one triangle. In the 50s, Erdős asked for a quantitative version of this statement: for every n and e, how many triangles must an n-vertex e-edge graph contain?

This question has received a great deal of attention, and a long series of partial results culminated in an asymptotic solution by Razborov, extended to larger cliques by Nikiforov and Reiher. Currently, an exact solution is only known for a small range of edge densities, due to Lovász and Simonovits. In this talk, I will discuss the history of the problem and recent work which gives an exact solution for almost the entire range of edge densities. This is joint work with Hong Liu and Oleg Pikhurko.

The interplay of minimum degree and 'structural properties' of large graphs with a given forbidden subgraph is a central topic in extremal graph theory. For a given graph $F$ we define the homomorphism threshold as the infimum $\alpha$ such that every $n$-vertex $F$-free graph $G$ with minimum degree $>\alpha n$ has a homomorphic image $H$ of bounded size (independent of $n$), which is $F$-free as well. Without the restriction of $H$ being $F$-free we recover the definition of the chromatic threshold, which was determined for every graph $F$ by Allen et al. The homomorphism threshold is less understood and we present recent joint work with O. Ebsen on the homomorphism threshold for odd cycles.

Understanding the distribution of subgraph counts has long been a central question in the study of random graphs. In this talk, we consider the distribution of Sn, the number of K4 subgraphs, in the Erdös Rényi random graph G(n, p). When the edge probability p \in (0, 1) is constant, a classical central limit theorem for Sn states that (Sn−µn)/σn converges in distribution. We establish a stronger form of convergence, namely the corresponding local limit theorem, which is joint work with O. Riordan.
 

A class C of graphs has polynomial expansion if there exists a polynomial p such that for every graph G from C and for every integer r, each minor of G obtained by contracting disjoint subgraphs of radius at most r is p(r)-degenerate. Classes with polynomial expansion exhibit interesting structural, combinatorial, and algorithmic properties. In the talk, I will survey these properties and propose further research directions.

The edge isoperimetric problem for a graph G is to find, for each n, the minimum number of edges leaving any set of n vertices.  Exact solutions are known only in very special cases, for example when G is the usual cubic lattice on Z^d, with edges between pairs of vertices at l_1 distance 1.  The most attractive open problem was to answer this question for the "strong lattice" on Z^d, with edges between pairs of vertices at l_infty distance 1.  Whilst studying this question we in fact solved the edge isoperimetric problem asymptotically for every Cayley graph on Z^d.  I'll talk about how to go from the specification of a lattice to a corresponding near-optimal shape, for both this and the related vertex isoperimetric problem, and sketch the key ideas of the proof. Joint work with Joshua Erde.

Reed conjectured in 1998 that the chromatic number of a graph should be at most the average of the clique number (a trivial lower bound) and maximum degree plus one (a trivial upper bound); in support of this conjecture, Reed proved that the chromatic number is at most some nontrivial convex combination of these two quantities.  King and Reed later showed that a fraction of roughly 1/130000 away from the upper bound holds. Motivated by a paper by Bruhn and Joos, last year Bonamy, Perrett, and I proved that for large enough maximum degree, a fraction of 1/26 away from the upper bound holds. Then using new techniques, Delcourt and I showed that the list-coloring version holds; moreover, we improved the fraction for ordinary coloring to 1/13. Most recently, Kelly and I proved that a 'local' list version holds with a fraction of 1/52 wherein the degrees, list sizes, and clique sizes of vertices are allowed to vary.
 

Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-coloured by n colours with at least n+1 edges of each colour there must be a matching that uses each colour exactly once (such a matching is called rainbow). This conjecture recently have been proved asymptotically by Pokrovskiy. In this talk, I will consider the same question without the bipartiteness assumption. It turns out that in any multigraph with bounded edge multiplicities, that is properly edge-coloured by n colours with at least n+o(n) edges of each colour, there must be a matching of size n-O(1) that uses each colour at most once. This is joint work with Peter Keevash.

A subset S of initially infected vertices of a graph G is called forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a tool in quantum information theory.

The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our bounds on the forcing number of pseudorandom graphs and related problems. The results are joint work with Thomas Kalinowski and Benny Sudakov.

Enumerating families of combinatorial objects with given properties and describing the typical structure of these objects are fundamental problems in extremal combinatorics. In this talk, we will investigate intersecting families of discrete structures in various settings, determining their typical structure as the size of the underlying ground set tends to infinity. Our new approach outlines a general framework for a number of similar problems; in particular, we prove analogous results for hypergraphs, permutations, and vector spaces using the same technique. This is joint work with József Balogh, Shagnik Das, Hong Liu, and Maryam Sharifzadeh.

Given a graph $G$, we can form a hypergraph $H$ whose edges correspond to the triangles in $G$. If $G$ is the standard Erdős-Rényi random graph with independent edges, then $H$ is random, but its edges are not independent, because of overlapping triangles. This is (presumably!) a major complication when proving results about triangles in random graphs.  However, it turns out that, for many purposes, we can treat the triangles as independent, in a one-sided sense (and losing something in the density): we can find an independent random hypergraph within the set of triangles. I will present two proofs, one of which generalizes to larger complete (and some non-complete) subgraphs.

Komlós conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large.  In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify. This is joint work with Hong Liu, Maryam Sharifzadeh and Katherine Staden.

It is well known that there is a finite colouring of the natural numbers such that there is no infinite set X with X+X (the pairwise sums from X, allowing repetition) monochromatic. It is easy to extend this to the rationals. Hindman, Leader and Strauss showed that there is also such a colouring of the reals, and asked if there exists a space 'large enough' that for every finite colouring there does exist an infinite X with X+X monochromatic. We show that there is indeed such a space. Joint work with Imre Leader.