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.

# Past Combinatorial Theory Seminar

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.

In a recent breakthrough, Peter Keevash proved the Existence conjecture for combinatorial designs, which has its roots in the 19th century. In joint work with Daniela Kühn, Allan Lo and Deryk Osthus, we gave a new proof of this result, based on the method of iterative absorption. In fact, `regularity boosting’ allows us to extend our main decomposition result beyond the quasirandom setting and thus to generalise the results of Keevash. In particular, we obtain a resilience version and a minimum degree version. In this talk, we will present our new results within a brief outline of the history of the Existence conjecture and provide an overview of the proof.

We will consider the following deceptively simple question, formulated recently by Po Shen Loh who connected it to an open problem in Ramsey Theory. Define the '2-less than' relation on the set of triples of integers by saying that a triple x is 2-less than a triple y if x is less than y in at least two coordinates. What is the maximal length of a sequence of triples taking values in {1,...,n} which is totally ordered by the '2-less than' relation?

In his paper, Loh uses the triangle removal lemma to improve slightly on the trivial upper bound of n^2, and conjectures that the truth should be of order n^(3/2). The gap between these bounds has proved to be surprisingly resistant. We shall discuss joint work with Tim Gowers, giving some developments towards this conjecture and a wide array of natural extensions of the problem. Many of these extensions remain open.