Past Combinatorial Theory Seminar

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.

A central theorem in combinatorics is Sperner’s Theorem, which determines the maximum size of a family in the Boolean lattice that does not contain a 2-chain. Erdos later extended this result and determined the largest family not containing a k-chain. Erdos and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result.

This question was resolved for 2-chains by Kleitman in 1966, who showed that amongst families of size M in the Boolean lattice, the number of 2-chains is minimized by a family whose sets are taken as close to the middle layer as possible. He also conjectured that the same conclusion should hold for all k, not just 2. The best result on this question is due to Das, Gan and Sudakov who showed roughly that Kleitman’s conjecture holds for families whose size is at most the size of the k+1 middle layers of the Boolean lattice. Our main result is that for every fixed k and epsilon, if n is sufficiently large then Kleitman’s conjecture holds for families of size at most (1-epsilon)2^n, thereby establishing Kleitman’s conjecture asymptotically (in a sense). Our proof is based on ideas of Kleitman and Das, Gan and Sudakov.

Joint work with Jozsef Balogh.

Many extremal results on cycles use what may be called BFS method, where a breath first search tree is used as a skeleton to build desired structures. A well-known example is the Bondy-Simonovits theorem that every n-vertex graph with more than 100kn^{1+1/k} edges contains an even cycle of length 2k. The standard BFS method, however, is not easily applicable for supersaturation problems where one wishes to show the existence of many copies of a given  subgraph. The method is also not easily applicable in the hypergraph setting.

In this talk, we focus on some variants of the standard BFS method. We use one of these in conjunction with some useful general reduction theorems that we develop to establish the supersaturation of loose (linear) even cycles in linear hypergraphs. This extends Simonovits' supersaturation theorem on even cycles in graphs. This is joint work with Liana Yepremyan.

If time allows, we will also discuss another variant (joint with Jie Ma) used in the study of Berge cycles of consecutive lengths in hypergraphs.

The $r$-neighbour bootstrap process on a graph $G$ starts with an initial set of "infected" vertices and, at each step of the process, a healthy vertex becomes infected if it has at least $r$ infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of $G$ becomes infected during the process, then we say that the initial set percolates.

In this talk I will discuss the proof of a conjecture of Balogh and Bollobás: for fixed $r$ and $d\to\infty$, the minimum cardinality of a percolating set in the $d$-dimensional hypercube is $\frac{1+o(1)}{r}\binom{d}{r-1}$. One of the key ideas behind the proof exploits a connection between bootstrap percolation and weak saturation. This is joint work with Jonathan Noel.

The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. Reed proved in 1998 that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. A key step in the proof deals with how to spare colors in a graph whose every vertex "sees few edges" in its neighborhood. We improve the existing approach, and discuss its applications to Reed's theorem and strong edge coloring.  This is joint work with Thomas Perrett (Technical University of Denmark) and Luke Postle (University of Waterloo).

Given two $k$-graphs $H$ and $F$, a perfect $F$-packing in $H$ is a collection of vertex-disjoint copies of $F$ in $H$ which together cover all the vertices in $H$. In the case when $F$ is a single edge, a perfect $F$-packing is simply a perfect matching. For a given fixed $F$, it is generally the case that the decision problem whether an $n$-vertex $k$-graph $H$ contains a perfect $F$-packing is NP-complete.

In this talk we describe a general tool which can be used to determine classes of (hyper)graphs for which the corresponding decision problem for perfect $F$-packings is polynomial time solvable. We then give applications of this tool. For example, we give a minimum $\ell$-degree condition for which it is polynomial time solvable to determine whether a $k$-graph satisfying this condition has a perfect matching (partially resolving a conjecture of Keevash, Knox and Mycroft). We also answer a question of Yuster concerning perfect $F$-packings in graphs.

This is joint work with Jie Han (Sao Paulo).
 

We prove tight upper and lower bounds on an observable of the antiferromagnetic Potts model. From this we deduce the case d=3 of a conjecture of Galvin and Tetali on maximising the number of proper colourings in d-regular graphs.