Réunion d'hiver SMC 2020

Montréal, 4 - 7 décembre 2020


Combinatoire Énumérative
Org: Sergi Elizalde (Dartmouth), Steven Karp (LaCIM, UQAM), Nadia Lafreniere (Dartmouth) et Alejandro Morales (UMass Amherst)

ARVIND AYYER, Indian Institute of Science
Toppleable permutations and excedances  [PDF]

Recall that an excedance of a permutation $\pi$ is any position $i$ such that $\pi_i > i$. 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. We will show that the number of toppleable permutations on $n$ letters is the same as the number of permutations on $n$ letters for which excedances happen exactly at $\{1,\dots, \lfloor (n-1)/2 \rfloor)$. Time permitting, we will show bijectively that this is also the number of acyclic orientations with unique sink of the complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor + 1}$.

This is joint work with D. Hathcock and P. Tetali (arXiv:2010.11236).

JUSTINE FALQUE, LIGM, Univ. Marne-la-Vallée
3-dimensional Catalan objets: a (partial) overview and a new bijection  [PDF]

A variant of the famous Catalan numbers, the sequence of 3-dimensional Catalan numbers counts the standard Young tableaux of shape (n,n,n) (whereas the classical Catalan numbers count those of shape (n,n)).

This talk will dwell on three combinatorial objects that are counted by the 3-dimensional Catalan numbers: first, 1234-avoiding up-down permutations; second, a certain class of weighted Dyck paths; and finally, product-coproduct prographs (introduced by Borie). We will outline how these objects relate to each other, and present a recently discovered bijection between the former two. Depending on the time left, we will discuss how the geometrical nature of PC prographs could be exploited to try to obtain a poset or even lattice structure on these objects.

ILSE FISCHER, University of Vienna
Bijective proofs of (skew) Schur polynomial factorizations  [PDF]

Schur polynomials and their generalizations appear in various different contexts. They are the irreducible characters of polynomial representations of the general linear group and an important basis of the space of symmetric functions. They are accessible from a combinatorial point of view as they are multivariate generating functions of semistandard tableaux associated with a fixed integer partition. Recently, Ayyer and Behrend discovered for a wide class of partitions factorizations of Schur polynomials with an even number of variables where half of the variables are the reciprocals of the others into symplectic and/or orthogonal group characters, thereby generalizing results of Ciucu and Krattenthaler for rectangular shapes. We present bijective proofs of such identities. (Joint work with Arvind Ayyer.)

MARIA GILLESPIE, Colorado State University
Parking functions and a projective embedding of $\overline{M}_{0,n}$  [PDF]

We present a new class of parking functions, which we call column restricted parking functions or CPF's, arising in the study of the compact moduli space $\overline{M}_{0,n}$ of genus $0$ stable curves with $n$ marked points. The space $\overline{M}_{0,n}$ embedded into the product of projective spaces $\mathbb{P}^1\times \mathbb{P}^2\times \cdots \times \mathbb{P}^{n-3}$, and we give give an explicit combinatorial formula for the multidegrees of this embedding in terms of CPF's of height $n-3$. This combinatorial interpretation implies that the total degree of the embedding (defined as the sum of the multidegrees) is equal to the total number of CPF's of height $n-3$, and we show that these are enumerated by the double factorial $(2(n-3)-1)!!=(2n-7)(2n-9) \cdots(5)(3)(1)$. This is joint work with Renzo Cavalieri and Leonid Monin.

If time permits, we will mention new joint work with Sean Griffin and Jake Levinson, in which we find an explicit bijection between CPF's and boundary points on $\overline{M}_{0,n}$ that is compatible with a geometric recursion defining the multidegrees.

SAM HOPKINS, University of Minnesota
Promotion of Kreweras words  [PDF]

Kreweras words are words consisting of n A's, n B's, and n C's in which every prefix has at least as many A's as B's and at least as many A's as C's. Equivalently, a Kreweras word is a linear extension of the poset Vx[n]. Kreweras words were introduced in 1965 by Kreweras, who gave a remarkable product formula for their enumeration. Subsequently they became a fundamental example in the theory of lattice walks in the quarter plane. We study Schützenberger's promotion operator on the set of Kreweras words. In particular, we show that 3n applications of promotion on a Kreweras word merely swaps the B's and C's. Doing so, we provide the first answer to a question of Stanley from 2009, asking for posets with "good" behavior under promotion, other than the four families of shapes classified by Haiman in 1992. Our proof uses webs (in the sense of Kuperberg) and we obtain some interesting enumerative corollaries about webs. This is joint work with Martin Rubey.

HELEN JENNE, CNRS, Institut Denis Poisson, Université de Tours
Double-dimer condensation and the dP3 Quiver  [PDF]

In this talk we will discuss an application of double-dimer condensation to a problem in cluster algebras, which is ongoing joint work with Tri Lai and Gregg Musiker. Double-dimer condensation is a recurrence satisfied by the partition function for double-dimer configurations of a planar bipartite graph. A similar identity for the number of dimer configurations of a planar bipartite graph was established nearly 20 years ago by Kuo.

In 2017, Lai and Musiker gave combinatorial interpretations for many toric cluster variables in the cluster algebra associated to the cone over the del Pezzo surface dP3. Specifically, they used Kuo condensation to show that most toric cluster variables have Laurent expansions agreeing with the partition functions for dimer configurations. However, in some cases, the dimer model was not sufficient. We show that in these cases, the Laurent expansions agree with partition functions for double-dimer configurations.

A Vertex Model for LLT Polynomials  [PDF]

In the talk we will describe a novel Yang-Baxter integrable vertex model. From this vertex model we will construct a certain class of partition functions that we will show are equal to the LLT polynomials of Lascoux, Leclerc, and Thibon. Using the vertex model formalism, we give alternate proofs of many properties of these polynomials, including symmetry and a Cauchy identity. This is based on joint work with Sylvie Corteel, Andrew Gitlin, and Jeremy Meza.

MATJAŽ KONVALINKA, University of Ljubljana
Some natural extensions of the parking space  [PDF]

We construct a family of $S_n$-modules indexed by $c\in\{1,\dots,n\}$ with the property that upon restriction to $S_{n-1}$ they recover the classical parking function representation of Haiman. The construction of these modules relies on an $S_n$-action on a set that is closely related to the set of parking functions. We compute the characters of these modules and use the resulting description to classify them up to isomorphism, and compute the number of isomorphism classes. Based on empirical evidence, we conjecture that when $c=1$, our representation is $h$-positive and is in fact the (ungraded) extension of the parking function representation constructed by Berget and Rhoades.

Berget and Rhoades asked whether the permutation representation obtained by the action of $S_{n-1}$ on parking functions of length $n-1$ can be extended to a permutation action of $S_{n}$. We answer this question in the affirmative, by realizing our module in two different ways.

This is joint work with Robin Sulzgruber and Vasu Tewari.

JOEL LEWIS, George Washington University
Hurwitz numbers for reflection groups  [PDF]

In the symmetric group, the Hurwitz numbers count factorizations of a given permutation as a product of a fixed number of transpositions, subject to the requirement that the factors used act transitively on $\{1, \ldots, n\}$. We study the analogous problem when the symmetric group is replaced by any Weyl group $W$, counting factorizations as a product of reflections subject to the requirement that the factors generate $W$. We find a beautiful uniform formula generalizing the result in the symmetric group, and describe some interesting features of the (case-by-case) proof.

ALI ASSEM MAHMOUD, University of Ottawa
On the Enumerative Structures in QFT  [PDF]

The aim of this talk is to display some enumerative results that are directly applied in quantum field theory. We shall see how the number of connected chord diagrams can be used to count one-particle-irreducible (1PI) diagrams in Yukawa theory. This translation of Feynman diagrams simplified the process of calculating the asymptotic behaviour of the corresponding Green functions.

MARNI MISHNA, Simon Fraser University
Enumerating excursions on Cayley graphs  [PDF]

Given a finitely generated group with generating set S, we study the cogrowth sequence, which is the number of words of length n over the alphabet S that are equal to one. This is related to the probability of return for walks in a Cayley graph with steps from S. This talk will survey the connections between the structure of the group, and properties of the cogrowth sequence via the nature of its generating function. We will then show that the cogrowth sequence is not P-recursive when G is an amenable group of superpolynomial growth, answering a question of Garrabant and Pak. In addition, we compute the exponential growth of the cogrowth sequence for certain infinite families of free products of finite groups and free groups. Work in collaboration with Jason Bell and Haggai Liu

Hecke insertion and maximal increasing and decreasing sequences in fillings of polyominoes  [PDF]

We will give a proof that the number of 01-fillings of a given stack polyomino (a polyomino with justified rows whose lengths form a unimodal sequence) with at most one 1 per column which do not contain a fixed-size northeast chain and a fixed-size southeast chain, depends only on the set of row lengths of the polyomino. The proof is via a bijection between fillings of stack polyominoes which differ only in the position of one row and uses Hecke insertion and jeu de taquin for increasing tableaux. We will discuss how this work relates to other results about chains in fillings of polyominoes as well as graphs and set partitions and mention some possible and impossible extensions.

COLLEEN ROBICHAUX, University of Illinois at Urbana-Champaign
An Efficient Algorithm for Deciding the Vanishing of Schubert Polynomial Coefficients  [PDF]

Schubert polynomials form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. The vanishing problem for Schubert polynomials asks if a coefficient of a Schubert polynomial is zero. We give a tableau criterion to solve this problem, 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\times n$ grid. In contrast, we show that computing these coefficients explicitly is $\#{\sf P}-{\sf complete}$. This is joint work with Anshul Adve and Alexander Yong.

VASU TEWARI, University of Pennsylvania
Refined mixed Eulerian numbers  [PDF]

Mixed Eulerian numbers were introduced by Postnikov as mixed volumes of hypersimplices, and they can be considered as a far-reaching generalization of classical Eulerian numbers. In this talk, we will introduce a refinement of these numbers by `inserting a $q$' in the setup. We will subsequently provide combinatorial and probabilistic interpretations for these \emph{remixed Eulerian numbers}. Time permitting, we will discuss our main motivation: combinatorics of Schubert polynomials and the permutahedral variety.

This is a report on work in progress with Philippe Nadeau.

NATHAN WILLIAMS, University of Texas at Dallas
Strange Expectations in Affine Weyl Groups  [PDF]

We extend our previous work on computing expected values of quadratic forms on coroot points in the Sommers region from simply-laced affine Weyl groups to all affine Weyl groups. In type A, our uniform formula recovers Drew Armstrong's conjecture for the average number of boxes in a simultaneous core. This is joint work with Marko Thiel and Eric Stucky.

© Société mathématique du Canada : http://www.smc.math.ca/