Schedule for: 21w5511 - Permutations and Probability

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Random tiling models and other stat mech models like the Potts model on a graph G become tractable in a certain limit of “blow up”s G_N, where each vertex of G is replaced with N vertices and each edge with K_{N,N}. We give exact enumerations, free energy, phase transitions, conformal invariance properties for these models. This is joint work with Cosmin Pohoata.

Inspired by the work of Hopkins, McConville and Propp (Elec. J. Comb., 2017) on sorting using toppling, we say that a permutation is toppleable if it gets sorted by a certain sequence of toppling moves. For the most part of the talk, I will focus on joint work with D. Hathcock and P. Tetali (arXiv:2010.11236) where we show that the number of toppleable permutations on n letters is the same as those for which excedances happen exactly at {1, \dots, [(n-1)/2]} (an excedance of a permutation pi is a position i such that pi_i > i), which is also the number of acyclic orientations with unique sink of the complete bipartite graph K_{[n/2], [n/2] + 1}. Time permitting, I will mention generalizations of these results joint with B. Bényi (arXiv:2104.13654) where we are able to completely classify permutations resulting from the toppling process and enumerate permutations toppling to them.

I will present new, non-asymptotic bounds on the heights of random combinatorial trees and conditioned Bienaymé trees, as well as stochastic inequalities relating the heights of combinatorial trees with different degree sequences. The tool for all the proofs is a new approach to coding rooted trees by sequences.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet at the Front Desk of PDC for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We establish a quantitative criterion for an operator defined on a Galton-Watson random tree for having an absolutely continuous spectrum. For the adjacency operator, this criterion requires that the offspring distribution has a relative variance below a threshold. As a by-product, we prove that the adjacency operator of a supercritical Poisson Galton-Watson tree has a non-trivial absolutely continuous part if the average degree is large enough. We also prove that its Karp and Sipser core has purely absolutely spectrum on an interval if the average degree is large enough. We finally illustrate our criterion on the Anderson model on a regular infinite tree and give a quantitative version of Klein's Theorem on the existence of an absolutely continuous part. These results find applications on the delocalization of eigenvectors of sparse random graphs. This is a joint work with Adam Arras (Aix-Marseille University).

We study random reduced walks in affine Weyl groups of types B, C and D. These walks almost surely approaches one of finitely many directions each corresponding to a signed permutation. We compute the exact directions for a natural set of parameters called Kac labels as weights for the walk. This settles a question by Thomas Lam, for types B and C in the affirmative and for type D in the negative. The main tool is a combinatorial two row model for a totally asymmetric simple exclusion process called the D∗-TASEP, with four parameters. By specializing the parameters in different ways, we obtain TASEPs for each of the Weyl groups mentioned above, i.e. on signed permutations. Computing certain correlations in these TASEPs gives the desired limiting directions. We also state several explicit conjectures for certain probabilities in these TASEPs on signed permutations. Joint work with Erik Aas, Arvind Ayyer and Samu Potka.

Macdonald polynomials are a family of symmetric functions that are known to have remarkable connections to a well-studied particle model called the asymmetric simple exclusion process (ASEP). It is natural to ask whether the modified Macdonald polynomials can be obtained using a combinatorial gadget for some other particle system. In this talk, we answer this question in the affirmative with a certain multispecies totally asymmetric zero-range process (TAZRP). This link motivated a new formula for modified Macdonald polynomials in terms of a new statistic on fillings of tableaux called queue inversions. We present a Markov process on these tableaux that projects to the TAZRP and derive formulas for stationary probabilities and certain correlations. Joint work with Arvind Ayyer and James Martin.

We show that the (usual, total variation) mixing time is not a quasi-isometry invariant, even between Cayley graphs. All terms will be explained in the talk. Joint work with Jonathan Hermon.

What do large permutations look like? We can in some cases answer this question with the help of limit structures called "permutons," and a variational principle. Examples show nice apparent behavior and some contrasts to the case of graphs and graphons. Joint work with Rick Kenyon, Dan Kral' and Charles Radin; later, with Chris Coscia, Sayan Das, Sumit Mukherjee and Martin Tassy.

In this talk, we study a non-uniform distribution on permutations (of any given size), where the probability of a permutation is proportional to $\theta^{rec}$ where $rec$ denotes the number of records (a.k.a. left-to-right maxima). The motivation for defining this model of non-uniform random permutations is the analysis of algorithms. Indeed, when analyzing algorithms working on arrays of numbers (modeled by permutations), the uniform distribution on the set of possible inputs is usually assumed. However, the actual data on which these algorithms are used is rarely uniform, and often displays a bias towards "sortedness". Our model has this bias towards "sortedness" while remaining tractable from the point of view of the analysis of algorithms. Our results on this model are of three types. First, we exhibit several efficient random samplers of permutations under this distribution. Second, we analyze the behavior of some classical permutation statistics, some of which with applications to the analysis of algorithms. Finally, we describe the "typical shape" of permutations in our model, by means of their (deterministic) permuton limit. This is joint work with Nicolas Auger, Cyril Nicaud and Carine Pivoteau.

A pattern $\tau$ is a fixed (short) permutation. We are interested in the number of occurrences of a pattern $\tau$ in a random (long) permutation $\pi$, where an occurrence is a subsequence with the same relative order as $\tau$. We also consider constrained cases, where we count only occurrences with some restrictions on the gaps between the elements of the subsequence. In particular, we consider vincular patterns, where some elements in the subsequence are required to be adjacent in $\pi$. Asymptotic normality has been shown by Bóna (2007, 2008, 2010) and (vincular permutations) Hofer (2018). We show that these results follow from general results on U-statistics. For constrained (e.g. vincular) cases, this requires results on m-dependent U-statistics. We consider also linear combinations of counts for several patterns. Typically, these too are asymptotically normal, but there are degenerate cases, see Janson, Nakamura and Zeilberger (2015) and Even-Zohar (2020). Much is known about degenerate cases too, but there are also open problems, in particular for constrained cases.

Linear extensions of a poset P=(X, <) of size n are order preserving bijections from X to {1,...,n}. These linear extensions generalize Young tableaux and various multi-dimensional random walks models. I will give a short survey about what is known about linear extensions and present our recent work on the subject. Joint work with Swee Hong Chan and Greta Panova.

The representation theory of the symmetric group provides several beautiful combinatorial formulas. The idea to use it to study random walks comes from Diaconis and Shahshahani, who used some formulas to bound the eigenvalues of the random transposition shuffle, leading to a cutoff phenomenon. Our main goal will be to explain how to improve their L^2 bound method to obtain cutoff profiles, and more concretely how this applies to random transpositions. We will first recall some definitions and explain the link between representation theory and Fourier analysis. Then, we will explain the limit profile method, and its generalisation to reversible Markov chains (by Nestoridi and Olesker-Taylor). Finally, we will discuss the Murnagham-Nakayama formula and its link with the fixed points of permutations. The talk will not assume prior knowledge of representation theory, all representation theoretic statements be also explained in terms of eigenvalues and eigenvectors of the transition matrix.

A stochastic process is called finitely dependent if variables located further than some fixed distance apart are independent. An obvious way to construct a finitely dependent process is as a block factor; that is, a fixed-range function of an i.i.d. process. It is much more difficult to construct and understand stationary finitely processes that are not block factors. In fact, for some decades it was unknown whether such processes exist. The picture has become much more intriguing thanks to the recent discovery that hard constraints distinguish between the two classes of process. Specifically, on the integer line Z (say), consider any system of hard local constraints on a discrete process. Provided the system satisfies certain non-triviality conditions, it cannot be satisfied by any block factor, but it can be satisfied by a stationary finitely dependent process. The former statement is proved by Ramsey-theoretic arguments. The latter comes down to a remarkable family of finitely dependent processes satisfying the canonical constraint system of proper colouring. There is essentially only one known construction of such processes, together with a few variants. The construction is short and explicit, yet at the same time deeply mysterious, and it revolves around random permutations. Based on joint works with Avi Levy, Tom Hutchcroft and Tom Liggett.

The totally asymmetric simple exclusion process (TASEP) was introduced around 1970 as a model for translation in protein synthesis and traffic flow. The inhomogeneous TASEP is a Markov chain of weighted particles hopping on a lattice, in which the hopping rate depends on the weight of the particles being interchanged. We will consider the case where the lattice is a ring, and each particle has a distinct weight, so that we can think of this model as a Markov chain on permutations. We will see that in many cases, and in particular for w an "evil-avoiding" permutation, the steady state probability of w can be expressed in terms of Schubert polynomials. Based on joint work with Donghyun Kim. The inhomogeneous TASEP, Schubert polynomials, and evil-avoiding permutations

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.