# Combinatorics Seminar 2015-16

### Agelos Georgakopoulos

Oleg Pikhurko

*The seminars are held on Friday at 2pm-3pm*

### 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) | Non-representable 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) | Fixed-energy 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_t-decompositions 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}s--Ko--Rado 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 |

4 Mar | Mihalis Kolountzakis (Crete) |
Periodicity for tilings and spectra |

11 Mar | Codrut Grosu (FU-Berlin) |
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 low-dimensional critical branching random walk |

6 May |
Mark Dukes (Strathclyde) |
Chip-firing on the complete bipartite graph |

13 May | Gabor Kun (Budapest) | Expanders, local convergence and Kazhdan Property (T) |

20 May | Jacques Verstraete (UCSD) | Cycles in k-chromatic graphs |

10 Jun | Endre Csoka (Budapest) | Independent sets and cuts in large-girth regular graphs |

17 June | Greg Sorkin (LSE) | Costs for VCG auctions and second-best structures |

24 Jun | Freddie Manners (Oxford) | Additive triples of permutations |

**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

power-law tail with index -3, giving the scale-free behaviour seen in many

real-world 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

doubly-exponential 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 so-called \textit{extensions}.*

*This is joint work with Sergey Norin.*

*colating 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.*

**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) **Fixed-energy 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 Chung-Graham-Wilson 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)** Non-representable hyperbolic matroids

Hyperbolic polynomials are multivariate generalisations of real-rooted 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 non-representable hyperbolic matroid. In this talk we aim to convey a better understanding of non-representability of hyperbolic matroids. We show how Jordan algebras give rise to non-representable hyperbolic matroids, and we create a large class of hyperbolic V\'amos-like 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 so-called \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 Chatterjee--Varadhan (dense setting) and Chatterjee--Dembo (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 R-enriched trees.

**11 Dec Dániel Korándi (ETH Zurich)** Saturation in random graphs

A graph H is K_s-saturated if it is a maximal K_s-free 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_s-saturated 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_s-free subgraph of the

Erdős-Ré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_t-decompositions of dense graphs

A K_t-decomposition of a graph G is a decomposition of G into edge-disjoint K_t. In this talk, we consider its fractional relaxation. Formally speaking, a fractional K_t-decomposition 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_t-decomposition implies an approximate K_t-decomposition. In this talk we will focus on the minimum degree threshold for the existence of fractional K_t-decompositions 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 n-vertex complete graph such that at each vertex no color appears more

than (n/2)-times contains a properly-colored 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 k-times. 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 n-vertex 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}s--Ko--Rado theorem

The Erd\H{o}s--Ko--Rado 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}s--Ko--Rado 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{n-1}{r-1}$, 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 sum-free 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, ad-hoc 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 low-dimensional 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 space-time 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 sub-linearly 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)** Chip-firing on the complete bipartite graph

In this talk I will highlight the results of a series of papers that studied chip-firing 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,t-Narayana polynomial that builds on Haglund's work concerning the q,t-Catalan polynomial.

**20 May Jacques Verstraete (UCSD)** Cycles in k-chromatic graphs

A well-studied 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 triangle-free $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 triangle-free 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.

**10 Jun Endre Csoka (Budapest)** Independent sets and cuts in large-girth regular graphs

We show the best known techniques to prove bounds for the size of the largest independent set, cut (bisection), dominating set or other similar structures in large-girth d-regular graphs including large random d-regular graphs. The best known upper bounds were found in the 1980s, but there have been a large progress about the lower bounds in the last decade. We summarize the techniques used in the three most recent papers (2013-2016) and of one new unpublished result. All the lower bounds are constructive, using local algorithms (or constant-time distributed algorithms).

**24 Jun Freddie Manners (Oxford)** Additive triples of permutations

By a "permutation", for now we just mean the elements {1..N} written out

in some order. Suppose we take two of these at random, and add them

together pointwise, modulo N. What is the probability that the

resulting sequence is again a permutation?

This question has been posed in the literature under various guises, and

a number of bounds proven or conjectured. In recent work with Sean

Eberhard and Rudi Mrazovi\'c, we compute the answer up to a factor of 1

+ o(1).

I will outline the proof, which uses Fourier analysis and some methods

from analytic combinatorics.

**17 June Greg Sorkin (LSE)** Costs for VCG auctions and second-best structures

We consider Vickrey-Clarke-Groves (VCG) auctions for a very general combinatorial structure, in an average-case setting where item costs are independent, identically distributed uniform random variables. We prove that the expected VCG cost is at least double the expected nominal cost, and exactly double when the desired structure is the basis of a matroid. In the matroid case, conditioned upon the VCG cost, the expectation of the nominal cost is exactly half the VCG cost, and we show several results relating variances and covariances of the nominal cost, VCG cost, and other quantities. As one application, we find the asymptotic variance of the VCG cost of the minimum spanning tree (MST) in a complete graph with random edge weights. One component in our proofs is an "extended VCG threshold" of possible use in other contexts.

If the cheapest structure is deleted, the cheapest remaining structure ("2nd cheapest") has been used as a baseline for evaluating costs of algorithmic mechanisms including VCG, and one may likewise define 3rd and subsequent structures. I will mention some recent results on costs, in the same average-case setting, of successive spanning trees and shortest paths.

Joint works with Svante Janon, and Alan Frieze and Wesley Pegden.