201718
The seminars are held on Friday at 2pm3pm 
Organisers:

Term 2 2017/18  Room MS.04
Date  Name  Title 

12 Jan  
19 Jan  Tom Hutchcroft (Cambridge)  TBA 
26 Jan  Shoham Letzter (Cambridge)  TBA 
2 Feb  
9 Feb  
16 Feb  
23 Feb  
2 Mar  
9 Mar  Cécile Mailler (Bath)  TBA 
16 Mar  Luka Rimanic (Bristol)  TBA 
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.