Skip to main content

# 2017-18

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) 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)
Answering questions of Itai Benjamini, we show that the event of complete occupation in 2-neighbour bootstrap percolation on the $d$-dimensional box $[n]^d$, for $d\geq 2$, at its critical initial density $p_c(n)$, is noise sensitive, while in $k$-neighbour bootstrap percolation on the $d$-regular random graph $G_{n,d}$, for $2\leq k\leq d-2$, it is insensitive. Many open problems remain. Joint work with Zsolt Bartha.

##### 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.