Past Combinatorial Theory Seminar

We introduce a new method for studying stochastic processes in random graphs controlled by degree information, involving combining enumeration techniques with an abstract second moment argument. We use it to constructively resolve a conjecture of Füredi from 1988: with high probability, the random graph G(n,1/2) admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which n-o(n) vertices have at least as many neighbours in their own part as across. This work is joint with Asaf Ferber, Matthew Kwan, Bhargav Narayanan, and Mehtaab Sawhney.

I'll consider recent results concerning the stability of the classic Brunn-Minkowski inequality. In particular, I will focus on the linear stability for homothetic sets. Resolving a conjecture of Figalli and Jerison, we showed there are constants $C,d>0$ depending only on $n$ such that for every subset $A$ of $\mathbb{R}^n$ of positive measure, if $|(A+A)/2 - A| \leq d |A|$, then $|co(A) - A| \leq C |(A+A)/2 - A|$ where $co(A)$ is the convex hull of $A$. The talk is based on joint work with Hunter Spink and Marius Tiba.

Suppose there are $n$ students in a class. But assume that not everybody is friends with everyone else, and there is a graph which determines the friendship structure. What is the chance that there are two friends in this class, both with birthdays on October 12? More generally, given a simple labelled graph $G_n$ on $n$ vertices, color each vertex with one of $c=c_n$ colors chosen uniformly at random, independent from other vertices. We study the question: what is the number of monochromatic edges of color 1?

As it turns out, the limiting distribution has three parts, the first and second of which are quadratic and linear functions of a homogeneous Poisson point process, and the third component is an independent Poisson. In fact, we show that any distribution limit must belong to the closure of this class of random variables. As an application, we characterize exactly when the limiting distribution is a Poisson random variable.

This talk is based on joint work with Bhaswar Bhattacharya and Somabha Mukherjee.

This is joint work with Paul Bourgade and Benjamin McKenna (Courant Institute, NYU).
The elastic manifold is a paradigmatic representative of the class of disordered elastic systems. These models describe random surfaces with rugged shapes resulting from a competition between random spatial impurities (preferring disordered configurations), on the one hand, and elastic self-interactions (preferring ordered configurations), on the other. The elastic manifold model is interesting because it displays a depinning phase transition and has a long history as a testing ground for new approaches in statistical physics of disordered media, for example for fixed dimension by Fisher (1986) using functional renormalization group methods, and in the high-dimensional limit by Mézard and Parisi (1992) using the replica method.
We study the topology of the energy landscape of this model in the Mézard-Parisi setting, and compute the (annealed) topological complexity both of total critical points and of local minima. Our main result confirms the recent formulas by Fyodorov and Le Doussal (2020) and allows to identify the boundary between simple and glassy phases. The core argument relies on the analysis of the asymptotic behavior of large random determinants in the exponential scale.

Consider an $n$ by $n$ random matrix $A$ with i.i.d entries. In this talk, we discuss some results on the magnitude of the smallest singular value of $A$, and, in particular, the problem of estimating the singularity probability when the entries of $A$ are discrete.

We study the set $L(G)$ of cycle lengths that appear in a sparse binomial random graph $G(n,c/n)$ and in a random $d$-regular graph $G_{n,d}$. We show in particular that for most values of $c$, for $G$ drawn from $G(n,c/n)$ the set $L(G)$ contains typically an interval $[\omega(1), (1-o(1))L_{\max}(G)]$, where $L_{\max}(G)$ is the length of a longest cycle (the circumference) of $G$. For the case of random $d$-regular graphs, $d\geq 3$ fixed, we obtain an accurate asymptotic estimate for the probability of $L(G)$ to contain a full interval $[k,n]$ for a fixed $k\geq 3$. Similar results are obtained also for the supercritical case $G(n,(1+\epsilon)/n)$, and for random directed graphs.
A joint work with Yahav Alon and Eyal Lubetzky.

Percolation models were originally introduced to describe the propagation of a fluid in a random medium. In dimension two, the percolation properties of a model are encoded by so-called crossing probabilities (probabilities that certain rectangles are crossed from left to right). In the eighties, Russo, Seymour and Welsh obtained general bounds on crossing probabilities for Bernoulli percolation (the most studied percolation model, where edges of a lattice are independently erased with some given probability $1-p$). These inequalities rapidly became central tools to analyze the critical behavior of the model.
In this talk I will present a new result which extends the Russo-Seymour-Welsh theory to general percolation measures satisfying two properties: symmetry and positive correlation. This is a joint work with Laurin Köhler-Schindler.

We study the model of randomly perturbed dense graphs, which is the union of any $n$-vertex graph $G_\alpha$ with minimum degree at least $\alpha n$ and the binomial random graph $G(n,p)$. In this talk, we shall examine the following central question in this area: to determine when $G_\alpha \cup G(n,p)$ contains $H$-factors, i.e. spanning subgraphs consisting of vertex disjoint copies of the graph $H$. We offer several new sharp and stability results.
This is joint work with Julia Böttcher, Olaf Parczyk, and Jozef Skokan.

In this talk we will discuss some classical and recent results on local limits of random graphs. It is well known that the limiting object of the local structure of the classical Erdos-Renyi random graph is a Galton-Watson tree. This can nicely be formalised in the language of Benjamini-Schramm or Aldous-Steele local weak convergence. Regarding local limits of sparse random planar graphs, there is a smooth transition from a Galton-Watson tree to a Skeleton tree. This talk is based on joint work with Michael Missethan.

We present an exponential improvement to the lower bound on diagonal Ramsey numbers for any fixed number of colors greater than two.
This is a joint work with David Conlon.
 

How does a colony of ants find the shortest path between its nest and a source of food without any means of communication other than the pheromones each ant leave behind itself?
In this joint work with Daniel Kious (Bath) and Bruno Schapira (Marseille), we introduce a new probabilistic model for this phenomenon. In this model, the nest and the source of food are two marked nodes in a finite graph. Ants perform successive random walks from the nest to the food, and the distribution of the $n$th walk depends on the trajectories of the $(n-1)$ previous walks through some linear reinforcement mechanism.
Using stochastic approximation methods, couplings with Pólya urns, and the electric conductances method for random walks on graphs (which I will explain on some simple examples), we prove that, depending on the exact reinforcement rule, the ants may or may not always find the shortest path(s) between their nest and the source food.

We discuss the behavior of geodesics in the continuous models of random geometry known as the Brownian map and the Brownian plane. We say that a point $x$ is a geodesic star with $m$ arms if $x$ is the endpoint of $m$ disjoint geodesics. We prove that the set of all geodesic stars with $m$ arms has dimension $5-m$, for $m=1,2,3,4$. This complements recents results of Miller and Qian, who derived upper bounds for these dimensions.

How much does the chromatic number of the random graph $G(n, 1/2)$ vary? Shamir and Spencer proved that it is contained in some sequence of intervals of length about $n^{1/2}$. Alon improved this slightly to $n^{1/2} / \log n$. Until recently, however, no lower bounds on the fluctuations of the chromatic number of $G(n, 1/2)$ were known, even though the question was raised by Bollobás many years ago. I will talk about the main ideas needed to prove that, at least for infinitely many $n$, the chromatic number of $G(n, 1/2)$ is not concentrated on fewer than $n^{1/2-o(1)}$ consecutive values.
I will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between $n^{1/4+o(1)}$ and $n^{1/2+o(1)}$, depending on $n$.
Joint work with Oliver Riordan.

The title of the talk corresponds to a family of interesting random processes, which includes lazy random walks on graphs and much beyond them. Often, a key step in analysing such processes is to estimate their spectral gaps (ie. the difference between two largest eigenvalues). It is thus of interest to understand what else about the chain we can know from the spectral gap. We will present a simple comparison idea that often gives us the best possible estimates. In particular, we re-obtain and improve upon several known results on hitting, meeting, and intersection times; return probabilities; and concentration inequalities for time averages. We then specialize to the graph setting, and obtain sharp inequalities in that setting. This talk is based on work that has been in progress for far too long with Yuval Peres.

In this talk we will consider the extremal values of the stationary distribution of the sparse directed configuration model. Under the assumption of linear $(2+\eta)$-moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have power-law behavior, we show that the upper tail of the stationary distribution also has power-law behavior with the same index. Moreover, these results extend to the PageRank scores of the model, thus confirming a version of the so-called power-law hypothesis. Joint work with Xing Shi Cai, Pietro Caputo and Matteo Quattropani.

The classical Turán problem asks: given a graph $H$, how many edges can an $4n$-vertex graph have while containing no isomorphic copy of $H$? By viewing $(k+1)$-uniform hypergraphs as $k$-dimensional simplicial complexes, we can ask a topological version (first posed by Nati Linial): given a $k$-dimensional simplicial complex $S$, how many facets can an $n$-vertex $k$-dimensional simplicial complex have while containing no homeomorphic copy of $S$? Until recently, little was known for $k > 2$. In this talk, we give an answer for general $k$, by way of dependent random choice and the combinatorial notion of a trace-bounded hypergraph. Joint work with Jason Long and Bhargav Narayanan.

Self-similar fragmentation processes are random models for particles that are subject to successive fragmentations. When the index of self-similarity is negative the fragmentations intensify as the masses of particles decrease. This leads to a shattering phenomenon, where the initial particle is entirely reduced to dust - a set of zero-mass particles - in finite time which is what we call the extinction time. Equivalently, these extinction times may be seen as heights of continuous compact rooted trees or scaling limits of heights of sequences of discrete trees. Our objective is to set up precise bounds for the large time asymptotics of the tail distributions of these extinction times.

A uniform spanning tree of $\mathbb{Z}^4$ can be thought of as the "uniform measure" on trees of $\mathbb{Z}^4$. The past of 0 in the uniform spanning tree is the finite component that is disconnected from infinity when 0 is deleted from the tree. We establish the logarithmic corrections to the probabilities that the past contains a path of length $n$, that it has volume at least $n$ and that it reaches the boundary of the box of side length $n$ around 0. Dimension 4 is the upper critical dimension for this model in the sense that in higher dimensions it exhibits "mean-field" critical behaviour. An important part of our proof is the study of the Newtonian capacity of a loop erased random walk in 4 dimensions. This is joint work with Tom Hutchcroft.

We prove that bounded-degree expanders with non-negative Ollivier-Ricci curvature do not exist, thereby solving a long-standing open problem suggested by Naor and Milman and publicized by Ollivier (2010). In fact, this remains true even if we allow for a vanishing proportion of large degrees, large eigenvalues, and negatively-curved edges. To establish this, we work directly at the level of Benjamini-Schramm limits. More precisely, we exploit the entropic characterization of the Liouville property on stationary random graphs to show that non-negative curvature and spectral expansion are incompatible 'at infinity'. We then transfer this result to finite graphs via local weak convergence and a relative compactness argument. We believe that this 'local weak limit' approach to mixing properties of Markov chains will have many other applications.

It is a basic fact of convexity that the volume of convex bodies is a polynomial, whose coefficients contain many familiar geometric parameters as special cases. A fundamental result of convex geometry, the Alexandrov-Fenchel inequality, states that these coefficients are log-concave. This proves to have striking connections with other areas of mathematics: for example, the appearance of log-concave sequences in many combinatorial problems may be understood as a consequence of the Alexandrov-Fenchel inequality and its algebraic analogues.

There is a long-standing problem surrounding the Alexandrov-Fenchel inequality that has remained open since the original works of Minkowski (1903) and Alexandrov (1937): in what cases is equality attained? In convexity, this question corresponds to the solution of certain unusual isoperimetric problems, whose extremal bodies turn out to be numerous and strikingly bizarre. In combinatorics, an answer to this question would provide nontrivial information on the type of log-concave sequences that can arise in combinatorial applications. In recent work with Y. Shenfeld, we succeeded to settle the equality cases completely in the setting of convex polytopes. I will aim to describe this result, and to illustrate its potential combinatorial implications through a question of Stanley on the combinatorics of partially ordered sets.

We investigate a graph theoretic analog of geodesic geometry. In a graph $G=(V,E)$ we consider a system of paths $P=\{P_{u,v}| u,v\in V\}$ where $P_{u,v}$ connects vertices $u$ and $v$. This system is consistent in that if vertices $y,z$ are in $P_{u,v}$, then the sub-path of $P_{u,v}$ between them coincides with $P_{y,z}$. A map $w:E\to(0,\infty)$ is said to induce $P$ if for every $u,v\in V$ the path $P_{u,v}$ is $w$-geodesic. We say that $G$ is metrizable if every consistent path system is induced by some such $w$. As we show, metrizable graphs are very rare, whereas there exist infinitely many 2-connected metrizable graphs.
 

I will introduce product structure theory of graphs and show how families of graphs that have such a structure admit short adjacency labeling scheme and small induced universal graphs. Time permitting, I will talk about another recent application of product structure theory, namely vertex ranking (coloring).

We consider the random directed graph $D(n,p)$ with vertex set $\{1,2,…,n\}$ in which each of the $n(n-1)$ possible directed edges is present independently with probability $p$. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at $p = 1/n$, with critical window $p = 1/n + \lambda n-4/3$ for $\lambda \in \mathbb{R}$. We show that, within this critical window, the strongly connected components of $D(n,p)$, ranked in decreasing order of size and rescaled by $n-1/3$, converge in distribution to a sequence $(C_1,C_2,\ldots)$ of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs in the sense of an $L^1$ sequence metric for which two directed multigraphs are close if there are compatible isomorphisms between their vertex and edge sets which roughly preserve the edge lengths. Our proofs rely on a depth-first exploration of the graph which enables us to relate the strongly connected components to a particular spanning forest of the undirected Erdős-Rényi random graph $G(n,p)$, whose scaling limit is well understood. We show that the limiting sequence $(C_1,C_2,\ldots)$ contains only finitely many components which are not loops. If we ignore the edge lengths, any fixed finite sequence of 3-regular strongly connected directed multigraphs occurs with positive probability.

The dimer model, a classical model of statistical mechanics, is the uniform distribution on perfect matchings of a graph. In two dimensions, one can define an associated height function which turns the model into a random surface (with specified boundary conditions). In the 1960s, Kasteleyn and Temperley/Fisher found an exact "solution" to the model, computing the correlations in terms of a matrix called the Kasteleyn matrix. This exact solvability was the starting point for the breakthrough work of Kenyon (2000) who proved that the centred height function converges to the Dirichlet (or zero boundary conditions) Gaussian free field. This was the first proof of conformal invariance in statistical mechanics.

In this talk, I will focus on a natural modification of the model where one allows the vertices on the boundary of the graph to remain unmatched: this is the so-called monomer-dimer model, or dimer model with free boundary conditions. The main result that we obtain is that the scaling limit of the height function of the monomer-dimer model in the upper half-plane is the Neumann (or free boundary conditions) Gaussian free field. Key to this result is a somewhat miraculous random walk representation for the inverse Kasteleyn matrix, which I hope to discuss.

Joint work with Marcin Lis (Vienna) and Wei Qian (Paris).

It is sometimes possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope $P$ is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which $P$ can be obtained as a (linear) projection. In this talk, we discuss some results on the extension complexity of random $d$-dimensional polytopes (obtained as convex hulls of random points on either on the unit sphere or in the unit ball), and on the extension complexity of polygons with all vertices on a common circle. Joint work with Matthew Kwan and Yufei Zhao