Abstract

We describe some recently discovered connections between one-dimensional interacting particle models and Macdonald polynomials and show the combinatorial objects that make this connection explicit. The first such model is the multispecies asymmetric simple exclusion process (ASEP) on a ring, linked to the symmetric Macdonald polynomials P_\lambda through its partition function, with multiline queues as the corresponding combinatorial object. The second particle model is the multispecies totally asymmetric zero range process (TAZRP) on a ring, which was recently found to have an analogous connection to the modified Macdonald polynomial H_\lambda. The combinatorial objects interpolating between probabilities of the TAZRP and the modified Macdonald polynomials turn out to be tableaux with a queue inversion statistic. We explain the plethystic relationship between multiline queues and queue inversion tableaux, and along the way, derive a new formula for P_\lambda using the queue inversion statistic. This plethystic correspondence is closely related to fusion in the setting of integrable systems.

• Video

Abstract

A dimer tiling of Z^d is a collection of edges such that every vertex is covered exactly once. Given a compact region R in R^d, consider regions R_n in (1/n) Z^d which approximate R (and some boundary condition). What do random dimer tilings of R_n look like for large n? The 2D version of this question was answered by Cohn, Kenyon, and Propp in 2000. I will talk about how to answer this question in 3D. In both cases, it turns out that a random tiling of R_n is exponentially more likely to lie close to a fixed ""limit shape"" (and more generally, there is a large deviation principle, meaning the probability of lying close to any possible limiting configuration is given by a function called the ""rate function""). While the results are analogous, I will explain that the methods of proof are very different, because many of the key tools for studying dimers are special to two dimensions. This talk is based on https://arxiv.org/abs/2304.08468, which is joint work with Nishant Chandgotia and Scott Sheffield.

Abstract

The dimer model studies a natural probability measure on the space of perfect matching (""dimer covers"") of an edge-weighted graph; the probability of a dimer cover is proportional to the product of its edge weights. When the graph is bipartite, a useful change in viewpoint is to view the edge weights as defining a ""C∗ local system"", that is a line bundle with connection. This leads us to consider natural generalizations using higher-rank bundles, in particular SLn -local systems. We will talk about a collection of results with emphasis on calculating connection probabilities in double and triple dimer models.

Abstract

One of the best-known planar diagram algebras is the Temperley-Lieb algebra. This algebra is defined combinatorially using non-intersecting matchings and can be realized as a centralizer of Lie algebras (or quantum groups) acting on tensor space. They have a wide range of applications, most notably to knot theory and statistical mechanics. The partition algebra is a generalization of the Temperley-Lieb algebra which was proposed by Martin to study higher dimensional statistical models. In this talk I will discuss planar subalgebras of the partition algebras related to the Temperley-Lieb algebra. This is joint work with N. Wallace and M. Zabrocki.

Abstract

We discuss large permutations with restricted permutation matrices, that is, whose permutation matrix has no 1s in some region. We give enumerative results and limit shapes.

• Video

Abstract

We establish a large deviation principle in a strong topology for the component empirical measure of several sequences of marked random graph models, including Erdos-Renyi random graphs, random regular graphs, and more general configuration models. We show that the corresponding rate function is given by a relatively tractable formula involving the relative entropy functional. We also describe several applications of this result, such as Gibbs conditioning principles. This talk is based on joint work with I-Hsun Chen and Sarath Yasodharan.

• Video

Abstract

Permutation limit theory arises by viewing a permutation as a probability measure on the unit square, and is motivated by dense graph limit theory. Using the theory of permutation limits (permutons), we can compute limiting properties of various permutation statistics for random permutations, such as number of fixed points, number of small cycles, pattern counts, and degree distribution of permutation graphs. We can also derive LDPs for random permutations. Our results apply to many non uniform distributions on permutations, including the the celebrated Mallows model, and mu-random permutations. This is based on joint work with Bhaswar Bhattacharya, Jacopo Borga, Sayan Das and Peter Winkler.

• Video
• Slides

Abstract

Motifs (patterns of subgraphs), such as edges and triangles, encode important structural information about the geometry of a network. Consequently, counting motifs in a large network is an important statistical and computational problem. In this talk we will consider the problem of estimating motif densities and fluctuations of subgraph counts in an inhomogeneous random graph sampled from a graphon. We will show that the limiting distributions of subgraph counts can be Gaussian or non-Gaussian, depending on a notion of regularity of subgraphs with respect to the graphon. Using these results and a novel multiplier bootstrap for graphons, we will construct confidence intervals for the motif densities. We will also present parallel results for patterns in random permutations through the lens of permuton theory. Finally, we will discuss various structure theorems and open questions about degeneracies of the limiting distribution.

• Video

• Slides

Abstract

The workshop will continue in an optional evening session, where we will make a plan for a course that fits the most populations of those attending the evening session. We will look over some existing materials, plan a shared materials archive, and discuss some of the more crucial mechanics of active classrooms.

Abstract

The Airy line ensemble was introduced by Prähofer and Spohn and is conjectured to describe the scaling limit of various random surfaces and stochastic growth models in the Kardar–Parisi–Zhang universality class. In this talk I will discuss a characterization result for Airy line ensembles, essentially indicating that if the top curve of a Brownian line ensemble is within a multiplicative 1+o(1) from a parabola, then it must be the Airy line ensemble (up to an affine shift). This is a joint work with Amol Aggarwal.

Abstract

The study of structures in large random graphs has been a central direction in probabilistic combinatorics. In this talk, I will survey several recent developments in this front with interesting connections. Certain important aspects in the study of structures in random graphs can be phrased in terms of thresholds — the density locations at which a structure emerges. In joint work with Jinyoung Park, building on connections to our resolution of a conjecture of Talagrand on the behavior of random linear programs under combinatorial constraints, we prove the long-standing Kahn-Kalai conjecture, that thresholds of general monotone properties are closely predicted by expectation obstructions. The Kahn-Kalai conjecture is a beautiful milestone towards the understanding of emergence of general structures, and yet to complete the quest, it remains to study these expectation obstructions. This latter task can prove to be highly challenging in several cases and bring in interesting connections to structural results. As an illustration, I will discuss joint work with Ashwin Sah, Mehtaab Sawhney and Michael Simkin on enumerating and determining the threshold of clique factors and bounded degree spanning trees in random subgraphs of graphs with high minimum degree. Our proof crucially builds on the regularity method and embedding techniques, which are seminal cornerstones of modern combinatorics. Switching from independent Erdos-Renyi random graphs to structured ensembles with dependency introduces significant challenges. I will discuss this challenge in the context of random Cayley subgraphs of general groups. Given a fixed finite group, random Cayley graphs are constructed by choosing the generating set at random. These graphs thus reflect interesting symmetries and properties of the group, at the cost of inducing complex dependencies. I will discuss results on clique and independence numbers in random Cayley graphs of general groups, as well as progress towards a conjecture of Alon on Cayley graphs with small clique and independence number. These questions are naturally connected with some fundamental problems in additive combinatorics, which we address using both group theoretic and purely combinatorial perspectives. This is based on joint work with David Conlon, Jacob Fox and Liana Yepremyan.

• Video

Abstract

We discuss two questions for random walks on finite graphs that are motivated by an old conjecture of Benjamini, Schramm, and me and an old question of Fontes and Mathieu. These old questions concern random walks on infinite Cayley graphs, the first involving also percolation and the second involving random environments. We try to attack them via questions on finite graphs without any group structure.

• Slides