Combinatorics Seminar
Agelos Georgakopoulos
Oleg Pikhurko
The seminars are held on Friday at 2pm3pm
Term 1 2015/16  Room MS.04
Date  Name  Title 

9 Oct  John Haslegrave (Warwick)  Preferential attachment with choice 
16 Oct  Natasha Morrison (Oxford)  Bootstrap Percolation in the Hypercube 
23 Oct  Jie Han (Birmingham)  Dirac's Theorem for Hypergraphs 
30 Oct  Benny Sudakov (ETH Zurich)  Quantitative quasirandomness 
6 Nov  Petter Brändén (KTH Stochholm)  Nonrepresentable hyperbolic matroids 
13 Nov  Liana Yepremyan (McGill)  The Local Stability Method and the Turan numbers of extensions 
20 Nov  Yufei Zhao (Oxford)  
27 Nov  Richard Kenyon (Brown)  Fixedenergy harmonic functions 
4 Dec  Benedikt Stufler (Munich)  Scaling limits and local weak limits of several random discrete structures 
11 Dec  Dániel Korándi (ETH Zurich)  Saturation in random graphs 
Term 2 2015/16  Room MS.04
Date  Name  Title 

15 Jan  Allan Lo (Birmingham) 
Fractional K_tdecompositions of dense graphs 
22 Jan  Jan Volec (ETH Zurich) 
Bounded colorings of graphs and hypergraphs 
29 Jan  Bhargav Narayanan (Cambridge)  Transference for the Erd\H{o}sKoRado theorem 
5 Feb  Hong Liu (Warwick) 
Some enumeration results in extremal combinatorics 
12 Feb at 1:30pm 
Kostas Tyros (Warwick) 
A concentration inequality for product spaces 
19 Feb  Imre Leader (Cambridge) 
Tiling with arbitrary tiles 
26 Feb  The room is unavailable 

4 Mar  Mihalis Kolountzakis (Crete) 
Periodicity for tilings and spectra 
11 Mar  Codrut Grosu (FUBerlin) 
The Towers of Hanoi with p pegs 
18 Mar  Jake Cooper (Warwick) 
Computability and Finite Forcibility of Graph Limits 
Term 3 2015/16  Room MS.04
Date  Name  Title 

29 Apr  Antal Járai (Bath) 
Electrical resistance of the lowdimensional critical branching random walk 
6 May 
Mark Dukes (Strathclyde) 
Chipfiring on the complete bipartite graph 
13 May  Gabor Kun (Budapest)  Expanders, local convergence and Kazhdan Property (T) 
20 May  Jacques Verstraete (UCSD)  Cycles in kchromatic graphs 
27 May  
3 Jun  
10 Jun  Endre Csoka (Budapest)  
17 June  Greg Sorkin (LSE)  
24 Jun  
1 Jul 
9 Oct John Haslegrave (Warwick) Preferential attachment with choice
Preferential attachment models for randomly growing graphs have been
widely studied. In the original model proposed by Barabási and Albert,
each new vertex forms a link to an old vertex chosen at random, with
probabilities proportional to the degrees. Bollobás, Riordan, Spencer and
Tusnády proved that the degree distribution approaches a limit with a
powerlaw tail with index 3, giving the scalefree behaviour seen in many
realworld examples. I will talk about a family of models recently
introduced by Malyshkin and Paquette, in which a new vertex first selects
r existing vertices preferentially, and then chooses the one with sth
highest degree of those r (breaking ties randomly). It was conjectured by
Krapivsky and Redner that whenever s>1 the degree distribution has a
doublyexponential tail; in fact for every s>1 there is a transition
between the conjectured behaviour and a degenerate limiting distribution,
depending on the value of r. The only case which exhibits a third type of
behaviour is when r=2 and s=1, where the tail distribution is given by a
power law with index 2 and a logarithmic correction. This is joint work
with Jonathan Jordan (Sheffield).
16 Oct Natasha Morrison (Oxford) Bootstrap Percolation in the Hypercube
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 \emph{percolates}.
In this talk I will discuss the proof of a conjecture of Balogh and Bollob\'as: for fixed $r$ and $d\to\infty$, the minimum cardinality of a perThe \textit{Tur\'an number} of a graph $G$, denoted by $ex(n,G)$, is
the maximum number of edges in an $G$free graph on $n$ vertices. The
\textit{Tur\'an density} of a graph $G$, denoted by $\pi(G)$, is the
limit as $n$ tends to infinity of the maximum edge density of an
$G$free graph on $n$ vertices. Unless $\pi(G) =0$, it captures the
asymptotic behaviour of $ex(n,G)$.
During this talk I will discuss a method, which we call \textit{local
stability method}, that allows one to obtain exact Tur\'an numbers from
Tur\'an density results. This method can be thought of as an extension
of the classical stability method by generically utilizing
Lagrangians and symmetrization. Using it, we solved a conjecture of
Frankl and Füredi from 1980's and obtained the Tur\'an number of a
hypergraph called, \textit{generalized triangle}, for uniformities 5
and 6. Further, our method is more generally applicable for determining
Tur\'an numbers of socalled \textit{extensions}.
This is joint work with Sergey Norin.
colating set in the $d$dimensional hypercube is $\frac{1+o(1)}{r}\binom{d}{r1}$. One of the key ideas behind the proof exploits a connection between bootstrap percolation and weak saturation. This is joint work with Jonathan Noel.
23 Oct Jie Han (Birmingham)
Dirac's Theorem for Hypergraphs
Cycles are fundamental objects in graph theory. A spanning cycle in a graph is also called a Hamiltonian cycle. The celebrated Dirac's Theorem in 1952 shows that every graph on $n\ge 3$ vertices with minimum degree at least $n/2$ contains a Hamiltonian cycle. In recent years, there has been a strong focus on extending Dirac’s Theorem to hypergraphs. We survey the results along the line and mention some recent progress on this problem.
Joint work with Yi Zhao.
27 Nov Richard Kenyon (Brown) Fixedenergy harmonic functions
This is joint work with Aaron Abrams.
We study the map from conductances to edge energies for harmonic functions
on graphs with Dirichlet boundary conditions.
We prove that for any compatible acyclic orientation and choice of energies there is a unique
choice of conductances such that the associated harmonic function realizes those orientations and energies.
For planar graphs one can construct associated tilings of planar regions with rectangles
of prescribed areas.
For rational energies and boundary data
the Galois group of $Q^{tr}$ (the totally real algebraic numbers) over $Q$ permutes the
enharmonic functions, acting on the set of compatible acyclic orientations.
30 Oct Benny Sudakov (ETH Zurich) Quantitative quasirandomness
A graph is quasirandom if its edge distribution is similar (in a well
defined quantitative way) to that of a random graph with the same edge
density. Classical results of Thomason and ChungGrahamWilson show
that a variety of graph properties are equivalent to quasirandomness.
On the other hand, in some known proofs the error terms which measure
quasirandomness can change quite dramatically when going from one
property to another which might be problematic in some applications.
Simonovits and Sós proved that the property that all induced subgraphs
have about the expected number of copies of a fixed graph H is
quasirandom. However, their proof relies on the regularity lemma and
gives a very weak estimate. They asked to find a new proof for this
result with a better estimate. The purpose of this talk is to
accomplish this.
Joint work with D. Conlon and J. Fox
6 Nov Petter Brändén (KTH Stochholm) Nonrepresentable hyperbolic matroids
Hyperbolic polynomials are multivariate generalisations of realrooted univariate polynomials. More than a decade ago Choe, Oxley, Sokal and Wagner proved that hyperbolic polynomials give rise to a class of matroids which contains the class of matroids representable over the complex numbers. We call such matroids hyperbolic. Wagner and Wei proved that there is a hyperbolic matroid which is not representable over any field, namely the V\'amos matroid. This was used by the speaker to find counterexamples to algebraic versions of the generalised Lax conjecture. The generalised Lax conjecture is an important conjecture in convex optimisation on the characterisation of so called hyperbolicity cones. However the V\'amos matroid is, to this day, essentially the only known nonrepresentable hyperbolic matroid. In this talk we aim to convey a better understanding of nonrepresentability of hyperbolic matroids. We show how Jordan algebras give rise to nonrepresentable hyperbolic matroids, and we create a large class of hyperbolic V\'amoslike matroids (one for each uniform hypergraph) and prove that most of these matroids fail to be representable over any field. This solves a recent conjecture of Burton, Vinzant and Youm. Joint work with Nima Amini.
13 Nov Liana Yepremyan (McGill) The Local Stability Method and the Turan numbers of extensions
The \textit{Tur\'an number} of a graph $G$, denoted by $ex(n,G)$, is
the maximum number of edges in an $G$free graph on $n$ vertices. The
\textit{Tur\'an density} of a graph $G$, denoted by $\pi(G)$, is the
limit as $n$ tends to infinity of the maximum edge density of an
$G$free graph on $n$ vertices. Unless $\pi(G) =0$, it captures the
asymptotic behaviour of $ex(n,G)$.
During this talk I will discuss a method, which we call \textit{local
stability method}, that allows one to obtain exact Tur\'an numbers from
Tur\'an density results. This method can be thought of as an extension
of the classical stability method by generically utilizing
Lagrangians and symmetrization. Using it, we solved a conjecture of
Frankl and Füredi from 1980's and obtained the Tur\'an number of a
hypergraph called, \textit{generalized triangle}, for uniformities 5
and 6. Further, our method is more generally applicable for determining
Tur\'an numbers of socalled \textit{extensions}.
This is joint work with Sergey Norin.
20 Nov Yufei Zhao (Oxford) Large deviations in random graphs
What is the probability that the number of triangles in an Erdős–Rényi random graph exceeds its mean by a constant factor? In this talk, I will discuss some recent progress on this problem.
Already the order in the exponent of the tail probability was a long standing open problem until several years ago when it was solved by DeMarco and Kahn, and independently by Chatterjee. We now wish to determine the exponential rate of the tail probability. Thanks for the works of ChatterjeeVaradhan (dense setting) and ChatterjeeDembo (sparse setting), this large deviations problem reduces to a natural variational problem. We solve this variational problem asymptotically, thereby determining the large deviation rate, which is valid at least for p > 1/n^c for some c > 0.
Based on joint work with Bhaswar Bhattacharya, Shirshendu Ganguly, and Eyal Lubetzky.
4 Dec Benedikt Stufler (Munich) Scaling limits and local weak limits of several random discrete structures
Using a unified approach, we obtain scaling limits and local weak limits of a large variety of random combinatorial structures, such as random unlabelled graphs from subcritical classes. Our methods are based on classical results for branching processes and Renriched trees.
11 Dec Dániel Korándi (ETH Zurich) Saturation in random graphs
A graph H is K_ssaturated if it is a maximal K_sfree graph, i.e., H
contains no clique on s vertices, but the addition of any missing edge
creates one. The minimum number of edges in a K_ssaturated graph was
determined over 50 years ago by Zykov and independently by Erdős, Hajnal
and Moon. In this talk, we consider the random analog of this problem:
minimizing the number of edges in a maximal K_sfree subgraph of the
ErdősRényi random graph G(n,p). We give asymptotically tight estimates on
this minimum, and also provide exact bounds for the related notion of weak
saturation in random graphs.
Joint work with Benny Sudakov.
19 Feb Imre Leader (Cambridge) Tiling with arbitrary tiles
A 'tile' is a finite subset T of Z^n. It may or may not be possible to partition Z^n into copies of T. However, Chalcraft conjectured that
every T does tile Z^d for some d. In this talk, we will discuss some examples, and also a proof of the conjecture, recently obtained in joint work
with Vytautas Gruslys and Ta Sheng Tan.
15 Jan Allan Lo (Birmingham) Fractional K_tdecompositions of dense graphs
A K_tdecomposition of a graph G is a decomposition of G into edgedisjoint K_t. In this talk, we consider its fractional relaxation. Formally speaking, a fractional K_tdecomposition of a graph G is a weighting on the copies of K_t in G such that the sum of the weights of K_t containing any given edge is equal to 1. A result of Haxell and Rödl shows that a fractional K_tdecomposition implies an approximate K_tdecomposition. In this talk we will focus on the minimum degree threshold for the existence of fractional K_tdecompositions and some related problems.
Joint work with Ben Barber, Daniela Kühn, Richard Montgomery and Deryk Osthus.
22 Jan Jan Volec (ETH Zurich) Bounded colorings of graphs and hypergraphs
A conjecture of Bollobas and Erdos from 1976 states that any coloring of edges
of the nvertex complete graph such that at each vertex no color appears more
than (n/2)times contains a properlycolored Hamilton cycle. This problem was
a motivation for the following more general question: Let c be a coloring of
E(K_n) where at each vertex, no color appear more than ktimes. What properly
colored subgraphs does c necessarily contain?
In this talk, I will be interested in spanning subgraphs of K_n that has bounded
maximum degree or the total number of cherries (the paths of length two). I will
also mention similar questions for hypergraphs, as well as analogous problems
concerned with rainbow subgraphs in edge colorings of K_n, where the total number
of appearances for each color is bounded.
One of our main results is a confirms the following conjecture of Shearer from 1979:
If G is an nvertex graph with O(n) cherries and c a coloring of E(K_n) such that
at each vertex every color appears only constantly many times, then c contains a
properly colored copy of G.
The talk is based on a joint work with Nina Kamčev and Benny Sudakov.
29 Jan Bhargav Narayanan (Cambridge) Transference for the Erd\H{o}sKoRado theorem
The Erd\H{o}sKoRado theorem is a central result in extremal set theory which tells us how large uniform intersecting families can be. In this talk, I shall discuss some recent results concerning the 'stability' of this result. One possible formulation of the Erd\H{o}sKoRado theorem is the following: if $n \ge 2r$, then the size of the largest independent set of the Kneser graph $K(n,r)$ is $\binom{n1}{r1}$, where $K(n,r)$ is the graph on the family of $r$element subsets of $\{1,\dots,n\}$ in which two sets are adjacent if and only if they are disjoint. The following will be the question of interest. Delete the edges of the Kneser graph with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? In this talk, I shall show that the answer to this question is in the affirmative even after we delete practically all the edges of the Kneser graph.
5 Feb Hong Liu (Warwick) Some enumeration results in extremal combinatorics
In this talk, I will discuss some recent developments on some enumeration problems in extremal combinatorics. Among others, I will discuss a problem of Cameron and Erd\H{o}s on counting the number of maximal sumfree sets of integers.
12 Feb Kostas Tyros (Warwick) A concentration inequality for product spaces
The aim of this talk is the presentation of a concentration inequality roughly stating the following. If a function $f$ belongs to $L^p(\Omega,\mathcal{F},P)$, where $p>1$ and $(\Omega,\mathcal{F},P)$ is the product space of sufficiently many probability spaces
$(\Omega_1,\mathcal{F}_1,P_1),...,(\Omega_n,\mathcal{F}_n,P_n)$, then there is a long enough interval $I$ of $[n]$
such that for almost all $\mathbf{x}$ in $\prod_{i\in I}\Omega_i$ the expected value of the section $f_\mathbf{x}$ of $f$ at $\mathbf{x}$, that is, the map $f_\mathbf{x}:\prod_{i\in[n]\setminus I}\Omega_i\to\mathbb{R}$ defined by $f_\mathbf{x}(\mathbf{y})=f(\mathbf{x},\mathbf{y})$ for all $\mathbf{y}$
in $\prod_{i\in[n]\setminus I}\Omega_i$, is close to the expected value of $f$.
This is a joint work with P. Dodos and V. Kanellopoulos.
4 Mar Mihalis Kolountzakis (Crete) Periodicity for tilings and spectra
We will talk about periodicity (and structure, more generally) in the study of tilings by translation, where the tile is a set or a function in an Abelian group, and also in the study of spectra of sets (sets of characters which form an orthogonal basis for the functions defined on the set). There are connections to harmonic analysis, number theory, combinatorics and computation, and these make this subject so fascinating. Starting from the Fuglede conjecture, now disproved in dimension at least 3, which would connect tilings with spectra, we will go over cases where periodicity always holds, cases where it is optional and cases where it's never true, in one dimension (most positive results) and higher dimension (most interesting questions).
18 Mar Jake Cooper (Warwick) Computability and Finite Forcibility of Graph Limits
The theory of graph limits seeks to provide analytic representations of large graphs, and has opened new connections between analysis, algebra, combinatorics and probability. Central to this talk will be the analytic object associated with a convergent sequence of (dense) graphs, known as a graphon. Problems from extremal combinatorics have led to the study of a particular class of graphons, the finitely forcible graphons, which are uniquely determined by finitely many subgraph densities. In this talk, we present a universal method of constructing finitely forcible graphons, which include, as special cases, adhoc counterexamples to conjectures of Lovasz and Szegedy on the space of typical vertices. The talk is based on joint work with Dan Kral and Taisa Martins.
29 Apr Antal Járai (Bath) Electrical resistance of the lowdimensional critical branching random walk
When a graph is viewed as an electrical network, important information can be gained about random walk on the graph. In some cases, this led to progress in understanding random walk on random fractal graphs. In this talk, I will present results on the geometry of the spacetime trace of critical branching random walk in Z^d x Z when d < 6. These show that the electrical resistance from the root to distance n grows sublinearly in n. A consequence is that the random walk escapes a ball of radius n faster than it does in dimensions d > 6. (Joint work with A. Nachmias.)
13 May Gabor Kun (Budapest) Expanders, local convergence and Kazhdan Property (T)
Abstract: We prove Bowen's conjecture, that every sequence of graphs that locally converges to the Cayley graph of a finitely generated group with Kazhdan Property (T) is essentially a disjoint union of expanders. We characterize such sequences in terms of the Markov operator. We give applications from ergodic theory to topology. No special background is assumed.
6 May (in MS.01) Mark Dukes (Strathclyde) Chipfiring on the complete bipartite graph
In this talk I will highlight the results of a series of papers that studied chipfiring on the complete bipartite graph. We will see how recurrent configurations on the complete bipartite graph can be classified in terms of parallelograpm polyominoes. This correspondence gives rise to a new bivariate polynomial called the q,tNarayana polynomial that builds on Haglund's work concerning the q,tCatalan polynomial.
20 May Jacques Verstraete (UCSD) Cycles in kchromatic graphs
A wellstudied problem in extremal graph theory is to determine lower bounds on the length of a longest cycle in families of graphs with prescribed chromatic number. It is clear that every $k$chromatic graph contains a cycle of length at least $k$, and it is not hard to show that every trianglefree $k$chromatic graph contains a cycle of length at least $2k$. Erd\H{o}s conjectured that every such graph contains cycles of at least $k^{2  o(1)}$ distinct lengths. In this talk, we prove this conjecture in a strong form, showing that every $k$chromatic trianglefree graph contains cycles of at least roughly $k^2\log k$ distinct lengths. This result is best possible up to the constant, and part of a more general result on $k$chromatic graphs with forbidden subgraphs.