Combinatorics Seminar
The seminars are held on Friday at 2pm3pm 
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}sKoRado type problems 
21 Oct  Maryam Sharifzadeh (Warwick)  RamseyTurantype 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_4free 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 (TUGraz) 
Homological connectivity of random hypergraphs 
27 Jan  Angelika Steger (ETH Zurich) 
Local resilience of almost spanning kcycles in random graphs 
3 Feb  Tamas Makai (TUGraz) 
Boostrap percolation on the binomial random graph G(n; p) 
10 Feb  Mark Jerrum (QMUL) 
Counting list Hcolourings in hereditary graph classes 
17 Feb  Amin CojaOghlan (Frankfurt) 
Informationtheoretic thresholds 
24 Feb  Peter Pach (Budapest) 
The cap set problem and the polynomial method 
3 Mar  
10 Mar  
17 Mar 
Term 3 2016/17  Room MS.04
Date  Name  Title 

28 April  Timothy Budd (ParisSaclay)  
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)  
16 June  Adam Harper (Warwick) 

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 realworld settingshardly any realworld network exhibits these stricter
notions of structural sparseness.
In this talk we will explore a notion of sparseness (socalled bounded expansion
classes introduced by Nesetril and Ossona de Mendez) that is general enough
to hold in realworld settings while still providing use with a rich algorithmic
toolkit. In particular, we will see a novel characterisation of bounded expansion
classes by 'neighbourhood complexity' that adds to the already diverse framework
of structurally sparse graphs.
14 Oct: David Ellis (QMUL) Some applications of the $p$biased measure to Erd\H{o}sKoRado type problems
Erd\H{o}sKoRado type problems' are wellstudied 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 powerset 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 FriedgutKalai 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}sKoRado type problems. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric threewise 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) RamseyTurantype of extremal problems
Motivated by the fact that the extremal example for Tur\'an theorem has linearsized independent sets, Erd\H os and S\'os initiated the socalled RamseyTur\'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 RamseyTur\'an variation of some classical results, whose extremal graphs are close to the Tur\'an graph, including Corr\'adiHajnal theorem on triangle factors in graphs and Erd\H osRothschild problem on the number of edgecolorings 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 LPduality 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 Ftiling 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 Fcover 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 nvertex medge 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_4free 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 edgecoloured complete graph is called rainbow if all its edges have different colours. Andersen conjectured that every properly nedgecoloured 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 edgecoloured 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 edgecoloured 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 coNPhard. 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 hardcore, monomerdimer, 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 highorder 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 (TUGraz) Homological connectivity of random hypergraphs
We consider 2dimensional simplicial complexes that are generated from the binomial random 3uniform hypergraph by taking the downwardclosure. We determine when this simplicial complex is homologically connected, meaning that its zeroth 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 kcycles in random graphs
The famous PosaSeymour conjecture states that for any k ≥ 2, a graph G = (V, E) with minimum degree kn/(k+1) contains the kth 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 kth 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 (TUGraz) 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 Hcolourings in hereditary graph classes
Suppose H is a fixed graph. Hcolourings 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 Hcolourings,
and demonstrated a dichotomy, in terms of the graph H, between polynomial time
and #Pcomplete.
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_ Hcolourings. In this talk, I’ll present
a classification (in fact a trichotomy) for the problem of approximately counting
list Hcolourings 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 CojaOghlan (Frankfurt) Informationtheoretic thresholds
In many discrete stuctures such as random errorcorrecting codes or random graph problems there occurs an informationtheoretic phase transition. For example, for "noise levels" above a certain informationtheoretic threshold decoding is impossible. In this talk I present a method for proving certain physics predictions on such informationtheoretic phase transitions. Among other things this leads to proofs of certain conjectures on lowdensity 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) threeterm 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 progressionfree subset of $\mathbb{Z}_4^n$  and mention some further applications.