Past Combinatorial Theory Seminar

A 1977 conjecture of Erdős and Hajnal asserts that for every hereditary class of graphs not containing all graphs, every graph in the class has a polynomial-sized clique or stable set. Fox, Pach, and Suk and independently Chernikov, Starchenko, and Thomas asked whether this conjecture holds for every class of graphs of bounded VC-dimension. In joint work with Alex Scott and Paul Seymour, we resolved this question in the affirmative. The talk will introduce the Erdős–Hajnal conjecture and discuss some ideas behind the proof of the bounded VC-dimension case.

Permutons are a framework set up for understanding large permutations, and are instrumental in pattern densities. However, they miss most of the algebraic properties of permutations. I will discuss what can still be said in this direction, and some possible ways to move beyond permutons. Joint with Fiona Skerman and Peter Winkler.

Do there exist universal sequences for all mazes on the two-dimensional integer lattice? We will give background on this question, as well as some recent results. Joint work with Mariaclara Ragosta.

Semidefinite programming (SDP) is a powerful tool in the design of approximation algorithms. After providing a gentle introduction to the basics of this method, I will explore a different facet of SDP and show how it can be used to derive short and elegant proofs of both classical and new estimates related to the MaxCut problem and discrepancy theory in graphs and matrices.

Building on this, I will demonstrate how these results lead to an improved upper bound on the celebrated log-rank conjecture in communication complexity.

In this talk I will discuss a new lower bound for the off-diagonal Ramsey numbers $R(3,k)$. For this, we develop a version of the triangle-free process that is significantly easier to analyse than the original process. We then 'seed' this process with a carefully chosen graph and show that it results in a denser graph that is still sufficiently pseudo-random to have small independence number.

This is joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

A matroid is frame if it can be extended such that it possesses a basis $B$ (a frame) such that every element is spanned by at most two elements of $B$. Frame matroids extend the class of graphic matroids and also have natural graphical representations. We characterise the inequivalent graphical representations of 3-connected frame matroids that have a fixed element $\ell$ in their frame $B$. One consequence is a polynomial time recognition algorithm for frame matroids with a distinguished frame element.

Joint work with Jim Geelen and Cynthia Rodríquez.

At most how many edge-disjoint Hamilton cycles does a given directed graph contain? It is easy to see that one cannot pack more than the minimum in-degree or the minimum out-degree of the digraph. We show that in the random directed graph $D(n,p)$ one can pack precisely this many edge-disjoint Hamilton cycles, with high probability, given that $p$ is at least the Hamiltonicity threshold, up to a polylog factor.

Based on a joint work with Asaf Ferber.

Graphs (and structures) which have a linear ordering of their vertices with given local properties have a rich spectrum of complexities. Some have full power of class NP (and thus no dichotomy) but for biconnected patterns we get dichotomy. This also displays the importance of Sparse Incomparability Lemma. This is a joint work with Gabor Kun (Budapest).

The class of $t$-perfect graphs consists of graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. These were first studied by Chvátal in 1975, motivated by the related and well-studied class of perfect graphs. While perfect graphs are easy to colour, the same is not true for $t$-perfect graphs; numerous questions and conjectures have been posed, and even the most basic, on whether there exists some $k$ such that every $t$-perfect graph is $k$-colourable, has remained open since 1994. I will talk about joint work with Maria Chudnovsky, Linda Cook, James Davies, and Sang-il Oum in which we establish the first finite bound and show that a little less than 200 000 colours suffice.

I will discuss various results and conjectures about off-diagonal hypergraph Ramsey numbers, focusing on recent developments.

A set in the Euclidean plane is called an integer distance set if the distance between any pair of its points is an integer.  All so-far-known integer distance sets have all but up to four of their points on a single line or circle; and it had long been suspected, going back to Erdős, that any integer distance set must be of this special form. In a recent work, joint with Marina Iliopoulou and Sarah Peluse, we developed a new approach to the problem, which enabled us to make the first progress towards confirming this suspicion.  In the talk, I will discuss the study of integer distance sets, its connections with other problems, and our new developments.

Upper bounds on the number of incidences between points and lines, tubes, and other geometric objects, have many applications in combinatorics and analysis. On the other hand, much less is known about lower bounds. We prove a general lower bound for the number of incidences between points and tubes in the plane under a natural spacing condition. In particular, if you take $n$ points in the unit square and draw a line through each point, then there is a non-trivial point-line pair with distance at most $n^{-2/3+o(1)}$. This quickly implies that any $n$ points in the unit square define a triangle of area at most $n^{-7/6+o(1)}$, giving a new upper bound for the Heilbronn's triangle problem.

Joint work with Alex Cohen and Cosmin Pohoata.

The normal covering number $\gamma(G)$ of a finite group $G$ is the minimal size of a collection of proper subgroups whose conjugates cover the group. This definition is motivated by number theory and related to the concept of intersective polynomials. For the symmetric and alternating groups we will see how these numbers are closely connected to some elementary (as in "relating to basic concepts", not "easy") problems in additive combinatorics, and we will use this connection to better understand the asymptotics of $\gamma(S_n)$ and $\gamma(A_n)$ as $n$ tends to infinity.

Paraphrasing the title of Riemann’s famous lecture of 1854 I ask: What is the most rudimentary notion of a geometry? A possible answer is a path system: Consider a finite set of “points” $x_1,…,x_n$ and provide a recipe how to walk between $x_i$ and $x_j$ for all $i\neq j$, namely decide on a path $P_{ij}$, i.e., a sequence of points that starts at $x_i$ and ends at $x_j$, where $P_{ji}$ is $P_{ij}$, in reverse order. The main property that we consider is consistency. A path system is called consistent if it is closed under taking subpaths. What do such systems look like? How to generate all of them? We still do not know. One way to generate a consistent path system is to associate a positive number $w_{ij}>0$ with every pair and let $P_{ij}$ be the corresponding $w$-shortest path between $x_i$ and $x_j$. Such a path system is called metrical. It turns out that the class of consistent path systems is way richer than the metrical ones.

My main emphasis in this lecture is on what we don’t know and wish to know, yet there is already a considerable body of work that we have done on the subject.

The new results that I will present are joint with my student Daniel Cizma as well as with him and with Maria Chudnovsky.

I'll discuss how a certain notion of symmetry captures the computational complexity of approximating homomorphism problems between relational structures, also known as constraint satisfaction problems. I'll present recent results on inapproximability of conflict-free and linearly-ordered hypergraph colourings and solvability of systems of equations.

In 1975, Bollobás, Erdős, and Szemerédi asked the following Zarankiewicz-type problem. What is the smallest $\tau$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + \tau$ must contain $K_{t, t, t}$? They further conjectured that $\tau = O(n^{1/2})$ when $t = 2$.

I will discuss our proof that $\tau = O(n^{1 - 1/t})$ (confirming their conjecture) and an infinite family of extremal examples. The bound $O(n^{1 - 1/t})$ is best possible whenever the Kővári-Sós-Turán bound $\operatorname{ex}(n, K_{t, t}) = O(n^{2 - 1/t})$ is (which is widely-conjectured to be the case).

This is joint work with Francesco Di Braccio (LSE).

In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the classical Ramsey numbers since 1935. I will outline a reinterpretation of their proof, replacing the underlying book algorithm with a simple inductive statement. In particular, I will present a complete proof of an improved upper bound on the off-diagonal Ramsey numbers and describe the main steps involved in improving their upper bound for the diagonal Ramsey numbers to $R(k,k)\le(3.8)^k$ for sufficiently large $k$.

Based on joint work with Parth Gupta, Ndiame Ndiaye, and Louis Wei.

Let $(V(u))$ be a branching random walk and $(\eta(u))$ be i.i.d marks on the vertices. To each path $\xi$ of the tree, we associate the discounted sum $D(\xi)$ which is the sum of the $\exp(V(u))\eta_u$ along the path. We study conditions under which $\sup_\xi D(\xi)$ is finite, answering an open question of Aldous and Bandyopadhyay. We will see that this problem is related to the study of the local time process of the branching random walk along a path. It is a joint work with Yueyun Hu and Zhan Shi.

A zero-one matrix $M$ is said to contain another zero-one matrix $A$ if we can delete some rows and columns of $M$ and replace some 1-entries with 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted $\operatorname{ex}(n,A)$, is the maximum number of 1-entries that an $n\times n$ zero-one matrix can have without containing $A$. The systematic study of this function for various patterns $A$ goes back to the work of Furedi and Hajnal from 1992, and the field has many connections to other areas of mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices, but very little is known about the general case (that is, the case where $A$ is not necessarily acyclic). We prove the first asymptotically tight general result by showing that if $A$ has at most $t$ 1-entries in every row, then $\operatorname{ex}(n,A)\leq n^{2-1/t+o(1)}$. This verifies a conjecture of Methuku and Tomon.

Our result also provides the first tight general bound for the extremal number of vertex-ordered graphs with interval chromatic number two, generalizing a celebrated result of Furedi, and Alon, Krivelevich and Sudakov about the (unordered) extremal number of bipartite graphs with maximum degree $t$ in one of the vertex classes.

Joint work with Barnabas Janzer, Van Magnan and Abhishek Methuku.

The celebrated Szemeredi-Trotter theorem states that the maximum number of incidences between $n$ points and $n$ lines in the plane is $\mathcal{O}(n^{4/3})$, which is asymptotically tight.

Solymosi conjectured that this bound drops to $o(n^{4/3})$ if we exclude subconfigurations isomorphic to any fixed point-line configuration. We describe a construction disproving this conjecture. On the other hand, we prove new upper bounds on the number of incidences for configurations that avoid certain subconfigurations. Joint work with Martin Balko.

In a graph $H$ whose edges are coloured (not necessarily properly) a rainbow copy of a graph $G$ is a (not necessarily induced) subgraph of $H$ that is isomorphic to $G$ and whose edges are all coloured differently. In this talk I will explain why the problem of finding such rainbow copies is interesting, survey what we know, concentrating mainly on the case where $G$ is a Hamilton cycle, and then tell you a bit about a new result about finding rainbow Hamilton cycles resiliently in random graphs (which is joint work with Peter Allen and Liana Yepremyan).

The classical lower-tail problem for triangles in random graphs asks the following: given $\eta\in[0,1)$, what is the probability that $G(n,p)$ contains at most $\eta$ times the expected number of triangles?  When $p=o(n^{-1/2})$ or $p = \omega(n^{-1/2})$ the asymptotics of the logarithm of this probability are known via Janson's inequality in the former case and regularity or container methods in the latter case.

We prove for the first time asymptotic formulas for the logarithm of the lower tail probability when $p=c n^{-1/2}$ for $c$ constant.  Our results apply for all $c$ when $\eta \ge 1/2$ and for $c$  small enough when $\eta < 1/2$.  For the special case $\eta=0$ of triangle-freeness, our results prove that a phase transition occurs as $c$ varies (in the sense of a non-analyticity of the rate function), while for $\eta \ge 1/2$ we prove that no phase transition occurs.

Our method involves ingredients from algorithms and statistical physics including rapid mixing of Markov chains and the cluster expansion.  We complement our asymptotic formulas with efficient algorithms to approximately sample from $G(n,p)$ conditioned on the lower tail event.

Joint work with Will Perkins, Aditya Potukuchi and Michael Simkin.

We give an exponential improvement on the upper bound for the $r$-colour diagonal Ramsey number for all $r$. The proof relies on geometric insights and offers a simplified proof in the case of $r=2$.

Joint Work with: Paul Ballister, Béla Bollobás, Marcelo Campos, Simon Griffiths, Rob Morris, Julian Sahasrabudhe and Marius Tiba.

We show that an $n$-vertex $k$-uniform hypergraph, where all $(k-1)$-subsets that are supported by an edge are in fact supported by at least $n/2+o(n)$ edges, contains a spanning $(k-1)$-dimensional sphere. This generalises Dirac's theorem, and confirms a conjecture of Georgakopoulos, Haslegrave, Montgomery, and Narayanan. Unlike typical results in the area, our proof does not rely on the absorption method or the regularity lemma. Instead, we use a recently introduced framework that is based on covering the vertex set of the host hypergraph with a family of complete blow-ups.

This is joint work with Freddie Illingworth, Richard Lang, Olaf Parczyk, and Amedeo Sgueglia.

The study of counting point-hyperplane incidences in the $d$-dimensional space was initiated in the 1990's by Chazelle and became one of the central problems in discrete geometry. It has interesting connections to many other topics, such as additive combinatorics and theoretical computer science. Assuming a standard non-degeneracy condition, i.e., that no $s$ points are contained in the intersection of $s$ hyperplanes, the currently best known upper bound on the number of incidences of $m$ points and $n$ hyperplanes in $\mathbb{R}^d$ is $O((mn)^{1-1/(d+1)}+m+n)$. This bound by Apfelbaum and Sharir is based on geometrical space partitioning techniques, which apply only over the real numbers.

In this talk, we discuss a novel combinatorial approach to study such incidence problems over arbitrary fields. Perhaps surprisingly, this approach matches the best known bounds for point-hyperplane incidences in $\mathbb{R}^d$ for many interesting values of $m, n, d$. Moreover, in finite fields our bounds are sharp as a function of $m$ and $n$ in every dimension. This approach can also be used to study point-variety incidences and unit-distance problem in finite fields, giving tight bounds for both problems under a similar non-degeneracy assumption. Joint work with A. Milojevic and I. Tomon.

An interesting twist on classical subgraph containment problems in graph theory is the following: given a graph $H$ and a collection $\{G_1, \dots , G_m\}$ of graphs on a common vertex set $[n]$, what conditions on $G_i$ guarantee a copy of $H$ using at most one edge from each $G_i$? Such a subgraph is called transversal, and the above problem is closely related to the study of temporal graphs in Network Theory. In 2020 Joos and Kim showed that if $\delta(G_i)\geq n/2$, the collection contains a transversal Hamilton cycle. We improve on their result by showing that it actually contains every transversal Hamilton cycle if $\delta(G_i)\geq (1/2+o(1))n$. That is, for every function $\chi:[n]\to[m]$, there is a Hamilton cycle whose $i$-th edge belongs to $G_{\chi(i)}$.

This is joint work with Candida Bowtell, Patrick Morris and Katherine Staden.

The organizing principle of Ramsey theory is that in large mathematical structures, there are relatively large substructures which are homogeneous. This is quantified in combinatorics by the notion of Ramsey numbers $r(s,t)$, which denote the minimum $N$ such that in any red-blue coloring of the edges of the complete graph on $N$ vertices, there exists a red complete graph on $s$ vertices or a blue complete graph on $t$ vertices.

While the study of Ramsey numbers goes back almost one hundred years, to early papers of Ramsey and Erdős and Szekeres, the long-standing conjecture of Erdős that $r(s,t)$ has order of magnitude close to $t^{s-1}$ as $t \to \infty$ remains open in general. It took roughly sixty years before the order of magnitude of $r(3,t)$ was determined by Jeong Han Kim, who showed $r(3,t)$ has order of magnitude $t^2/\log t$ as $t \to \infty$. In this talk, we discuss a variety of new techniques, including the modern method of containers, which lead to a proof of the conjecture of Erdős that $r(4,t)$ is of order close to $t^3$.

One of the salient philosophies in our approach is that good Ramsey graphs hide inside pseudorandom graphs, and the long-standing emphasis of tackling Ramsey theory from the point of view of purely random graphs is superseded by pseudorandom graphs. Via these methods, we also come close to determining the well-studied related quantities known as Erdős-Rogers functions and discuss related hypergraph coloring problems and applications.

Joint work in part with Sam Mattheus, Dhruv Mubayi and David Conlon.

Models for networks that evolve and change over time are ubiquitous in a host of domains including modeling social networks, understanding the evolution of systems in proteomics, the study of the growth and spread of epidemics etc.

This talk will give a brief summary of three recent findings in this area where stochastic approximation techniques play an important role:

1. Understanding the effect and detectability of change point in the evolution of the system dynamics.
2. Reconstructing the initial "seed" that gave rise to the current network, sometimes referred to as Network Archeology.
3. The disparity in the behavior of different centrality measures such as degree and page rank centrality for measuring popularity in settings where there are vertices of different types such as majorities and minorities as well as insight analyzing such problems give for at first sight unrelated issues such as sampling rare groups within the network.

The main goal will to be convey unexpected findings in each of these three areas and in particular the "unreasonable effectiveness" of continuous time branching processes.

Let $G$ be a $d$-regular graph of growing degree on $n$ vertices. Form a random subgraph $G_p$ of $G$ by retaining edge of $G$ independently with probability $p=p(d)$. Which conditions on $G$ suffice to observe a phase transition at $p=1/d$, similar to that in the binomial random graph $G(n,p)$, or, say, in a random subgraph of the binary hypercube $Q^d$?

We argue that in the supercritical regime $p=(1+\epsilon)/d$, $\epsilon>0$ a small constant, postulating that every vertex subset $S$ of $G$ of at most $n/2$ vertices has its edge boundary at least $C|S|$, for some large enough constant $C=C(\epsilon)>0$, suffices to guarantee likely appearance of the giant component in $G_p$. Moreover, its asymptotic order is equal to that in the random graph $G(n,(1+\epsilon)/n)$, and all other components are typically much smaller.

We also give examples demonstrating tightness of our main result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.

A cluster graph is a disjoint union of complete graphs. We consider the random $G(n,p)$ graph on $n$ vertices with connection probability $p$, conditioned on the rare event of being a cluster graph. There are three main motivations for our study.

1. For $p = 1/2$, each random cluster graph occurs with the same probability, resulting in the uniform distribution over set partitions. Interpreting such a partition as a graph adds additional structural information.
2. To study how the law of a well-studied object like $G(n,p)$ changes when conditioned on a rare event; an evidence of this fact is that the conditioned random graph overcomes a phase transition at $p=1/2$ (not present in the dense $G(n,p)$ model).
3. The original motivation was an application to community detection. Taking a random cluster graph as a model for a prior distribution of a partition into communities leads to significantly better community-detection performance.

This is joint work with Martijn Gösgens, Lukas Lüchtrath, Elena Magnanini and Élie de Panafieu.

Coboundary expansion is a notion introduced by Linial and Meshulam, and by Gromov that combines combinatorics topology and linear algebra. Kaufman and Lubotzky observed its relation to "Property testing", and in recent years it has found several applications in theoretical computer science, including for error correcting codes (both classical and quantum), for PCP agreement tests, and even for studying polarization in social networks.

In the talk I will introduce this notion and some of its applications. No prior knowledge is assumed, of course.

I will talk about the behaviour of random maps on surfaces (for example, random triangulations) of given genus, when their size tends to infinity. Such questions can be asked from the viewpoint of the local behaviour (Benjamini-Schramm convergence) or global behaviour (diameter, Gromov Hausdorff convergence), and in both cases, much combinatorics is involved. I will survey the landmark results for the case of fixed genus, and state very recent results in which we manage to address the "high genus" regime, when the genus grows proportionally to the size – for this regime we establish isoperimetric inequalities and prove the long-suspected fact that the diameter is logarithmic with high probability.

Based on joint work with Thomas Budzinski and Baptiste Louf.

The saturation number of a graph is a famous and well-studied counterpoint to the Turán number, and the rainbow saturation number is a generalisation of the saturation number to the setting of coloured graphs. Specifically, for a given graph $F$, an edge-coloured graph is $F$-rainbow saturated if it does not contain a rainbow copy of $F$, but the addition of any non-edge in any colour creates a rainbow copy of $F$. The rainbow saturation number of $F$ is the minimum number of edges in an $F$-rainbow saturated graph on $n$ vertices. Girão, Lewis, and Popielarz conjectured that, like the saturation number, for all $F$ the rainbow saturation number is linear in $n$. I will present our attractive and elementary proof of this conjecture, and finish with a discussion of related results and open questions.

We show that there exists $C>1$, such that if $A$ is a subset of a non-alternating finite simple group $G$ of density $|A|/|G|= \alpha$, then $AA^{-1}AA^{-1}$ contains a subgroup of density at least $\alpha^{C}$. We will also give a corresponding (slightly weaker) statement for alternating groups.

To prove our results we introduce new hypercontractive inequalities for simple groups. These allow us to show that the (non-abelian) Fourier spectrum of indicators of 'global' sets are concentrated on the high-dimensional irreducible representations. Here globalness is a pseudorandomness notion reminiscent of the notion of spreadness.

The talk is based on joint works with David Ellis, Shai Evra, Guy Kindler, Nathan Lindzey, and Peter Keevash, and Dor Minzer. No prior knowledge of representation theory will be assumed.

A colouring rule is a way to colour the points $x$ of a probability space according to the colours of finitely many measure preserving tranformations of $x$. The rule is paradoxical if the rule can be satisfied a.e. by some colourings, but by none whose inverse images are measurable with respect to any finitely additive extension for which the transformations remain measure preserving. We show that proper graph colouring as a rule can be paradoxical. And we demonstrate rules defined via optimisation that are paradoxical. A connection to measure theoretic paradoxes is established.

The positive discrepancy of a graph $G$ is the maximum surplus of edges in an induced subgraph of $G$ compared to its expected size. This quantity is closely related to other well studied parameters, such as the minimum bisection and the spectral gap. I will talk about the extremal behavior of the positive discrepancy among graphs with given number of vertices and average degree, uncovering a surprising pattern. This leads to an almost complete solution of a problem of Alon on the minimum bisection and let's us extend the Alon-Boppana bound on the second eigenvalue to dense graphs.

Joint work with Eero Räty and Benny Sudakov.

The directed landscape is a random directed metric on the plane that is the scaling limit for models in the KPZ universality class (i.e. last passage percolation on $\mathbb{Z}^2$, TASEP). In this metric, typical pairs of points are connected by a unique geodesic.  However, certain exceptional pairs are connected by more exotic geodesic networks. The goal of this talk is to describe a full classification for these exceptional pairs.

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X\subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices.

We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications.

Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.

Brown-Erdős-Sós initiated the study of the maximum number of edges in an $n$-vertex $r$-graph such that no $k$ edges span at most $s$ vertices. If $s=rk-2k+2$ then this function is quadratic in $n$ and its asymptotic was previously known for $k=2,3,4$. I will present joint work with Stefan Glock, Jaehoon Kim, Lyuben Lichev and Shumin Sun where we resolve the cases $k=5,6,7$.

Given a matrix $A$ with integer entries, a subset $S$ of an abelian group and $r\in\mathbb N$, we say that $S$ is $(A,r)$-Rado if any $r$-colouring of $S$ yields a monochromatic solution to the system of equations $Ax=0$. A classical result of Rado characterises all those matrices $A$ such that $\mathbb N$ is $(A,r)$-Rado for all $r \in \mathbb N$. Rödl and Ruciński, and Friedgut, Rödl and Schacht proved a random version of Rado’s theorem where one considers a random subset of $[n]:=\{1,\dots,n\}$.

In this paper, we investigate the analogous random Ramsey problem in the more general setting of abelian groups. Given a sequence $(S_n)_{n\in\mathbb N}$ of finite subsets of abelian groups, let $S_{n,p}$ be a random subset of $S_n$ obtained by including each element of $S_n$ independently with probability $p$. We are interested in determining the probability threshold for $S_{n,p}$ being $(A,r)$-Rado.

Our main result is a general black box for hypergraphs which we use to tackle problems of this type. Using this tool in conjunction with a series of supersaturation results, we determine the probability threshold for a number of different cases. A consequence of the Green-Tao theorem is the van der Waerden theorem for the primes: every finite colouring of the primes contains arbitrarily long monochromatic arithmetic progressions. Using our machinery, we obtain a random version of this result. We also prove a novel supersaturation result for $[n]^d$ and use it to prove an integer lattice generalisation of the random version of Rado's theorem.

This is joint work with Andrea Freschi and Andrew Treglown (both University of Birmingham).

For integers $k \ge 1$ and $n \ge 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph $K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph $J(n,k,s)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two sets whose intersection has size exactly $s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász' conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

This is joint work with my students Arturo Merino (TU Berlin) and Namrata (Warwick).

Random temporal graphs are a version of the classical Erdős-Rényi random graph $G(n,p)$ where additionally, each edge has a distinct random time stamp, and connectivity is constrained to sequences of edges with increasing time stamps. We are interested in the asymptotics for the distances in such graphs, mostly in the regime of interest where the average degree $np$ is of order $\log n$ ('near' the phase transition).

More specifically, we will discuss the asymptotic lengths of increasing paths: the lengths of the shortest and longest paths between typical vertices, as well as the maxima between any two vertices; this also covers the (temporal) diameter. In the regime $np \gg \log n$, longest increasing paths were studied by Angel, Ferber, Sudakov and Tassion.

The talk contains joint work with Nicolas Broutin and Gábor Lugosi.

In this talk we will review the problem of sharpness in percolation, tracing its origins back to the seminal works of Menshikov, Grimmett-Marstrand and Aizenman-Barsky, which successfully settled the question in the context of Bernoulli independent percolation. Then we will present some recent advancements on the field, which have opened up the possibility of investigating dependent percolation models. Special emphasis will be given to the Interpolation technique, which has proved itself very effective. In particular, it has been used to establish the sharpness for Interlacements Percolation, a model introduced by Sznitman with notoriously intricate dependencies.

This talk is based on a joint work with Duminil-Copin, Goswami, Rodriguez and Severo

A rooted tree $T$ has degree sequence $(d_1,\ldots,d_n)$ if $T$ has vertex set $[n]$ and vertex $i$ has $d_i$ children for each $i$ in $[n]$. 

I will describe a line-breaking construction of random rooted trees with given degree sequences, as well as a way of coupling random trees with different degree sequences that also couples their heights to one another. 

The construction and the coupling have several consequences, and I'll try to explain some of these in the talk.

First, let $T$ be a branching process tree with critical—mean one—offspring distribution, and let $T_n$ have the law of $T$ conditioned to have size $n$. Then the following both hold.
1) $\operatorname{height}(T_n)/\log(n)$ tends to infinity in probability. 
2) If the offspring distribution has infinite variance then $\operatorname{height}(T_n)/n^{1/2}$ tends to $0$ in probability. This result settles a conjecture of Svante Janson.

The next two statements relate to random rooted trees with given degree sequences. 
1) For any $\varepsilon > 0$ there is $C > 0$ such that the following holds. If $T$ is a random tree with degree sequence $(d_1,\ldots,d_n)$ and at least $\varepsilon n$ leaves, then $\mathbb{E}(\operatorname{height}(T)) < C \sqrt{n}$. 
2) Consider any random tree $T$ with a fixed degree sequence such that $T$ has no vertices with exactly one child. Then $\operatorname{height}(T)$ is stochastically less than $\operatorname{height}(B)$, where $B$ is a random binary tree of the same size as $T$ (or size one greater, if $T$ has even size). 

Euclidean Ramsey Theory is a natural multidimensional version of Ramsey Theory. A subset of Euclidean space is called Ramsey if, for any $k$, whenever we partition Euclidean space of sufficiently high dimension into $k$ classes, one class much contain a congruent copy of our subset. It is still unknown which sets are Ramsey. We will discuss background on this and then proceed to some recent results.

In this talk, I will present new results addressing two rather well-known problems on the embeddability of planar graphs on point-sets in the plane. The first problem, often attributed to Mohar, asks for the asymptotics of the minimum size of so-called universal point sets, i.e. point sets that simultaneously allow straight-line embeddings of all planar graphs on $n$ vertices. In the first half of the talk I will present a family of point sets of size $O(n)$ that allow straight-line embeddings of a large family of $n$-vertex planar graphs, including all bipartite planar graphs. In the second half of the talk, I will present a family of $(3+o(1))\log_2(n)$ planar graphs on $n$ vertices that cannot be simultaneously embedded straight-line on a common set of $n$ points in the plane. This significantly strengthens the previously best known exponential bound.