201718
The seminars are held on Friday at 2pm3pm 
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)  TBA 
1 Jun  Hannah Guggiari (Oxford)  TBA 
8 Jun  Jozef Skokan (LSE)  TBA 
15 Jun  Igor Razgon (Birkbeck)  TBA 
22 Jun  Robert Johnson (Queen Mary)  Strategy Stealing in Avoidance Games 
Term 2 2017/18  Room MS.04
Date  Name  Title 

12 Jan  Frederik Garbe (Birmingham)  Contagious sets in a degreeproportional 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ősRé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)  Measurevalued 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)  RamseyTurán problems for cliques 
17 Nov  Johannes Carmesin (Cambridge)  Embedding simply connected 2complexes in 3space 
24 Nov  Jakub Sosnovec (Warwick)  Finitely forcible graphons with an almost arbitrary structure 
1 Dec  Florian Lehner (Warwick)  Bounding the copnumber 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 nearoptimal 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 ncube 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.
RamseyTurá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 RamseyTurán problem, Combinatorica 35 (2015), 435476], we prove that if $\delta$ is sufficiently small (in a sense depending on $t$), then
\[
f_t(\delta)=
\begin{cases}
\frac{3t10}{3t4}+\delta\delta^2 & \text{ if $t$ is even,} \cr
\frac{t3}{t1}+\delta & \text{ if $t$ is odd.}
\end{cases}
\]
This is joint work with Clara M. Lüders.
Embedding simply connected 2complexes in 3space (Johannes Carmesin)
We characterise the embeddability of simply connected 2dimensional simplicial complexes in 3space 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 copnumber of a graph in terms of its genus (Florian Lehner)
The copandrobber 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 degreeproportional 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 bestpossible 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 GaltonWatson 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 wellknown 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ősRényi Graph (Sam Thomas)
We consider the mixing time of a simple random walk $X$ in a dynamical ErdősRényi environment $\eta$, in the sparsesupercritical 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 quasirandom 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 $ab$ 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.
Measurevalued 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 discretetime 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 nonatomic) on a Polish space.
(Joint work with JeanFranç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 3term 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 3term 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 treelike graphs in locally dense graphs (Joonkyung Lee)
We prove that a class of graphs obtained by gluing complete multipartite graphs in a treelike way satisfies a conjecture of Kohayakawa, Nagle, Rödl, and Schacht on randomlike counts for small graphs in locally dense graphs. This implies an approximate version of the conjecture for graphs with bounded treewidth. 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 treelike 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 nvertex graph has the maximum number of monochromatictrianglefree red/blue edgecolourings. While this original problem strengthens Mantel’s theorem, recent years have witnessed the study of the ErdősRothschild extension of several classic combinatorial theorems. In this talk, we seek the ErdősRothschild extension of Sperner’s Theorem. More precisely, we search for the set families in $2^{[n]}$ with the most monochromatickchainfree rcolourings. 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 edgecolouring 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.