Past Combinatorial Theory Seminar

Let $X$ and $Y$ be two $n$-vertex graphs. Identify the vertices of $Y$ with $n$ people, any two of whom are either friends or strangers (according to the edges and non-edges in $Y$), and imagine that these people are standing one at each vertex of $X$. At each point in time, two friends standing at adjacent vertices of $X$ may swap places, but two strangers may not. The friends-and-strangers graph $FS(X,Y)$ has as its vertex set the collection of all configurations of people standing on the vertices of $X$, where two configurations are adjacent when they are related via a single friendly swap. This provides a common generalization for the famous 15-puzzle, transposition Cayley graphs of symmetric groups, and early work of Wilson and of Stanley.
I will describe several recent results and open problems addressing the extremal and typical aspects of the notion, focusing on the result that the threshold probability for connectedness of $FS(X,Y)$ for two independent binomial random graphs $X$ and $Y$ in $G(n,p)$ is $p=p(n)=n-1/2+o(1)$.
Joint work with Colin Defant and Noah Kravitz.

I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on odd and even cycles. Erdős and Hajnal asked in 1981 whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases, while, in 1984, Erdős asked whether there is a constant $C$ such that every graph with average degree at least $C$ contains a cycle whose length is a power of 2.

We generalize the fact that all graphs omitting a fixed finite bipartite graph can be uniformly approximated by rectangles (Alon-Fischer-Newman, Lovász-Szegedy), showing that hypergraphs omitting a fixed finite $(k+1)$-partite $(k+1)$-uniform hypergraph can be approximated by $k$-ary cylinder sets. In particular, in the decomposition given by hypergraph regularity one only needs the first $k$ levels: such hypergraphs can be approximated using sets of vertices, sets of pairs, and so on up to sets of $k$-tuples, and on most of the resulting $k$-ary cylinder sets, the density is either close to 0 or close to 1. Moreover, existence of such approximations uniformly under all measures on the vertices is a characterization. Our proof uses a combination of analytic, combinatorial and model-theoretic methods, and involves a certain higher arity generalization of the epsilon-net theorem from VC-theory.  Joint work with Henry Towsner.

The Schmidt subspace theorem is a far-reaching generalization of the Thue-Siegel-Roth theorem in diophantine approximation. In this talk I will give an interpretation of Schmidt's subspace theorem in terms of the dynamics of diagonal flows on homogeneous spaces and describe how the exceptional subspaces arise from certain rational Schubert varieties associated to the family of linear forms through the notion of Harder-Narasimhan filtration and an associated slope formalism. This geometric understanding opens the way to a natural generalization of Schmidt's theorem to the setting of diophantine approximation on submanifolds of $GL_d$, which is our main result. In turn this allows us to recover and generalize the main results of Kleinbock and Margulis regarding diophantine exponents of submanifolds. I will also mention an application to diophantine approximation on Lie groups. Joint work with Nicolas de Saxcé.

This talk will focus on the following two related problems:
    (1) What is the minimum number of edges in a graph containing all $n$-vertex planar graphs as subgraphs? A simple construction of Babai, Erdos, Chung, Graham, and Spencer (1982) has $O(n^{3/2})$ edges, which is the best known upper bound.
    (2) What is the minimum number of *vertices* in a graph containing all $n$-vertex planar graphs as *induced* subgraphs? Here steady progress has been achieved over the years, culminating in a $O(n^{4/3})$ bound due to Bonamy, Gavoille, and Pilipczuk (2019).
    As it turns out, a bound of $n^{1+o(1)}$ can be achieved for each of these two problems. The two constructions are somewhat different but are based on a common technique. In this talk I will first give a gentle introduction to the area and then sketch these constructions. The talk is based on joint works with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.

What is fairness, and to what extent is it practically achievable? I'll talk about a simple mathematical model under which one might hope to understand such questions. Red and blue points occur as independent homogeneous Poisson processes of equal intensity in Euclidean space, and we try to match them to each other. We would like to minimize the sum of a some function (say, a power, $\gamma$) of the distances between matched pairs. This does not make sense, because the sum is infinite, so instead we satisfy ourselves with minimizing *locally*. If the points are interpreted as agents who would like to be matched as close as possible, the parameter $\gamma$ encodes a measure of fairness - large $\gamma$ means that we try to avoid occasional very bad outcomes (long edges), even if that means inconvenience to others - small $\gamma$ means everyone is in it for themselves.
    In dimension 1 we have a reasonably complete picture, with a phase transition at $\gamma=1$. For $\gamma<1$ there is a unique minimal matching, while for $\gamma>1$ there are multiple matchings but no stationary solution. In higher dimensions, even existence is not clear in all cases.

A spanning tree of $G$ is a subgraph of $G$ with the same vertex set as $G$ that is a tree. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in random $k$-regular graphs, showing that the number of spanning trees $\kappa_1(G_n)$ in a random $k$-regular graph on $n$ vertices satisfies $\lim_{n \to \infty} (\kappa_1(G_n))^{1/n} = c_{1,k}$ in probability, where $c_{1,k} = (k-1)^{k-1} (k^2-2k)^{-(k-2)/2}$.

In this talk we will discuss a high-dimensional of the matching model for simplicial complexes, known as random Steiner complexes. In particular, we will prove a high-dimensional counterpart of McKay's result and discuss the local limit of such random complexes. 
Based on a joint work with Lior Tenenbaum. 

We study the minimum total weight of a disk triangulation using any number of vertices out of $\{1,..,n\}$ where the boundary is fixed and the $n \choose 3$ triangles have independent rate-1 exponential weights. We show that, with high probability, the minimum weight is equal to $(c+o(1))n-1/2\log n$ for an explicit constant $c$. Further, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle $(123)$ are both attained by the minimum weight disk triangulation. We will discuss a related open problem concerning simple-connectivity of random simplicial complexes, where a similar phenomenon is conjectured to hold. Based on joint works with Itai Benjamini, Eyal Lubetzky, and Zur Luria.

In long-range percolation on $\mathbb{Z}^d$, each potential edge $\{x,y\}$ is included independently at random with probability roughly $\beta\|x-y\|-d-\alpha$, where $\alpha > 0$ controls how long-range the model is and $\beta > 0$ is an intensity parameter. The smaller $\alpha$ is, the easier it is for very long edges to appear. We are normally interested in fixing $\alpha$ and studying the phase transition that occurs as $\beta$ is increased and an infinite cluster emerges. Perhaps surprisingly, the phase transition for long-range percolation is much better understood than that of nearest neighbour percolation, at least when $\alpha$ is small: It is a theorem of Noam Berger that if $\alpha < d$ then the phase transition is continuous, meaning that there are no infinite clusters at the critical value of $\beta$. (Proving the analogous result for nearest neighbour percolation is a notorious open problem!) In my talk I will describe a new, quantitative proof of Berger's theorem that yields power-law upper bounds on the distribution of the cluster of the origin at criticality.
    As a part of this proof, I will describe a new universal inequality stating that on any graph, the maximum size of a percolation cluster is of the same order as its median with high probability. This inequality can also be used to give streamlined new proofs of various classical results on e.g. Erdős-Rényi random graphs, which I will hopefully have time to talk a little bit about also.

I will present work in progress with D. Gayet and F. Pouran (Grenoble) to establish Russo-Seymour-Welsh (RSW) estimates for 2d statistical mechanics models that do not satisfy the FKG inequality. RSW states that critical percolation has no characteristic length, in the sense that large rectangles are crossed by an open path with a probability that is bounded below by a function of their shape, but uniformly in their size; this ensures the polynomial decay of many relevant quantities and opens the way to deeper understanding of the critical features of the model. All the standard proofs of RSW rely on the FKG inequality, i.e. on the positive correlation between increasing events; we establish the stability of RSW under small perturbations that do not preserve FKG, which extends it for instance to the high-temperature anti-ferromagnetic Ising model.

A connected matching is a matching contained in a connected component. A well-known method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs.
    
I will describe Łuczak's reduction, introduce the new reduction, and mention potential applications of the improved method.

Let $X$ be a random variable, taking values in $\{1,…,n\}$, with standard deviation $\sigma$ and let $f_X$ be its probability generating function. Pemantle conjectured that if $\sigma$ is large and $f_X$ has no roots close to 1 in the complex plane then $X$ must approximate a normal distribution. In this talk, I will discuss a complete resolution of Pemantle's conjecture. As an application, we resolve a conjecture of Ghosh, Liggett and Pemantle by proving a multivariate central limit theorem for, so called, strong Rayleigh distributions. I will also discuss how these sorts of results shed light on random variables that arise naturally in combinatorial settings. This talk is based on joint work with Marcus Michelen.

In 1943, Hadwiger conjectured that every graph with no Kt minor is $(t-1)$-colorable for every $t\geq 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t(\log t)^{1/2})$ and hence is $O(t(\log t)^{1/2)}$-colorable. Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^\beta)$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t(\log t)^{1/2})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^\beta)$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^6)$-colorable.

We will be interested in the structure of random typical minimal factorizations of the n-cycle into transpositions, which are factorizations of $(1,\ldots,n)$ as a product of $n-1$ transpositions. We shall establish a phase transition when a certain amount of transpositions have been read one after the other. One of the main tools is a limit theorem for two-type Bienaymé-Galton-Watson trees conditioned on having given numbers of vertices of both types, which is of independent interest. This is joint work with Valentin Féray.

Let $r>3$ be an integer and consider the following game on the complete graph $K_n$ for $n$ a multiple of $r$: Two players, Maker and Breaker, alternately claim previously unclaimed edges of $K_n$ such that in each turn Maker claims one and Breaker claims $b$ edges. Maker wins if her graph contains a $K_r$-factor, that is a collection of $n/r$ vertex-disjoint copies of $K_r$, and Breaker wins otherwise. In other words, we consider the $b$-biased $K_r$-factor Maker-Breaker game. We show that the threshold bias for this game is of order $n^2/(r+2)$. This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen, Böttcher, Kohayakawa, Naves and Person who resolved the case $r=3$ or $4$ up to a logarithmic factor.
    Joint work with Rajko Nenadov.

I will introduce recent work on the two- and three-dimensional uniform spanning trees (USTs) that establish the laws of these random objects converge under rescaling in a space whose elements are measured, rooted real trees, continuously embedded into Euclidean space. (In the three-dimensional case, the scaling result is currently only known along a particular scaling sequence.) I will also discuss various properties of the intrinsic metrics and measures of the limiting spaces, including their Hausdorff dimension, as well as the scaling limits of the random walks on the two- and three-dimensional USTs. In the talk, I will attempt to emphasise where the differences lie between the two cases, and in particular the additional challenges that arise when it comes to the three-dimensional model.
    The two-dimensional results are joint with Martin Barlow (UBC) and Takashi Kumagai (Kyoto). The three-dimensional results are joint with Omer Angel (UBC) and Sarai Hernandez-Torres (UBC).

A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property $H$, the speed of $H$ is the function which sends an integer n to the number of distinct elements in $H$ with underlying set $\{1,...,n\}$. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete "jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollobás, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.

Let $G_n$ be a sequence of finite, simple, connected, regular graphs with degrees tending to infinity and let $T_n$ be a uniformly drawn spanning tree of $G_n$. In joint work with Yuval Peres we show that the local limit of $T_n$ is the $\text{Poisson}(1)$ branching process conditioned to survive forever (that is, the asymptotic frequency of the appearance of any small subtree is given by the branching process). The proof is based on electric network theory and I hope to show most of it.

Liouville quantum gravity (LQG) is a theory of random fractal surfaces with origin in the physics literature in the 1980s. Most literature is about LQG with matter central charge $c\in (-\infty,1]$. We study a discretization of LQG which makes sense for all $c\in (-\infty,25)$. Based on a joint work with Gwynne, Pfeffer, and Remy.

There is a growing body of results in extremal combinatorics and Ramsey theory which give better bounds or stronger conclusions under the additional assumption of bounded VC-dimension. Schur and Erdős conjectured that there exists a suitable constant $c$ with the property that every graph with at least $2^{cm}$ vertices, whose edges are colored by $m$ colors, contains a monochromatic triangle. We prove this conjecture for edge-colored graphs such that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension. This result is best possible up to the value of $c$.
    Joint work with Jacob Fox and Andrew Suk.

Ideas from physics have predicted a number of important properties of random constraint satisfaction problems such as the satisfiability threshold and the free energy (the exponential growth rate of the number of solutions). Another prediction is the condensation regime where most of the solutions are contained in a small number of clusters and the overlap of two random solutions is concentrated on two points. We establish this phenomena in the random regular NAESAT model. Joint work with Danny Nam and Youngtak Sohn.

What is the connection between phase transitions in statistical physics and the computational tractability of approximate counting and sampling? There are many fascinating answers to this question but many mysteries remain. I will discuss one particular type of a phase transition: the first-order phase in the Potts model on $\mathbb{Z}^d$ for large $q$, and show how tools used to analyze the phase transition can be turned into efficient algorithms at the critical temperature. In the other direction, I'll discuss how the algorithmic perspective can help us understand phase transitions.

Active matter describes ensembles of self-organizing agents, or particles, interacting with their local environments so that their micro-scale behavior determines macro-scale characteristics of the ensemble. While there has been a surge of activity exploring the physics underlying such systems, less attention has been paid to questions of how to program them to achieve desired outcomes. We will present some recent results designing programmable active matter for specific tasks, including aggregation, dispersion, speciation, and locomotion, building on insights from stochastic algorithms and statistical physics.

Let $X_1, \ldots$ be i.i.d. copies of some real random variable $X$. For any $\varepsilon_2, \varepsilon_3, \ldots$ in $\{0,1\}$, a basic algorithm introduced by H.A. Simon yields a reinforced sequence $\hat{X}_1, \hat{X}_2, \ldots$ as follows. If $\varepsilon_n=0$, then $\hat{X}_n$ is a uniform random sample from $\hat{X}_1, …, \hat{X}_{n-1}$; otherwise $\hat{X}_n$ is a new independent copy of $X$. The purpose of this talk is to compare the scaling exponent of the usual random walk $S(n)=X_1 +\ldots + X_n$ with that of its step reinforced version $\hat{S}(n)=\hat{X}_1+\ldots + \hat{X}_n$. Depending on the tail of $X$ and on asymptotic behavior of the sequence $\varepsilon_j$, we show that step reinforcement may speed up the walk, or at the contrary slow it down, or also does not affect the scaling exponent at all. Our motivation partly stems from the study of random walks with memory, notably the so-called elephant random walk and its variations.

We say that a graph $G$ is $H$-free if $G$ does not contain $H$ as a (not necessarily induced) subgraph. For a positive integer $n$, denote by $\text{ex}(n,H)$ the largest number of edges in an $H$-free graph with $n$ vertices (the Turán number of $H$). The classical theorem of Erdős, Kleitman, and Rothschild states that, for every $r\geq3$, there are $2^{\text{ex}(n,H)+o(n2)}$ many $K_r$-free graphs with vertex set $\{1,…, n\}$. There exist (at least) three different derivations of this estimate in the literature: an inductive argument based on the Kővári-Sós-Turán theorem (and its generalisation to hypergraphs due to Erdős), a proof based on Szemerédi's regularity lemma, and an argument based on the hypergraph container theorems. In this talk, we present yet another proof of this bound that exploits connections between entropy and independence. This argument is an adaptation of a method developed in a joint work with Gady Kozma, Tom Meyerovitch, and Ron Peled that studied random metric spaces.