Combinatorial Theory Seminar

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.

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.
 

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.

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.

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 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.

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.