Combinatorial Theory Seminar

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 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.

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.

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).

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

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.