# Combinatorics Seminar

Organisers:

### Term 1 2016/17 - Room MS.04

Date Name Title
7 Oct Felix Reidl (Aachen) Characterising structural sparseness by neighbourhood complexity
Or: If your neighbourhood is boring you probably live in a sparse region.
14 Oct David Ellis (QMUL)  Some applications of the $p$-biased measure to Erd\H{o}s-Ko-Rado type problems
21 Oct Maryam Sharifzadeh (Warwick) Ramsey-Turan-type of extremal problems
28 Oct Ping Hu (Warwick) Tilings in graphons
4 Nov Katherine Staden (Warwick) The number of triangles in a graph with a given number of vertices and edges
11 Nov Alexey Pokrovskiy (ETH) Rainbow cycles and rainbow expanders
18 Nov Agnes Backhausz (Eötvös Loránd University) On the graph limit approach to eigenvectors of random regular graphs
25 Nov Richard Montgomery (Cambridge) Subdivisions in C_4-free graphs
2 Dec Tim Netzer (Innsbruck) Checking Inclusion of Polytopes and Spectrahedra
9 Dec Will Perkins (Birmingham)
An occupancy approach to bounding graph polynomials

### Term 2 2016/17 - Room MS.04

Date Name Title
13 Jan Christoph Koch (Warwick)
Jigsaw percolation on random hypergraphs
20 Jan Mihyun Kang (TU-Graz)
Homological connectivity of random hypergraphs
27 Jan Angelika Steger (ETH Zurich)
Local resilience of almost spanning k-cycles in random graphs
3 Feb Tamas Makai (TU-Graz)
Boostrap percolation on the binomial random graph G(n; p)
10 Feb Mark Jerrum (QMUL)
Counting list H-colourings in hereditary graph classes
17 Feb Amin Coja-Oghlan (Frankfurt)
Information-theoretic thresholds
24 Feb Peter Pach (Budapest)
The cap set problem and the polynomial method
10 Mar Hong Liu (Warwick) Proof of Komlos's conjecture on Hamiltonian subsets
17 Mar Matthew Fitch (Warwick)
Rational Exponents for Hypergraph Turan Problems

### Term 3 2016/17 - Room MS.04

Date Name Title
28 April Timothy Budd (Paris-Saclay)
5 May Lukasz Grabowski (Lancaster)

12 May Jakub Konieczny (Oxford)

19 May
26 May
2 June Olaf Parczyk (Frankfurt)
9 June Andrzej Ruciński (Poznan)

23 June Janos Pach (EPFL)

30 June Yufei Zhao (Oxford)

7 Oct Felix Reidl (Aachen) Characterising structural sparseness by neighbourhood complexity

Or: If your neighbourhood is boring you probably live in a sparse region.

Structurally sparse graphs always had a special place in algorithm theory:
almost any problem becomes much more tractable if we restrict ourselves to
nice graph classes like trees, planar graphs, or graphs excluding a minor.
On the other hand, algorithms on such classes are only of limited use
in real-world settings---hardly any real-world network exhibits these stricter
notions of structural sparseness.

In this talk we will explore a notion of sparseness (so-called bounded expansion
classes introduced by Nesetril and Ossona de Mendez) that is general enough
to hold in real-world settings while still providing use with a rich algorithmic
toolkit. In particular, we will see a novel characterisation of bounded expansion
of structurally sparse graphs.

14 Oct: David Ellis (QMUL) Some applications of the $p$-biased measure to Erd\H{o}s-Ko-Rado type problems

Erd\H{o}s-Ko-Rado type problems' are well-studied in extremal combinatorics; they concern the sizes of families of objects in which any two (or any $r$) of the objects in the family 'agree', or 'intersect', in some way.

If $X$ is a finite set, the '$p$-biased measure' on the power-set of $X$ is defined as follows: choose a subset $S$ of $X$ at random by including each element of $X$ independently with probability $p$. If $\mathcal{F}$ is a family of subsets of $X$, one can consider the {\em $p$-biased measure} of $\mathcal{F}$, denoted by $\mu_p(\mathcal{F})$, as a function of $p$. If $\mathcal{F}$ is closed under taking supersets, then this function is an increasing function of $p$. Seminal results of Friedgut and Friedgut-Kalai give criteria under which this function has a 'sharp threshold'. Perhaps surprisingly, a careful analysis of the behaviour of this function also yields some rather strong results in extremal combinatorics which do not explicitly mention the $p$-biased measure - in particular, in the field of Erd\H{o}s-Ko-Rado type problems. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric three-wise intersecting family of subsets of $\{1,2,\ldots,n\}$ has size $o(2^n)$, and some 'stability' results characterizing the structure of 'large' $t$-intersecting families of $k$–element subsets of $\{1,2,\ldots,n\}$. Based on joint work with (subsets of) Nathan Keller, Noam Lifschitz and Bhargav Narayanan.

21 Oct: Maryam Sharifzadeh (Warwick) Ramsey-Turan-type of extremal problems

Motivated by the fact that the extremal example for Tur\'an theorem has linear-sized independent sets, Erd\H os and S\'os initiated the so-called Ramsey-Tur\'an theory, where they studied the maximum size of an $H$-free graph $G$ with the additional condition that $\alpha(G)=o(|G|)$. During this talk, I will discuss the Ramsey-Tur\'an variation of some classical results, whose extremal graphs are close to the Tur\'an graph, including Corr\'adi-Hajnal theorem on triangle factors in graphs and Erd\H os-Rothschild problem on the number of edge-colorings with no monochromatic clique.

Joint work partly with J\'ozsef Balogh and Hong Liu, and partly with J\'ozsef Balogh and Theodore Molla.

28 Oct: Ping Hu (Warwick) Tilings in graphons

We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F be an edge gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings. As an application of our theory, we determine the asymptotically almost surely F-tiling number of inhomogeneous random graphs G(n,W). As another application, we give a strengthening of a theorem of Komlos, which gives minimum degree threshold that guarantees a prescribed lower bound on the fractional F-cover number of a graphon W.

Joint work with Jan Hladky and Diana Piguet.

4 Nov Katherine Staden (Warwick) The number of triangles in a graph with a given number of vertices and edges

The famous theorem of Tur\'an from 1940 states that every $n$-vertex graph with at least $n^2/4$ edges contains at least one triangle. Erd\H{o}s asked for a quantitative version of this statement: for every n and m, how \emph{many} triangles an must an n-vertex m-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\'asz 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.

4 Nov: Richard Montgomery (Cambridge) Subdivisions in C_4-free graphs

Bollob\'as and Thomason, and independently Koml\'os and Szemer\'edi, showed in 1994 that any graph $G$ with average degree $d(G)$ contains a subdivision of a clique with at least $c\sqrt{d(G)}$ vertices, for some universal constant $c>0$. In 1999, Mader conjectured that $C_4$-free graphs $G$ in fact contain a subdivision of a larger clique, one with at least $c d(G)$ vertices, for some universal constant $c>0$. I will discuss a proof of this conjecture as well as a generalisation concerning $K_{s,t}$-free graphs.

This is joint work with Hong Liu.

11 Nov: Alexey Pokrovskiy (ETH) Rainbow cycles and rainbow expanders

A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. Andersen conjectured that every properly n-edge-coloured complete graph Kn has a rainbow Hamiltonian path. This seminar will be about a proof of an approximate version of this conjecture - that every properly edge-coloured Kn has a rainbow cycle of length n - O(n^{3/4}). One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured Kn formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular it has very good expansion properties.

This is joint work with Noga Alon and Benjamin Sudakov.

18 Nov: Agnes Backhausz (Eötvös Loránd University) On the graph limit approach to eigenvectors of random regular graphs

The goal of the talk is to show how the graph limit approach
can be used to understand spectral properties of large random
regular graphs. In our work, we consider eigenvectors of
random regular graphs of fixed degree. As the number of
vertices tends to infinity, as a "limit", we investigate
invariant random processes on the infinite tree that
satisfy the eigenvalue equation and that can be "modelled" on
random regular graphs. In this infinite setting, based on
certain entropy inequalities, we could prove that (under
appropriate conditions) all these processes are Gaussian.
As a consequence, we could prove that the distribution of
delocalized eigenvectors of finite random regular graphs
is close to the Gaussian distribution. Joint work with Balazs
Szegedy.

2 Dec: Tim Netzer (Innsbruck) Checking Inclusion of Polytopes and Spectrahedra

The question whether one polytope is contained in another arises in interesting applications. Its computational complexity depends on the type of the input, and reaches from polynomial time to co-NP-hard. Spectrahedra are generalizations of polyhedra, and appear as feasible sets in semidefinite programming. In many applications, one or both of the given sets are spectrahedra, and inclusion testing becomes even more complicated, even at a conceptual level. There are certain relaxations of the problem, that work well in practice. After introducing the necessary background, we show that these relaxations are only reliable for simplices, and we derive some quantitative error bounds in the general case. The results use methods from operator theory, and some nice elementary constructions.

9 Dec: Will Perkins (Birmingham) An occupancy approach to bounding graph polynomials

I will present a new method for proving tight bounds on graph polynomials and on the number of independent sets, matchings, and colorings in regular graphs. The method is based on optimizing various observables in relevant probabilistic models from statistical physics (e.g., the hard-core, monomer-dimer, and Potts models) via linear programming relaxations. No previous knowledge of statistical physics is needed for the talk, and I will present many related open problems. Based on joint work with E. Davies, M. Jenssen, and B. Roberts.

13 Jan: Christoph Koch (Warwick) Jigsaw percolation on random hypergraphs

Jigsaw percolation was introduced by Brummit, Chatterjee, Dey, and Sivakoff as a model for interactions within a social network. It was inspired by the idea of collectively solving a puzzle. The premise is that each individual of a group of people has a piece of a puzzle all of which must be combined in a certain way to solve the puzzle. The compatibility of different puzzle pieces and the information which pairs of people meet are stored in two graphs (on a common vertex set), the puzzle graph and the people graph. Bollobás, Riordan, Slivken, and Smith studied the process when both graphs are given by independent binomial random graphs. More abstractly the process can be seen as a notion of simultaneous connectedness of a pair of (random) graphs. We transfer the process to hypergraphs in the context of high-order connectedness. We provide the asymptotic order of the critical threshold probability for percolation when both hypergraphs are chosen binomially at random, extending the result of Bollobás, Riordan, Slivken, and Smith. The evolution of the process is closely related to the presence of traversable triples in the pair of random hypergraphs.

This is joint work with Béla Bollobás, Oliver Cooley, and Mihyun Kang.

20 Jan: Mihyun Kang (TU-Graz) Homological connectivity of random hypergraphs

We consider 2-dimensional simplicial complexes that are generated from the binomial random 3-uniform hypergraph by taking the downward-closure. We determine when this simplicial complex is homologically connected, meaning that its zero-th and first homology groups with coefficients in $\mathbb{F}_2$ vanish. Although this is not intrinsically a monotone property, we show that it nevertheless has a single sharp threshold, and indeed prove a hitting time result relating the connectedness to the disappearance of the last minimal obstruction.

(Joint work with Oliver Cooley, Penny Haxell, and Philipp Spr\"ussel)

27 Jan: Angelika Steger (ETH Zurich) Local resilience of almost spanning k-cycles in random graphs

The famous Posa-Seymour conjecture states that for any k ≥ 2, a graph G = (V, E) with minimum degree kn/(k+1) contains the k-th power of a Hamilton cycle. The conjecture was confirmed a couple of decades later by Komlos, Sarközy, Szemeredi for n large enough. Here we extend this result to a sparse setting. We show that for all k ≥ 2 and ε,α > 0, if p ≥ C(logn/n)1/k then any subgraph of a random graph Gn,p with minimum degree at least (k/(k + 1) + α)np, contains the k-th power of a cycle on at least (1 − ε)n vertices, improving upon the recent results of Noever and Steger for k = 2, as well as Allen, Böttcher, Ehrenmüller and Taraz for k ≥ 3.

3 Feb: Tamas Makai (TU-Graz) Boostrap percolation on the binomial random graph G(n; p)

Bootstrap percolation on a graph, with infection threshold a positive integer r, is an infection process which starts out from a set of initially infected vertices and in each further step every vertex with at least r infected neighbours becomes infected. The process stops once no further vertices can become infected.

We consider bootstrap percolation on the binomial random graph G(n; p), when the set of initially infected vertices has size a, which was investigated among others by Janson, Luczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of infected vertices at the end of the process.

This is joint work with Mihyun Kang.

10 Feb: Mark Jerrum (QMUL) Counting list H-colourings in hereditary graph classes

Suppose H is a fixed graph. H-colourings of a graph G (a.k.a. homomorphisms from G
to H) generalise familiar proper vertex colourings of G. More than 15 years ago, Dyer
and Greenhill considered the computational complexity of counting H-colourings,
and demonstrated a dichotomy, in terms of the graph H, between polynomial time
and #P-complete.

That result was for exact counting, and, even now, there is only a partial complexity
classification for approximate counting. However, the classification problem becomes
tractable if we look instead at _list_ H-colourings. In this talk, I’ll present
a classification (in fact a trichotomy) for the problem of approximately counting
list H-colourings of a graph. It turns out that some interesting hereditary graph
classes come into play in describing and proving the trichotomy result.

This is joint work with Andreas Galanis and Leslie Ann Goldberg (Oxford).

17 Feb: Amin Coja-Oghlan (Frankfurt) Information-theoretic thresholds

In many discrete stuctures such as random error-correcting codes or random graph problems there occurs an information-theoretic phase transition. For example, for "noise levels" above a certain information-theoretic threshold decoding is impossible. In this talk I present a method for proving certain physics predictions on such information-theoretic phase transitions. Among other things this leads to proofs of certain conjectures on low-density generator matrix codes and the random graph coloring problem.

24 Feb: Peter Pach (Budapest) The cap set problem and the polynomial method

The cap set problem asks for the largest possible size of a subset of $\mathbb{F}_3^n$ free of (nonconstant) three-term arithmetic progressions. The best bound prior to 2016 was given by Bateman and Katz, who proved that this size is at most $O(3^n/n^{1+\varepsilon})$ with an absolute constant $\varepsilon>0$. Last year a much better bound, namely $o(2.756^n)$, was obtained with the help of a new variant of the polynomial method. I will talk about this method -- which was first applied for the analogous question about the largest possible size of a progression-free subset of $\mathbb{Z}_4^n$ -- and mention some further applications.

10 Mar: Hong Liu (Warwick) Proof of Komlos's conjecture on Hamiltonian subsets

Komlos 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 Jaehoon Kim, Maryam Sharifzadeh and Katherine Staden.

17 Mar: Matthew Fitch (Warwick) Rational Exponents for Hypergraph Turan Problems

Given a family of k-hypergraphs F, ex(n,F) is the maximum number of edges a k-hypergraph can have, knowing that said hypergraph has n vertices but contains no copy of any hypergraph from F as a subgraph. I will discuss a result I have proved, which says for any rational r between 0 and k-1, there exists some finite family F of k-hypergraphs for which ex(n,F) is of order n^(k-r).