Schedule for: 19w5220 - Asymptotic Algebraic Combinatorics

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.

I will survey applications of exact and asymptotic combinatorial methods to problems in probability theory. The methods will be familiar to combinatorialists: bijections (including RSK), inclusion-exclusion and other determinantal methods, lattice path enumeration results, the transfer matrix method, and analytic methods based on generating functions in one or more variables. The questions may be less familiar. These include non-intersecting Brownian motions and Brownian watermelons, SLE and Liouville Quantum Gravity, random tilings and quantum walks.

Consider a list of n particles labelled in increasing order. A sorting network is a way of sorting this list into decreasing order by swapping adjacent particles, using as few swaps as possible. Simulations of large-n uniform random sorting networks reveal a surprising and beautiful global structure involving sinusoidal particle trajectories, a semicircle law, and a theorem of Archimedes. Based on these simulations, Angel, Holroyd, Romik, and Virag made a series of conjectures about the limiting behaviour of sorting networks. In this talk, I will discuss how to use the local structure of random sorting networks to prove these conjectures.

A shifted tableau of staircase shape has row lengths n,n-1,...,2,1 adjusted on the right side. I will present the limit shape for a uniformly random shifted Young tableau. This implies via properties of the Edelman– Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. (Based on joint work with Samu Potka and Robin Sulzgruber.)

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

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

I will review the progress in problems related to the branching graphs in asymptotic combinatorics and representation theory during the last 40 years. We will start from characters of infinite-dimensional unitary group, pass through Gelfand-Tsetlin graph and asymptotics of Schur polynomials, and end with a very recent topic of q-deformations.

Meet in the foyer of the Max Bell building, in front of the meeting room, for the group photo. Dress for the weather, as the photo will be outside. Don't be late, or you may not be in the group photo!

A standard Young tableau (SYT) is a filling of the boxes of a Young diagram of size n with the numbers 1 to n, such that the rows and columns are increasing. The hook-length formula of Frame, Robinson and Thrall allows one to compute the number of SYTs of a certain shape. However, when one considers SYTs of skew shapes (a diagram obtained by removing a Young diagram $\mu$ from the top left corner of a larger Young diagram $\lambda$), there is no such simple formula, and it is therefore harder to count them. In this talk, we will study the asymptotics of the number of SYTs of skew shapes. Our technique relies on bounds for characters of the symmetric group. This is joint work with Valentin Féray.

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.

Pólya urns are urns where at each unit of time a ball is drawn and replaced with some other balls according to its colour. We introduce a more general model: the replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We extend the work of Flajolet et al. on Pólya urns: the generating function encoding the evolution of the urn is studied by methods of analytic combinatorics. We show that the initial partial differential equations lead to ordinary linear differential equations which are related to hypergeometric functions (giving the exact state of the urns at time n). When the time goes to infinity, we prove that these periodic Pólya urns have asymptotic fluctuations which are described by a product of generalized gamma distributions. With the additional help of what we call the density method (a method which offers access to enumeration and random generation of poset structures), we prove that the law of the south-east corner of a triangular Young tableau follows asymptotically a product of generalized gamma distributions. This allows us to tackle some questions related to the continuous limit of large random Young tableaux and links with random surfaces. Joint work with Philippe Marchal and Michael Wallner.

The asymptotic study of multivariate generating functions comprises the domain of Analytic Combinatorics in Several Variables (ACSV). Analogously to the univariate setting, the techniques of ACSV show how the singularities of a (typically rational) multivariate generating function dictate asymptotics of its coefficients. Unlike the univariate case, however, a multivariate generating function encodes a wealth of sequences: one can take a direction vector R and examine asymptotics of the coefficient sequence on positive integer multiples of R. Although this definition is a priori only non-trivial when R contains rational entries, the techniques of ACSV show asymptotics typically vary in a uniformly predictable way as R varies smoothly, meaning asymptotics can be defined in a limit sense for “generic” directions. In this talk we survey the techniques of ACSV, discuss a new study of asymptotic transitions between different generic asymptotic regions, and highlight some new software implementations. Includes joint work with Yuliy Baryshnikov and Robin Pemantle, Bruno Salvy, and Éric Schost and Kevin Hyun.

I will present the recently developed theory of permutons, which are limits of permutation sequences. The convergence in terms of permutons can be seen either at the convergence of the rescaled permutation matrix, or as the convergence of pattern proportions. We will survey recent results involving permutons: limit of the so-called Mallows model, large deviation theory for permutations, limits of uniform random permutations in permutation classes with finite specification...

Let $\mathfrak{g}$ be a simple Lie algebras and $V_i$, $I=1,\cdots, m$ be finite dimensional representations of $\mathfrac{g}$. The asymptotic of the multiplicity of irreducible representations in the tensor product $\prod_{I=1}^m V_i^{\otimes N_i}$ is derived in the limit $N_i\to \infty$, and $N_1:\cdots :N_m$ is finite. This asymptotic is used to compute the asymptotic of the character measure in this limit. This is a joint work with N. Reshetikhin and V. Serganova.

We introduce a large class of random Young diagrams which can be regarded as a natural one-parameter deformation of some classical Young diagram ensembles; a deformation which is related to Jack polynomials and Jack characters. We show that each such a random Young diagram converges asymptotically to some limit shape and that the fluctuations around the limit are asymptotically Gaussian. This is a joint work with Piotr Śniady.

Spin characters of the symmetric groups, with the right choice of the normalization, form a beautiful collection of polynomial functions on the set of shifted Young diagrams. During the talk I will present two explicit formulas for spin characters in terms of maps (=bicolored graphs drawn on surfaces). Bonus: I leave it as an open problem to the participants of the workshop to fill in the gap in an alternative, conceptually new proof of these formulas. References: Sho Matsumoto, Piotr Śniady. Stanley character formula for the spin characters of the symmetric groups. https://arxiv.org/abs/1810.13255 Sho Matsumoto, Piotr Śniady. Linear versus spin: representation theory of the symmetric groups. https://arxiv.org/abs/1811.10434

Asymptotic representation theory of symmetric groups is a rich and beautiful subject with deep connections with probability, mathematical physics, and algebraic combinatorics. A one-parameter deformation of this theory related to infinite random matrices over a finite field leads to a randomization of the classical Robinson-Schensted correspondence between words and Young tableaux. Exploring such randomizations we find unexpected applications to six vertex (square ice) type models and traffic systems on a 1-dimensional lattice.

In the thermodynamic limit of the lozenge tiling model the frozen boundary develops special points where the liquid region meets with two different frozen regions. These are called turning points. It was conjectured by Okounkov and Reshetikhin that in the scaling limit of the model the local point process near turning points should converge to the GUE corners process. We will discuss various results showing that the point process at a turning point is the GUE corner process and that the GUE corner process is there in some form even when at the turning point the liquid region meets two frozen regions of arbitrary (non-lattice) rational slope. The last regime arises when weights in the model are periodic in one direction with arbitrary fixed finite period.

It is a remarkable fact that for many combinatorial statistics, the roots of the corresponding generating function are each either a complex root of unity or zero. We call such generating functions \textit{cyclotomic} and study the possible limit distributions of their coefficients using cumulants. We consider three main examples of cyclotomic generating functions. First, we use Stanley's $q$-hook length formula to study the major index on standard tableaux of block diagonal skew shape. We give a simple statistic on partitions, \textit{aft}, which completely classifies all possible normalized limit laws for major index on any sequence of partition shapes, resulting in the uniform-sum and normal distributions. Our classification provides a common generalization of earlier work due to Canfield--Janson--Zeilberger, Chen--Wang--Wang, Diaconis, Feller, Mann--Whitney, and others on limit distributions of $q$-multinomial coefficients and $q$-Catalan numbers. In our second example, we consider the coefficients of Stanley's $q$-hook-content formula and illustrate a variety of normal and non-normal limit laws in this case. Finally, we consider $q$-hook length formulas of Bj\"orner--Wachs for the generating functions of the major index and inversion number on linear extensions of labeled forests. We conclude with several open problems concerning unimodality, log-concavity, and local limit laws. This talk is based on joint works with Matjaž Konvalinka and Joshua Swanson.

The Nonvanishing Problem asks if a coefficient of a polynomial is nonzero. Many families of polynomials in algebraic combinatorics admit combinatorial counting rules and simultaneously enjoy having saturated Newton polytopes (SNP). Thereby, in amenable cases, Nonvanishing is in the complexity class ${\sf NP} \cap {\sf coNP}$ of problems with "good characterizations". This suggests a new algebraic combinatorics viewpoint on complexity theory. This paper focuses on the case of Schubert polynomials. These form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. We give a tableau criterion for Nonvanishing, from which we deduce the first polynomial time algorithm. These results are obtained from new characterizations of the Schubitope, a generalization of the permutahedron defined for any subset of the n x n grid, together with a theorem of A. Fink, K. Meszaros and A. St. Dizier, which proved a conjecture of C. Monical, N. Tokcan and the speaker.

I shall explain, and illustrate by examples, how I go about evaluating determinants.

In the literature there are several determinant formulas for Schur functions: the Jacobi--Trudi formula, the dual Jacobi--Trudi formula, the Giambelli formula, the Lascoux--Pragacz formula, and the Hamel--Goulden formula, where the Hamel--Goulden formula implies the others. In this talk we use the Bazin--Sylvester identity to derive a determinant formula for Macdonald's ninth variation of Schur functions. As consequences we obtain a generalization of the Hamel--Goulden formula and a Lascoux--Pragacz-type determinant formula for factorial Schur functions conjectured by Morales, Pak and Panova. This is joint work with Meesue Yoo.

Let $G$ be a graded graph with levels $V_0,V_1,\dots$. Fix $m$ and choose a vertex $v$ on the level $V_n, n\geqslant m$. Consider the uniform measure on the paths from $V_0$ to the vertex $v$. Each such a path has a unique vertex on the level $V_m$, and so the measure $\nu_v^m$ on $V_m$ is induced. It is natural to expect that such measures have a limit when vertex $v$ goes to infnity by somehow ``regular'' way. This limit is then natural to call the Plancherel measure (on the set $V_m$). We justify such approach for the graphs of Young and Schur (of Young diagrams and strict Young diagrams, respectively). For them the regularity is understood as follows: the proportion of the boxes contained in the first row and the first column goes to 0. For Young graph this was essentially proved in the seminal work of Vershik and Kerov. We propose more straightforward and elementary approach and discuss the appearing polynomial identities.

The lecture hall partitions were introduced by Bousquet-Mélou and Eriksson in 1997 by showing that they are the inversion vectors of elements of the parabolic quotient $\tilde{C}_n/C_n$. Since 1997, a lot of beautiful combinatorial techniques were developed to study these objects and their generalisations. These use basic hypergeometric series, geometric combinatorics, real rooted polynomials... Some of those results can be found in the survey paper by C. D. Savage "The Mathematics of lecture hall partitions". Here we take a different approach and show that these objects are also multivariate moments of the Little q-Jacobi polynomials. The multivariate moments were introduced by Williams and me in the context of asymmetric exclusion processes. The benefit of this new approach is that we define a tableau analogue of lecture hall partitions and we show that their generating function is a beautiful product. This uses a mix of orthogonal polynomials techniques, non intersecting lattice paths (i.e. determinants) and q-Selberg integral. This is joint work with Jang Soo Kim (SKKU).

In this talk we present some asymptotic of bounded Lecture Hall Tableaux of a given shape. We describe how to view the tableaux as a collection of nonintersecting paths. We then use tangent method, developed by Colomo and Sportiello, to recover a parametrization of the arctic curves arising in the thermodynamic limit.

We give new bounds and asymptotic estimates for Kronecker and Littlewood--Richardson coefficients. Notably, we resolve Stanley's questions on the shape of partitions attaining the largest Kronecker and Littlewood–Richardson coefficients. We apply the results to asymptotics of the number of standard Young tableaux of skew shapes. Joint work of: Igor Pak, Greta Panova, Damir Yeliussizov.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, Max Bell and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon. The Front Desk has a luggage storage service.