Past Combinatorial Theory Seminar

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.

I will talk about two separate projects where random walks are building a random tree, yielding preferential attachment behaviour from completely local mechanisms.
First, the Tree Builder Random Walk is a randomly growing tree, built by a walker as she is walking around the tree. At each time $n$, she adds a leaf to her current vertex with probability $n^{-\gamma}, \gamma\in(2/3, 1]$, then moves to a uniform random neighbor on the possibly modified tree. We show that the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási-Albert preferential attachment tree model. This coupling implies that many properties known for the BA-model, such as diameter and degree distribution, can be directly transferred to our model. Joint work with János Engländer, Giulio Iacobelli, and Rodrigo Ribeiro. Second, we introduce a network-of-networks model for physical networks: we randomly grow subgraphs of an ambient graph (say, a box of $\mathbb{Z}^d$) until they hit each other, building a tree from how these spatially extended nodes touch each other. We compute non-rigorously the degree distribution exponent of this tree in large generality, and provide a rigorous analysis when the nodes are loop-erased random walks in dimension $d=2$ or $d\geq 5$, using a connection with the Uniform Spanning Tree. Joint work with Ádám Timár, Sigurdur Örn Stefánsson, Ivan Bonamassa, and Márton Pósfai. (See https://arxiv.org/abs/2306.01583)

We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$ (as induced subposet), but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use $\textrm{sat}^{\ast}(n,k)$ to denote the smallest size of such a family. With more work we pinpoint the exact value of $\textrm{sat}^{\ast}(n,k)$, for all $k$ and sufficiently large $n$. Previously, exact values for $\textrm{sat}^{\ast}(n,k)$ were only known for $k$ up to 6. We also show that for any poset $\mathcal{P}$, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: $\textrm{sat}^{\ast}(n, \mathcal{P})=O(n^c)$, where $c \leq |\mathcal{P}|^2/4+1$. This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.