Skip to main content

Combinatorics Seminar


The seminars are held on Friday at 2pm-3pm

Organisers:


John Haslegrave

Katherine Staden



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 subsets
27 Oct Ben Barber (Bristol) Isoperimetry in integer lattices
3 Nov Eoin Long (Oxford) TBA
10 Nov Christian Reiher (Hamburg) TBA
17 Nov Johannes Carmesin (Cambridge) Embedding simply connected 2-complexes in 3-space
24 Nov Jakub Sosnovec (Warwick) TBA
1 Dec Andrew Granville (UCL) TBA
8 Dec Jakub Konieczny (Oxford)
TBA


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≥2, at its critical initial density pc(n), is noise sensitive, while in k-neighbour bootstrap percolation on the d-regular random graph Gn,d, for 2≤k≤d−2, it is insensitive. Many open problems remain. Joint work with Zsolt Bartha.

Monochromatic infinite subsets (Paul Russell)

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 Zd, with edges between pairs of vertices at l1 distance 1. The most attractive open problem was to answer this question for the "strong lattice" on Zd, with edges between pairs of vertices at ldistance 1. Whilst studying this question we in fact solved the edge isoperimetric problem asymptotically for every Cayley graph on Zd. 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.


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.



Embedding simply connected 2-complexes in 3-space

Abstract: 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.