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.