Past Combinatorial Theory Seminar

We determine the minimal forbidden minors characterising the class of countable graphs that embed into some compact surface. We will also discuss Thomas’s conjecture that the Robertson—Seymour Graph Minor Theorem extends to countably infinite graphs. [https://arxiv.org/abs/2301.11042]

Consider the following "controlled" random graph process: edges of the complete graph are revealed one by one in random order to an online algorithm, which immediately decides whether to retain each observed edge. The algorithm's objective is to construct a graph property within specified constraints on the total number of observed edges ("time") and the total number of retained edges ("budget").

During this talk, I will present results in this model for natural graph properties, such as connectivity, Hamiltonicity, and containment of fixed-size subgraphs. Specifically, I will describe a strategy to construct a Hamilton cycle at the hitting time for minimum degree 2 by retaining a linear number of edges. This extends the classical hitting time result for Hamiltonicity originally established by Ajtai–Komlós–Szemerédi and Bollobás.

The talk is based on joint work with Alan Frieze and Michael Krivelevich.

We show that every 2-coloring of the natural numbers and any finite coloring of the rationals contains monochromatic sets of the form $\{x, y, xy, x+y\}$. We also discuss generalizations and obstructions to extending this result to arbitrary finite coloring of the naturals. This is partially based on joint work with Marcin Sabok.

Motivated by the desire to construct large independent sets in random graphs, Karp and Sipser modified the usual greedy construction to yield an algorithm that outputs an independent set with a large cardinal called the Karp-Sipser core. When run on the Erdős-Rényi $G(n,c/n)$ random graph, this algorithm is optimal as long as $c < e$. We will present the proof of a physics conjecture of Bauer and Golinelli (2002) stating that at criticality, the size of the Karp-Sipser core is of order $n^{3/5}$. Along the way we shall highlight the similarities and differences with the usual greedy algorithm and the $k$-core algorithm.
Based on a joint work with Nicolas Curien and Thomas Budzinski.

A $k$-block in a graph is a set of $k$ vertices every two of which are joined by $k$ vertex disjoint paths. By a result of Weissauer, graphs with no $k$-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions for bounded tree width, a lot can be said about graphs with no $k$-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a $k$-block in a graphs. We will discuss this phenomenon and its consequences in the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.

Let $G$ be a $d$-regular graph of growing degree on $n$ vertices, and 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$ being 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 the 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 further give examples demonstrating the tightness of this result in several key senses.

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

A factorisation $x=u_1u_2\cdots$ of an infinite word $x$ on alphabet $X$ is called ‘super-monochromatic’, for a given colouring of the finite words $X^{\ast}$ on alphabet $X$, if each word $u_{k_1}u_{k_2}\cdots u_{k_n}$, where $k_1<\cdots<k_n$, is the same colour. A direct application of Hindman’s theorem shows that if $x$ is eventually periodic, then for every finite colouring of $X^{\ast}$, there exist a suffix of $x$ that admits a super-monochromatic factorisation. What about the converse?

In this talk we show that the converse does indeed hold: thus a word $x$ is eventually periodic if and only if for every finite colouring of $X^{\ast}$ there is a suffix of $x$ having a super-monochromatic factorisation. This has been a conjecture in the community for some time. Our main tool is a Ramsey result about alternating sums. This provides a strong link between Ramsey theory and the combinatorics of infinite words.

Joint work with Imre Leader and Luca Q. Zamboni

In the critical beta-splitting model of a random $n$-leaf rooted tree, clades (subtrees) are recursively split into sub-clades, and a clade of $m$ leaves is split into sub-clades containing $i$ and $m-i$ leaves with probabilities $\propto 1/(i(m-i))$. This model turns out to have interesting properties. There is a canonical embedding into a continuous-time model ($\operatorname{CTCS}(n)$). There is an inductive construction of $\operatorname{CTCS}(n)$ as $n$ increases, analogous to the stick-breaking constructions of the uniform random tree and its limit continuum random tree. We study the heights of leaves and the limit fringe distribution relative to a random leaf. In addition to familiar probabilistic methods, there are analytic methods (developed by co-author Boris Pittel), based on explicit recurrences, which often give more precise results. So this model provides an interesting concrete setting in which to compare and contrast these methods. Many open problems remain.
Preprints at https://arxiv.org/abs/2302.05066 and https://arxiv.org/abs/2303.02529

More than 30 year ago Jerrum studied the planted clique problem and proved that under worst-case initialization Metropolis fails to recover planted cliques of size $\ll n^{1/2}$ in the Erdős-Rényi graph $G(n,1/2)$. This result is classically cited in the literature of the problem, as the "first evidence" that finding planted cliques of size much smaller than square root $n$ is "algorithmically hard". Cliques of size $\gg n^{1/2}$ are easy to find using simple algorithms. In a recent work we show that the Metropolis process actually fails to find planted cliques under worst-case initialization for cliques up to size almost linear in $n$. Thus the algorithm fails well beyond the $\sqrt{n}$ "conjectured algorithmic threshold". We also prove that, for a large parameter regime, that the Metropolis process fails also under "natural initialization". Our results resolve some open questions posed by Jerrum in 1992. Based on joint work with Zongchen Chen and Iias Zadik.

Magnant and Martin conjectured that every $d$-regular graph on $n$ vertices can be covered by $n/(d+1)$ vertex-disjoint paths. Gruslys and Letzter verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all $\alpha>0$, there exists $n_0=n_0(\alpha)$ such that every $d$-regular digraph on $n$ vertices with $d \ge \alpha n $ can be covered by at most $n/(d+1)$ vertex-disjoint cycles. Moreover if $G$ is an oriented graph, then $n/(2d+1)$ cycles suffice. This also establishes Jackson's long standing conjecture for large $n$ that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian.
This is joint work with Viresh Patel and  Mehmet Akif Yıldız.

The speakers are Maya Stein (University of Chile), Mathias Schacht (Hamburg), János Pach (Rényi Institute, Hungary and IST Austria), Marthe Bonamy (Bordeaux), Mehtaab Sawhney (Cambridge/MIT), and Julian Sahasrabudhe (Cambridge). Please see the event website for further details including titles, abstracts, and timings. Anyone interested is welcome to attend, and no registration is required.

Let $p_c$ and $q_c$ be the threshold and the expectation threshold, respectively, of an increasing family $F$ of subsets of a finite set $X$. Recently, Park and Pham proved Kahn–Kalai conjecture stating that a not-too-large multiple of $q_c$ is an upper bound on $p_c$. In the talk, I will present a slight improvement to the Park–Pham theorem, which is obtained from transferring the threshold result from the small $p$ regime to general $p$. Based on joint work with Oliver Riordan.

"Colouring" a tournament means partitioning its vertex set into acylic subsets; and the "domination number" is the size of the smallest set of vertices with no common in-neighbour. In some ways these are like the corresponding concepts for graphs, but in some ways they are very different. We give a survey of some recent results and open questions on these topics.

Joint with Tung Nguyen and Alex Scott.

We determine the minimal forbidden minors characterising the class of countable graphs that embed into some compact surface. We will also discuss Thomas’s conjecture that the Robertson—Seymour Graph Minor Theorem extends to countably infinite graphs. [https://arxiv.org/abs/2301.11042]

A classic result of Chvatál and Erdős (1972) asserts that, if the vertex-connectivity of a graph G is at least as large as its independence number, then G has a Hamilton cycle. We prove a similar result, implying that a graph G is pancyclic, namely it contains cycles of all lengths between 3 and |G|: we show that if |G| is large and the vertex-connectivity of G is larger than its independence number, then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs.

I will discuss statistical inference problems on edge-correlated stochastic block models. We determine the information-theoretic threshold for exact recovery of the latent vertex correspondence between two correlated block models, a task known as graph matching. As an application, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. Furthermore, we obtain the precise threshold for exact community recovery using multiple correlated graphs, which captures the interplay between the community recovery and graph matching tasks. This is based on joint work with Julia Gaudio and Anirudh Sridhar.

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We recently proved a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $2^{c\sqrt{\log |G| \log\log|G|}}$. This talk will outline the proof. Joint work with Matija Bucić, Tung Nguyen and Alex Scott.

Random greedy algorithms became ubiquitous in Combinatorics after Rödl's nibble (semi-random method), which was repeatedly refined for various applications, such as iterative graph colouring algorithms (Molloy-Reed) and lower bounds for the Ramsey number $R(3,t)$ via the triangle-free process (Bohman-Keevash / Fiz Pontiveros-Griffiths-Morris). More recently, when combined with absorption, they have played a key role in many existence and approximate counting results for combinatorial structures, following a paradigm established by my proofs of the Existence of Designs and Wilson's Conjecture on the number of Steiner Triple Systems. Here absorption (converting approximate solutions to exact solutions) is generally the most challenging task, which has spurred the development of many new ideas, including my Randomised Algebraic Construction method, the Kühn-Osthus Iterative Absorption method and Montgomery's Addition Structures (for attacking the Ryser-Brualdi-Stein Conjecture). The design and analysis of a suitable guiding mechanism for the random process can also come with major challenges, such as in the recent proof of Erdős' Conjecture on Steiner Triple Systems of high girth (Kwan-Sah-Sawhney-Simkin). This talk will survey some of this background and also mention some recent results on the Queens Problem (Bowtell-Keevash / Luria-Simkin / Simkin) and the Existence of Subspace Designs (Keevash-Sah-Sawhney). I may also mention recent solutions of the Talagrand / Kahn-Kalai Threshold Conjectures (Frankston-Kahn-Narayanan-Park / Park-Pham) and thresholds for Steiner Triple Systems / Latin Squares (Keevash / Jain-Pham), where the key to my proof is constructing a suitable spread measure via a guided random process.

A regular bipartite tournament is an orientation of a complete balanced bipartite graph $K_{2n,2n}$ where every vertex has its in- and outdegree both equal to $n$. In 1981, Jackson conjectured that any regular bipartite tournament can be decomposed into Hamilton cycles. We prove this conjecture for sufficiently large $n$. Along the way, we also prove several further results, including a conjecture of Liebenau and Pehova on Hamilton decompositions of dense bipartite digraphs.

Let $p \ge 3$ be a prime integer. The density of a non-empty solution set of a system of affine equations $L_i(x) = b_i$, $i=1,\dots,k$ on a vector space over the field $\mathbb{F}_p$ is determined by the dimension of the linear subspace $\langle L_1,\dots,L_k \rangle$, and tends to $0$ with the dimension of that subspace. In particular, if the solution set is dense, then the system of equations contains at most boundedly many pairwise distinct linear forms. In the more general setting of systems of affine conditions $L_i(x) \in E_i$ for some strict subsets $E_i$ of $\mathbb{F}_p$ and where the solution set and its density are taken inside $S^n$ for some non-empty subset $S$ of $\mathbb{F}_p$ (such as $\{0,1\}$), we can however usually find subsets of $S^n$ with density at least $1/2$ but such that the linear subspace $\langle L_1,\dots,L_k \rangle$ has arbitrarily high dimension. We shall nonetheless establish an approximate boundedness result: if the solution set of a system of affine conditions is dense, then it contains the solution set of a system of boundedly many affine conditions and which has approximately the same density as the original solution set. Using a recent generalisation by Gowers and the speaker of a result of Green and Tao on the equidistribution of high-rank polynomials on finite prime fields we shall furthermore prove a weaker analogous result for polynomials of small degree.

Based on joint work with Timothy Gowers (College de France and University of Cambridge).

I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi's theorem and describe a proof of such bounds for sets lacking nontrivial configurations of the form (x,y), (x,y+z), (x,y+2z), (x+z,y) in the finite field model setting.

In this talk, I will review some recent progress on random graph matching problems, that is, to recover the vertex correspondence between a pair of correlated random graphs from the observation of two unlabelled graphs. In this talk, I will touch issues of information threshold, efficient algorithms as well as complexity theory. This is based on joint works with Hang Du, Shuyang Gong and Zhangsong Li.

We present two ways of obtaining hypercontractive inequalities for low-degree functions on compact Lie groups: one based on Ricci curvature bounds, the Bakry-Emery criterion and the representation theory of compact Lie groups, and another based on a (very different) probabilistic coupling approach. As applications we make progress on a question of Gowers concerning product-free subsets of the special unitary groups, and we also obtain 'mixing' inequalities for the special unitary groups, the special orthogonal groups, the spin groups and the compact symplectic groups. We expect that the latter inequalities will have applications in physics.

Based on joint work with Guy Kindler (HUJI), Noam Lifshitz (HUJI) and Dor Minzer (MIT).

The triangle removal lemma of Ruzsa and Szemerédi is a fundamental result in extremal graph theory; very roughly speaking, it says that if a graph is "far" from triangle-free, then it contains "many" triangles. Despite decades of research, there is still a lot that we don't understand about this simple statement; for example, our understanding of the quantitative dependencies is very poor.

In this talk, I will discuss asymmetric versions of the triangle removal lemma, where in some cases we can get almost optimal quantitative bounds. The proofs use a mix of ideas coming from graph theory, number theory, probabilistic combinatorics, and Ramsey theory.

Based on joint work with Lior Gishboliner and Asaf Shapira.

We consider a bond percolation on the hypercube in the supercritical regime. We derive vertex-expansion properties of the giant component. As a consequence we obtain upper bounds on the diameter of the giant component and the mixing time of the lazy random walk on the giant component. This talk is based on joint work with Joshua Erde and Michael Krivelevich.