Combinatorics Seminar
The seminars are held on Friday at 2pm-3pm |
Organisers:
|
Term 3 2017/18 - Room MS.04
| Date | Name | Title |
|---|---|---|
| 27 Apr | Joonkyung Lee (Oxford) | |
| 4 May | Shagnik Das (FU Berlin) | Colourings without monochromatic chains |
| 11 May | Guillem Perarnau (Birmingham) | Rainbow factors in hypergraphs |
| 18 May | Federico Vigolo (Oxford) | Geometric constructions of expanders |
| 25 May | Jaehoon Kim (Birmingham) | Randomly perturbed graphs and spanning trees |
| 1 Jun | Hannah Guggiari (Oxford) | Approximating the position of a hidden agent in a graph |
| 8 Jun | Jozef Skokan (LSE) | The k-colour Ramsey number of odd cycles via non-linear optimisation |
| 15 Jun | Igor Razgon (Birkbeck) | Branching programs and CNFs of bounded treewidth. |
| 22 Jun | Robert Johnson (Queen Mary) | Strategy Stealing in Avoidance Games |
| 29 Jun | Stefan Glock | A rainbow blow-up lemma |
Term 2 2017/18 - Room MS.04
| Date | Name | Title |
|---|---|---|
| 12 Jan | Frederik Garbe (Birmingham) | Contagious sets in a degree-proportional bootstrap percolation process |
| 19 Jan | Tom Hutchcroft (Cambridge) | Geometric and spectral properties of causal maps |
| 26 Jan | Shoham Letzter (Cambridge) | Path partitions of regular graphs |
| 2 Feb | Nikolaos Fountoulakis (Birmingham) | Majority dynamics on random graphs |
| 9 Feb | Sam Thomas (Cambridge) | Mixing Time of Random Walk on Dynamical Erdős-Rényi Graph |
| 16 Feb | Christian Elsholtz (TU Graz) | The combinatorics of multipicative functions |
| 23 Feb | Richard Lang (Birmingham) | |
| 2 Mar | Robert Johnson (Queen Mary) | Strategy Stealing in Avoidance Games (postponed owing to adverse weather conditions) |
| 9 Mar | Cécile Mailler (Bath) | Measure-valued Pólya processes. |
| 16 Mar | Luka Rimanic (Bristol) | Szemerédi's theorem in the primes |
Term 1 2017/18 - Room MS.04
| Date | Name | Title |
|---|---|---|
| 6 Oct | Short talks by several members of the department |
Dan Král' - Uniqueness of extremal configurations Andrzej Grzesik - Forcing cycles in oriented graphs Alex Wendland - A generalisation of Cayley graphs Péter Pach - Forbidden arithmetic progressions Hong Liu - TBA Agelos Georgakopoulos - TBA |
| 13 Oct | Gábor Pete (Rényi Institute and TU Budapest) | Noise sensitivity questions in bootstrap percolation |
| 20 Oct | Paul Russell (Cambridge) | Monochromatic infinite sumsets |
| 27 Oct | Ben Barber (Bristol) | Isoperimetry in integer lattices |
| 3 Nov | Eoin Long (Oxford) | Isoperimetric stability for the cube |
| 10 Nov | Christian Reiher (Hamburg) | Ramsey-Turán problems for cliques |
| 17 Nov | Johannes Carmesin (Cambridge) | Embedding simply connected 2-complexes in 3-space |
| 24 Nov | Jakub Sosnovec (Warwick) | Finitely forcible graphons with an almost arbitrary structure |
| 1 Dec | Florian Lehner (Warwick) | Bounding the cop-number of a graph in terms of its genus |
| 8 Dec | Jakub Konieczny (HUJI) | A density version of Cobham's theorem |
Noise sensitivity questions in bootstrap percolation (Gábor Pete)
Monochromatic infinite sumsets (Paul Russell)
It is well known that there is a finite colouring of the natural numbers such that there is no infinite set $X$ with $X+X$ (the pairwise sums from $X$, allowing repetition) monochromatic. It is easy to extend this to the rationals. Hindman, Leader and Strauss showed that there is also such a colouring of the reals, and asked if there exists a space 'large enough' that for every finite colouring there does exist an infinite $X$ with $X+X$ monochromatic. We show that there is indeed such a space. Joint work with Imre Leader.
Isoperimetry in integer lattices (Ben Barber)
The edge isoperimetric problem for a graph $G$ is to find, for each $n$, the minimum number of edges leaving any set of $n$ vertices. Exact solutions are known only in very special cases, for example when $G$ is the usual cubic lattice on $\mathbb Z^d$, with edges between pairs of vertices at $\ell_1$ distance 1. The most attractive open problem was to answer this question for the "strong lattice" on $\mathbb Z^d$, with edges between pairs of vertices at $\ell_\infty$ distance 1. Whilst studying this question we in fact solved the edge isoperimetric problem asymptotically for every Cayley graph on $\mathbb Z^d$. I'll talk about how to go from the specification of a lattice to a corresponding near-optimal shape, for both this and the related vertex isoperimetric problem, and sketch the key ideas of the proof. Joint work with Joshua Erde.
Isoperimetric stability for the cube (Eoin Long)
The n-cube is the graph on vertex set $\{0,1\}^n$ in which two vertices are adjacent if they differ in a single coordinate. Given a subset $A$ of $\{0,1\}^n$, one may ask how much $A$ 'expands'. Two natural measurements of expansion are given by the edge boundary (how many edges leave $A$) and the vertex boundary (how many vertices are adjacent to some element in $A$). Optimal bounds for these quantities based on the size of $A$ are given by the edge & vertex isoperimetric inequalites for the cube. In this talk I will discuss some recent work which gives stability for these inequalities. Joint work with Peter Keevash.
Ramsey-Turán problems for cliques (Christian Reiher)
An important question in extremal graph theory raised by Vera T. Sós asks to determine for a given integer $t\ge 3$ and a given positive real number $\delta$ the asymptotically supremal edge density $f_t(\delta)$ that an $n$-vertex graph can have provided it contains neither a complete graph $K_t$ nor an independent set of size $\delta n$.
Building upon recent work of Fox, Loh, and Zhao [The critical window for the classical Ramsey-Turán problem, Combinatorica 35 (2015), 435-476], we prove that if $\delta$ is sufficiently small (in a sense depending on $t$), then
\[
f_t(\delta)=
\begin{cases}
\frac{3t-10}{3t-4}+\delta-\delta^2 & \text{ if $t$ is even,} \cr
\frac{t-3}{t-1}+\delta & \text{ if $t$ is odd.}
\end{cases}
\]
This is joint work with Clara M. Lüders.
Embedding simply connected 2-complexes in 3-space (Johannes Carmesin)
We characterise the embeddability of simply connected 2-dimensional simplicial complexes in 3-space in a way analogous to Kuratowski's characterisation of graph planarity, by excluded minors. This answers questions of Lovász and Wagner.
Finitely forcible graphons with an almost arbitrary structure (Jakub Sosnovec)
The theory of combinatorial limits offers analytic tools to study large combinatorial objects. In this theory, an analytic object representing large dense graphs is called a graphon. A graphon is finitely forcible if its structure is determined by finitely many subgraph densities, i.e., the asymptotic structure of graphs represented by such a graphon depends only on finitely many density constraints. Finitely forcible graphons appear in various scenarios, particularly in extremal combinatorics.
Lovász and Szegedy conjectured that all finitely forcible graphons possess a simple structure. This was disproved in a strong sense by Cooper, Král' and Martins, who showed that any graphon is a subgraphon of a finitely forcible graphon. We strenghten this result by showing for every $\varepsilon>0$ that any graphon spans a $1-\varepsilon$ proportion of a finitely forcible graphon.
Join work with Daniel Král', László M. Lovász and Jonathan A. Noel.
Bounding the cop-number of a graph in terms of its genus (Florian Lehner)
The cop-and-robber game is a game on a graph played between two players, a set of cops, and a single robber. The rules of the game are as follows: In the first round both the cops and the robber choose starting vertices, in each consecutive even round each cop can move to a neighbouring vertex, in odd rounds, the robber can move to a neighbouring vertex. The game has perfect information, meaning that each player knows the positions of both the cops and the robber at any point in time. The cops win, if after some finite number of steps one of them occupies the same vertex as the robber, otherwise the robber wins.
A graph $G$ is called $k$-cop win, if for a set of $k$ cops there is a strategy to win the game no matter how the robber plays. The cop number $c(G)$ is the least number $k$ such that $G$ is $k$-cop win. This notion was first introduced in 1984 by Aigner and Fromme, who showed that the cop number of a planar graph is at most $3$. Using similar techniques, Quilliot showed that if $G$ can be embedded on an orientable surface of genus $g$, then $c(G) \leq 2g + 3$. Schroeder subsequently improved this bound to $\frac 32 g + 3$ and conjectured an upper bound of $g+3$.
Using a reduction to a topological game played on an orientable surface, we are able to further improve the bound to $\frac 43 g + 3$ which to our knowledge is the first improvement since Schroeder first formulated his conjecture in 2001.
Joint work with N. Bowler, J. Erde, and M. Pitz.
A density version of Cobham's theorem (Jakub Konieczny)
Cobham's theorem asserts that if a sequence is automatic with respect to two multiplicatively independent bases, then it is ultimately periodic. In the talk I will discuss the proof of a stronger density version of the result: if two sequences which are automatic with respect to two multiplicatively independent bases coincide on a set of density one, then they also coincide on a set of density one with a periodic sequence. This has application to a problem of Deshouillers and Ruzsa concerning the least nonzero digit of $n!$ in base 12. Based on joint work with J. Byszewski.
Contagious sets in a degree-proportional bootstrap percolation process (Frederik Garbe)
We study the following bootstrap percolation process: given a connected graph $G$, we infect an initial set of vertices $A$, and in each step a vertex $v$ becomes infected if at least a $\rho$-proportion of its neighbours are infected (where $\rho$ is a fixed constant). Once infected, a vertex remains infected forever. A set $A$ which infects the whole graph is called a contagious set. It is natural to ask for the minimal size of a contagious set.
Our main result states that for every $\rho$ between 0 and 1, every connected graph $G$ on $n$ vertices has a contagious set of size less than $2\rho n$ or a contagious set of size 1 (note that allowing the latter possibility is necessary since every contagious set has size at least one). This improves previous results of Chang and of Chang and Lyuu, who established the analogous bounds with $5.83 \rho n$ and $4.92 \rho n$ respectively in place of $2 \rho n$, and also improves a recent result of Gentner and Rautenbach, who proved the analogous result with $(2+\varepsilon)\rho n$ in place of $2 \rho n$ for the special case when $G$ has girth at least five and $\rho$ is sufficiently small compared to $\varepsilon$. Moreover, a simple construction shows that our theorem is best-possible in the sense that the bound $2\rho n$ cannot be replaced by $C \rho n$ for any $C \lt2$.
This is joint work with Andrew McDowell and Richard Mycroft.
Geometric and spectral properties of causal maps (Tom Hutchcroft)
Consider the random graph formed by first taking a critical Galton-Watson plane tree, and then adding the horizontal connections between successive vertices in each level. This very simple random graph model is essentially the same thing as the 1+1 dimensional causal dynamical triangulation that was introduced by Ambjorn and Loll as a model of quantum gravity and has been studied extensively by physicists. In this talk, I will discuss the following questions about this graph:
- What does the graph look like as a metric space?
- How does random walk on the graph behave?
Joint work with Nicolas Curien and Asaf Nachmias.
Path partitions of regular graphs (Shoham Letzter)
The well-known theorem of Dirac (1952) states that a graph on $n$ vertices with minimum degree at least $n/2$ contains a Hamilton cycle. As a possible generalisation of Dirac's result, Magnant and Martin (2009) conjectured that every $k$-regular graph on $n$ vertices can be partitioned into at most $n/(k+1)$ paths, a bound which is attained by a disjoint union of $k+1$ cliques. Note that the regularity assumption is needed in order to allow for a partition into a small number of paths, as otherwise a sufficiently unbalanced bipartite graph is a counter example. We prove this conjecture in the case where $k$ is linear in $n$ and $n$ is large.
This talk is based on joint work with Vytautas Gruslys.
Majority dynamics on random graphs (Nikolaos Fountoulakis)
In this talk I will discuss some work in progress about the evolution of majority dynamics. This is a process on graphs which proceeds in rounds. Each vertex can take one of two possible states and during each round each vertex adopts the state of the majority of its neighbours or retains its state if there is a tie. This is not a monotone process and the state of a vertex may change more than once. We are going to discuss the evolution of this dynamics on random graphs. Our focus will be the $G(n,p)$ model and our work towards the proof of a conjecture of Benjamini, Chan, O'Donnel , Tamuz and Tan.
This is joint work with M. Kang and T. Makai from TU Graz.
Mixing Time of Random Walk on Dynamical Erdős-Rényi Graph (Sam Thomas)
We consider the mixing time of a simple random walk $X$ in a dynamical Erdős-Rényi environment $\eta$, in the sparse-supercritical regime. We use a coupling argument: we start with two systems, $(X,\eta)$ and $(Y,\xi)$; first we couple the two environments, $\eta$ and $\xi$, then we couple the walks, $X$ and $Y$. To couple the walks, we temporarily decouple the environments, before recoupling them to finish. This is joint work with Perla Sousi.
The combinatorics of multipicative functions (Christian Elsholtz)
The Paley graph is an interesting example of a quasi-random graph, defined by a simple number theoretic construction: Let $E=\mathbb{F}_p$ ($p\equiv 1 \bmod 4$ a prime), and $(a,b)$ is an edge iff $a-b$ is a square mod $p$. There are many nice properties going back to the fact that a product of squares is again a square.
In this talk we discuss completely multiplicative functions $f:\mathbb{N} \rightarrow \{-1,1\}$. A famous example is the Liouville $\lambda$-function: $\lambda(n)=(-1)^{\Omega(n)}$, where $\Omega(n)$ is the number of prime factors, with multiplicity. This function behaves quite random like. However, what one can actually prove is much weaker than related results on the Paley graph.
An old conjecture of S. Chowla says for every $k$ the sequence $(\lambda(n+1), ..., \lambda(n+k))$ should include each of the $2^k$ sign patterns infinitely often. It is also expected that all of the sign patterns of size $k$ occur with density $1/2^k$, but this is unknown even when $k=2$.
There has been much recent work on such questions, (e.g. Sign patterns of the Liouville and Möbius functions by Kaisa Matomäki, Maksym Radziwill and Terence Tao).
Monochromatic Cycle Partitioning (Richard Lang)
A classic result of Erdős, Gyárfás and Pyber states that for every edge colouring of the complete graph with $r$ colours, there is a cover of its vertex set into at most $f(r)=25r^2 \log r$ monochromatic disjoint cycles. In this talk, I will address some of the recent developments in this area when the host graph is not complete.
Strategy Stealing in Avoidance Games (Robert Johnson)
Let H be a hypergraph. In the achievment game on H, two players take it in turns to colour vertices of H in their own colour. The player who first achieves an edge of H in their colour wins. The well known strategy stealing argument shows that for any H this game is either a first player win or a draw.
We consider the avoidance (or misere) version of this game in which the first player to achieve an edge of H in their colour loses. A plausible hope (implicit in a remark of Beck) is that when H is transitive, the avoidance game is either a second player win or a draw. We show that this is false and investigate what possible extra conditions on H may make it true.
Joint work with Imre Leader and Mark Walters.
Measure-valued Pólya processes (Cécile Mailler)
A Pólya urn is a stochastic process that describes the composition of an urn that contains balls of different colours. The set of colours is usually a finite set $\{1, ... , d\}$. At each discrete-time step, one draws a ball uniformly at random in the urn (let $c$ be its colour), and replace it in the urn together with $R(c,i)$ balls of colour $i$, for all $i = 1, ... , d$. In this talk, I will present a generalisation of this model to an infinite, and potentially uncountable set of colours. In this new framework, the composition of the urn is a measure (possibly non-atomic) on a Polish space.
(Joint work with Jean-François Marckert.)
Szemerédi's theorem in the primes (Luka Rimanic)
Green and Tao famously proved in 2005 that any subset of the primes of fixed positive density contains arbitrarily long arithmetic progressions. Green had previously shown that, in fact, subsets of the primes of relative density tending to zero contain a 3-term progression. This was followed by work of Helfgott and de Roton, and Naslund, who improved the bounds on the relative density in the case of 3-term progressions. Henriot extended this result to systems of complexity one. The aim of this talk is to present an analogous result for longer progressions. This is joint work with Julia Wolf.
Counting tree-like graphs in locally dense graphs (Joonkyung Lee)
We prove that a class of graphs obtained by gluing complete multipartite graphs in a tree-like way satisfies a conjecture of Kohayakawa, Nagle, Rödl, and Schacht on random-like counts for small graphs in locally dense graphs. This implies an approximate version of the conjecture for graphs with bounded tree-width. We also prove an analogous result for odd cycles instead of complete multipartite graphs.
The proof uses a general information theoretic method to prove graph homomorphism inequalities for tree-like structured graphs, which may be of independent interest.
Colourings without monochromatic chains (Shagnik Das)
In 1974, Erdős and Rothschild introduced a new kind of extremal problem, asking which n-vertex graph has the maximum number of monochromatic-triangle-free red/blue edge-colourings. While this original problem strengthens Mantel’s theorem, recent years have witnessed the study of the Erdős-Rothschild extension of several classic combinatorial theorems. In this talk, we seek the Erdős-Rothschild extension of Sperner’s Theorem. More precisely, we search for the set families in $2^{[n]}$ with the most monochromatic-k-chain-free r-colourings. Time and interest permitting, we shall present some results, sketch some proofs, and offer open problems.
This is joint work with Roman Glebov, Benny Sudakov and Tuan Tran.
Rainbow factors in hypergraphs (Guillem Perarnau)
For any $r$-graph $H$, we consider the problem of finding a rainbow $H$-factor in an $r$-graph $G$ with large minimum $l$-degree and an edge-colouring that is suitably bounded. We show that the asymptotic degree threshold is the same as that for finding an $H$-factor. This is joint work with Matthew Coulson, Peter Keevash and Liana Yepremyan.
Geometric constructions of expanders (Federico Vigolo)
In this talk I will introduce a new means of constructing families of expanders by approximating actions on metric measure spaces. I will then illustrate some unexpected geometric and rigidity properties of the expanders thus obtained.
Randomly perturbed graphs and spanning trees (Jaehoon Kim)
A classical result of Komlós, Sárközy and Szemerédi states that every $n$-vertex graph with minimum degree at least $(1/2+ o(1))n$ contains every $n$-vertex tree with maximum degree at most $O(n/\log{n})$ as a subgraph, and the bounds on the degree conditions are sharp.
On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every $n$-vertex graph $G$ with minimum degree at least $\alpha n$ for any fixed $\alpha >0$ and every $n$-vertex tree $T$ with bounded maximum degree, one can still find a copy of $T$ in $G$ with high probability after adding $O(n)$ randomly-chosen edges to $G$.
We extend this result to trees with unbounded maximum degree. More precisely, for a given $n^{\epsilon}\leq \Delta\leq cn/\log n$ and $\alpha>0$, we determined the precise number (up to a constant factor) of random edges that we need to add to an arbitrary $n$-vertex graph $G$ with minimum degree $\alpha n$ in order to guarantee with high probability a copy of any fixed $T$ with maximum degree at most $\Delta$. This is joint work with Felix Joos.
Approximating the position of a hidden agent in a graph (Hannah Guggiari)
A cat and mouse play a pursuit and evasion game on a connected graph $G$ with $n$ vertices. The mouse moves to vertices $m_1$, $m_2$,... of $G$ where $m_i$ is in the closed neighbourhood of $m_{i-1}$ for $i>1$. The cat tests vertices $c_1$, $c_2$,... of $G$ without restriction and is told whether the distance between $c_i$ and $m_i$ is at most the distance between $c_{i-1}$ and $m_{i-1}$. The mouse knows the cat's strategy, but the cat does not know the mouse's strategy. We will show that the cat can determine the position of the mouse up to distance $O(\sqrt{n})$ within finite time and that this bound is tight up to a constant factor. This disproves a conjecture of Dayanikli and Rautenbach. This is joint work with Alexander Roberts and Alex Scott.
The k-colour Ramsey number of odd cycles via non-linear optimisation (Jozef Skokan)
For a graph $G$, the $k$-colour Ramsey number $R_k(G)$ is the least integer $N$ such that every $k$-colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $G$. Let $C_n$ denote the cycle on $n$ vertices. We show that for fixed $k > 2$ and $n$ odd and sufficiently large, $R_k(C_n) = 2^{k-1}(n-1) + 1.$
This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a conjecture of Bondy and Erdős for large $n$. We also establish a surprising correspondence between extremal $k$-colourings for this problem and perfect matchings in the hypercube $Q_k$. This allows us to in fact prove a stability-type generalisation of the above. The proof is analytic in nature, the first step of which is to use the Regularity Lemma to relate this problem in Ramsey theory to one in convex optimisation.
This is joint work with Matthew Jenssen.
Branching programs and CNFs of bounded treewidth (Igor Razgon)
Non-deterministic read-once branching programs (NOROBP) is a model for representation of Boolean functions. This model subsumes deterministic read-once branching programs and also Ordered Binary Decision diagrams having several important theoretical and practical applications.
In this talk I will consider how efficient NROBPs are in representing CNFs with bounded (primal graph) treewidth. In particular, for each (sufficiently) large $k$ there is an infinite class of CNFs of treewidth at most $k$ whose size of corresponding NROBPs is $n^{\Omega(k)}$. In other words, NROBPs are \emph{not} fixed-parameter tractable in representation of CNFs of bounded treewidth. Given the generality of the model, we can say that read-once branching programs are inherently uncapable to efficiently represent CNFs of bounded treewidth.
From the purely graph theoretical perspective, this result considers a particular, `compact' representation of all vertex covers of the given graph $G$ and shows that if $G$ has a bounded degree then the size of this representation is exponential in the pathwidth of $G$.
The above result has been published in [R, Algorithmica 75(2): 277-294 (2016)]. We will also discuss possible generalization of this result to more powerful models of representation of Boolean functions and interesting combinatorial questions that arise from this research direction.
A rainbow blow-up lemma (Stefan Glock)
We prove a rainbow version of the blow-up lemma of Koml\'os, S\'ark\"ozy and Szemer\'edi for globally bounded edge colourings. In the talk, we shall discuss applications of our blow-up lemma to rainbow embeddings of bounded degree spanning subgraphs and even rainbow decompositions. We will also sketch some ideas of the proof, based on the switching method and the partial resampling algorithm developed by Harris and Srinivasan. This is joint work with Felix Joos.