Workshop

Zoom Link

Zoom Link

I will briefly recall the framework of local weak limits of finite graphs introduced by I. Benjamini and O. Schramm, and then explain how this probabilistic viewpoint allowed me to answer a long-standing open question in discrete geometry (the one in the title), raised by E. Milman, A. Naor and Y. Ollivier.

Zoom Link

We show that the shortest s-t path problem has the overlap-gap property in (i) sparse G(n,p) graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse G(n,p) graphs, shortest path is solved by O(log n)-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem.

This is based on joint work with Tselil Schramm.

Zoom Link

Fast algorithms for recovering a latent community structure from an observed hypergraph are usually based on the spectral decomposition of a matrix associated with the hypergraph. Their statistical accuracy can be evaluated by analysing expected error rates for randomly generated hypergraphs with a given community structure, such as the hypergraph stochastic block model (HSBM). Fast and provably exact community recovery algorithms are usually based on aggregating the observed adjacency tensor into a similarity matrix, the entries of which describe the number of hyperedges indicent to a particular node pair. Unfortunately, the mapping of the adjacency tensor to a similarity matrix loses information, and in some cases this information loss may be statistically significant. Therefore, it still remains unknown whether a fast and exact community recovery algorithm exists in the general setting. Instead of the similarity matrix, an alternative is to apply linear-algebraic techniques to a wide matrix obtained by lossless flattening the adjacency tensor. In this presentation I discuss ongoing research on the analysis of a community recovery algorithm based on flattening the observed hypergraph adjacency tensor. In particular, the approach yields a strongly consistent estimator for recovering communities in d-regular hypergraphs with n >> 1 nodes, for which the average hyperedge density is of order at least n^{-d/2}. In still sparser regimes, community recovery is known to be possible but there are no known fast algorithms. These findings suggest that community recovery from d-uniform hypergraphs with d ≥ 3 may be much harder than what one might expect based on analogous theoretical results for graphs (d=2).

Zoom Link

Spin models on graphs are a source of many interesting questions in statistical physics, algorithms, and combinatorics. The Ising model is a classical example—first introduced as a model of magnetization, it can combinatorially be described as a weighted probability distribution on 2-vertex-colorings of a graph. We’ll consider a fixed-magnetization version of the Ising model—akin to fixing the number of, say, blue vertices in every coloring—and a natural Markov chain sampling algorithm called the Kawasaki dynamics. We show some surprising results regarding the existence and location of a fast/slow mixing threshold for these dynamics. Our proofs require a combination of Markov chain tools, such as path coupling and spectral independence, with combinatorial tools, such as random graph analysis and second moment methods. Joint work with Aiya Kuchukova, Marcus Pappik, and Will Perkins.

Zoom Link

We study the mixing behavior of random walks on Cayley graphs of nilpotent groups, with a focus on their connection to the projected walks on the Abelianizations. For a generating set $S$ of a nilpotent group $G$, we establish that under a degree condition on $|S|$, the spectral gap and the $\varepsilon$-mixing time of the simple random walk $X = (X_t)_{t \geq 0}$ on the corresponding Cayley graph are asymptotically equivalent to those of the projected walk on the Abelianization, represented by $[G,G] X_t$. Consequently, $X$ exhibits cutoff if and only if its projection does. Furthermore, when the generating set $S$ consists of $k$ elements sampled uniformly at random with replacement from $G$, and $1 \ll \log k \ll \log |G|$, we show that the simple random walk on the resulting Cayley graph exhibits cutoff with high probability. The cutoff time, in this case, is determined by the cutoff time of the projected walk on the Abelianization. This work is based on joint research with Jonathan Hermon.

Zoom Link

The family of beta-splitting random trees was introduced by David Aldous in 1993. The tree is a binary tree with a given number of leaves, and is constructed by recursively splitting the set of leaves into two random subsets with sizes having a distribution given by a certain formula including a parameter beta. The "critical" case beta = -1 turns out to be particularly interesting, and it has recently attracted renewed interest by Aldous and others, including myself. I will talk about a few of these results, in particular a representation using exchangeable random partitions of N, and, using this, an analysis of leaf height using Mellin transforms.

(Joint work with David Aldous, see arXiv:2412.09655 and arXiv:2412.12319.)

Zoom Link

We describe large deviations principles for interacting particle systems on sparse graphs, and some consequences.   As an intermediate step we establish a Sanov-type large deviation principle for empirical measures of sparse random graphs with marks in Polish spaces,  yielding a tractable rate function that enables characterization of Gibbs conditioning principles.   This is joint work with I-Hsun Chen, Ivan Lee and Sarath Yasodharan.

Zoom Link

Given a closed set on the plane and two probability distributions on the real line, when are there random variables with the given distributions whose joint distribution is supported by the given set?  We consider both discrete and continuous distributions; in the latter case, the problem is equivalent to asking which sets in the unit square can support a permuton. 

Joint work with Chris Coscia and Martin Tassy.

Zoom Link

A classic problem in probability theory and combinatorics is to estimate the probability that the random graph G(n,p) contains no triangles.  This problem can be viewed as a question in "non-linear large deviations".   The asymptotics of the logarithm of this probability (and related lower tail probabilities) are known in two distinct regimes.  When p>> 1/\sqrt{n}, at this level of accuracy the probability matches that of G(n,p) being bipartite; and when p<< 1/\sqrt{n}, Janson's Inequality gives the asymptotics of the log.  I will discuss a new approach to estimating this probability in the "critical regime": when p = \Theta(1/\sqrt{n}).  The approach uses ideas from statistical physics and algorithms and gives information about the typical structure of graphs drawn from the corresponding conditional distribution.  Based on joint work with Matthew Jenssen, Aditya Potukuchi, and Michael Simkin.  

Zoom Link

In their seminal work, Diaconis and Shahshahani proved that shuffling a deck of $n$ cards sufficiently well via random transpositions takes $1/2 n log n$ steps. Their argument was algebraic and relied on the combinatorics of the symmetric group. In this talk, I will focus on two other shuffles, generalizing random transpositions and I will discuss the underlying combinatorics for understanding their mixing behavior and indeed proving cutoff. The talk will be based on joint works with A. Yan and S. Arfaee.