Réunion d'hiver SMC 2023

Montréal, 1 - 4 decembre 2023


Combinatoires algébrique et énumérative
Org: Alejandro Morales (Université du Québec à Montréal (UQAM)), Mohamed Omar (York University) et Vasu Tewari (University of Toronto)

MARIE ALBENQUE, CNRS -- Université Paris cité
Bijective proof of rational enumerative schemes for maps on the torus of genus $g$.  [PDF]

Maps are graphs embedded into surfaces. Their study started in the 60s with Tutte's work, in which he obtained many closed enumerative formulas for the planar case (i.e. when the surface is the sphere). These formulas, obtained by highly non trivial computations, are remarkably simple. To explain this simplicity, some bijections between planar maps and certain families of decorated trees were obtained (among others!) by Cori and Vauquelin in 1981 and by Schaeffer in 1997 and 1998

When the underlying surface is the torus with $g$ holes, in 1991 Bender and Canfield obtained, followed by Bender, Canfield and Richmond in 1993, obtained some formulas analogous to Tutte's ones, but in the form of a rationality scheme valid for any $g$.

In this talk, I will give the first bijective derivation of their result, which consists in an extension of Schaeffer's bijection to the torus.

This is based on a joint work with Mathias Lepoutre.

FARID ALINIAEIFARD, University of British Columbia
Generalized chromatic functions  [PDF]

We define vertex-colourings for edge-partitioned digraphs, which unify the theory of P-partitions and proper vertex-colourings of graphs. We use our vertex-colourings to define generalized chromatic functions, which merge the chromatic symmetric and quasisymmetric functions of graphs and generating functions of P-partitions. Moreover, generalized chromatic functions can refine the (3+1)-free conjecture and the Tree Conjecture. We discuss several open problems related to the refinement of the conjectures.

DAVE ANDERSON, Ohio State University
New formulas for Schubert polynomials via bumpless pipe dreams  [PDF]

The last five years have seen many applications of the “bumpless pipe dreams” (BPDs) introduced in Lam-Lee-Shimozono’s seminal paper on back stable Schubert polynomials. I will report on joint work with William Fulton, in which we obtain a decomposition of the Schubert polynomial as a sum of “drift polynomials”. The new formula has several pleasant features: 1) in many cases, it allows efficient computation of the Schubert polynomial; 2) the constituent drift polynomials have tableau formulas, and can (sometimes) be written naturally as Lindström-Gessel-Viennot determinants; and 3) nearly without change, the same formula computes the enriched Schubert polynomials, which specialize to the back stable ones. I’ll also demo some software for working with BPDs.

SPENCER BACKMAN, University of Vermont
Higher Categorical Associahedra  [PDF]

The associahedron is a well-known polytope with connections to many different areas of combinatorics, algebra, geometry, topology, and physics. The associahedron has Catalan number many vertices which can be equivalently described in terms of triangulations of a polygon, planar binary trees, maximal parenthesizations of a word, etc. From one perspective, the associahedron encodes the combinatorics of morphisms in the Fukaya category of a symplectic manifold. In 2017, Bottman introduced a family of posets called 2-associahedra which encode the combinatorics of functors between Fukaya categories, and he conjectured that they can be realized as the face posets of convex polytopes. We will begin by reviewing the basic theory of associahedra. We will then introduce categorical n-associahedra as a natural extension of associahedra and 2-associahedra, and we will produce a family of complete polyhedral fans called velocity fans whose face posets are the categorical n-associahedra. This is joint work with Nathaniel Bottman and Daria Poliakova.

Alcoved signed permutations  [PDF]

We introduce a new partial order on signed permutations whose cover relations are determined by certain \emph{big ascents}. Its Hasse diagram is dual to the alcove triangulation of the fundamental parallelepiped of the type C root system, as studied by Lam and Postnikov. This duality allows us to use Ehrhart theory to obtain a generating function for big ascents and, conversely, to combinatorially interpret the coefficients of $h^*$-polynomial of the type C half-open hypersimplices. We also obtain a relation between the distribution of covers in our poset and the usual descents in the ``half'' weak order of type BC. Moreover, we show that these family of posets converges, in a precise sense, to the lattice of strict partitions. This is based on joint work with Antoine Abram.

JONATHAN BORETSKY, Harvard University
The Totally Nonnegative Tropical Flag Variety  [PDF]

The flag variety of rank $r=(r_1,\ldots,r_k)$ has points corresponding to collections of subspaces $(V_1,\ldots, V_k)$ with $V_i$ of dimension $r_i$ such that $V_i$ is contained in $V_{i+1}$. We explore two nonnegative versions of this variety: First, we study the nonnegative flag variety, which corresponds to a subset of the flag variety consisting of flags that can be represented by totally positive matrices. Second, we study the tropicalization of the flag variety and, more specifically, its nonnegative part. In both cases, we provide equivalent descriptions of these spaces for flag varieties of rank $r=(a,a+1,\ldots,b)$, where $r$ consists of consecutive integers. This talk is based on joint work with Chris Eur and Lauren Williams.

Card shuffling, derangements, and q-analogues  [PDF]

How many times do you need to shuffle a deck of cards to ensure it is adequately mixed? This is a question in probability theory, but for many methods of card shuffling, the answer relies on combinatorics and representation theory. In this talk, I will discuss several classical card-shuffling processes and introduce their q-analogues, which can be understood as random walks on the (Type A) Hecke algebra. Motivated by questions of mixing times, I will present recent results and conjectures concerning the eigenvalues and eigenspaces of these (q-)shuffling operators. Along the way we will see derangements, desarrangements, and tableau combinatorics. This is joint work with Commins and Reiner, as well as Axelrod-Freed, Chiang, Commins and Lang.

KELVIN CHAN, York University
A cocharge folklore and super coinvariant spaces  [PDF]

It is well-known that the major index $maj$ and the cocharge statistics $chr$ of standard tableaux are equidistributed. It is also well-known that $maj$ and $chr$ are related to bases of the classical coinvariant spaces. In this talk, we consider a generalization of the classic coinvariant spaces called the super coinvariant spaces. We motivate and discuss a folklore that refines the equidistrubition of $maj$ and $chr$. Finally, we discuss some open problems in super coinvariant spaces.

JEREMY CHIZEWER, University of Waterloo
Enumeration and Compact Encoding of AVL Trees  [PDF]

An AVL tree is a type of self-balancing binary search tree commonly used in computer science. From an enumerative perspective, an AVL tree is a rooted planar binary tree such that the heights of the left and right subtrees at any node differ by at most one. Because AVL trees are most easily recursively decomposed by height instead of by number of nodes, their enumeration is more difficult than other classes of recursively defined trees.

Motivated by a desire to derive the information-theoretic lower bound on the number of bits needed to encode an AVL tree, we develop a new method for the study of combinatorial classes whose generating functions satisfy certain functional equations and use this tool to derive the growth rate of AVL trees and related structures. We also describe a new encoding for AVL trees that uses less than one bit per node.

Joint work with Stephen Melczer, J. Ian Munro, and Ava Pun.

ANGELE FOLEY, Wilfrid Laurier University
H-Chromatic Symmetric Functions  [PDF]

We recently introduced H-chromatic symmetric functions, $X^H_G$, which use the H-coloring of a graph G to define a generalization of Stanley's chromatic symmetric functions. In this talk we take a tour of these new symmetric functions, considering equivalence questions and basis questions. We also include conjectures and open problems.

This is joint work with N.M. Eagles, A. Huang, E. Karagozishvili, and A. Yu.

LUCAS GAGNON, York University
The shadows of quasisymmetric Templerley—Lieb coinvariants are noncrossing partitions  [PDF]

In the early 2000s, Hivert and Aval, Bergeron, and Bergeron found compelling evidence that the Templerley—Lieb algebra $\mathrm{TL}_{n}(2)$ and the quasisymmetric polynomials $\mathrm{QSym}_{n}$ in $R = \mathbb{C}[x_{1}, \ldots, x_{n}]$ should have a coinvariant theory much like the symmetric group and symmetric polynomials. Unfortunately, pinning down the details of this relationship is harder than expected, and a $\mathrm{TL}_{n}(2)$ action on $R/\langle \mathrm{QSym}_{n}^{+} \rangle$ has eluded description for almost 20 years. I will describe how noncrossing partitions can take us from the Templerley—Lieb algebra to quasisymmetric polynomials and back, moving one step closer to a true coinvariant theory along the way. Based on joint work with Nantel Bergeron.

SAM HOPKINS, Howard University
Combinatorial reciprocity for non-intersecting paths  [PDF]

Combinatorial reciprocity is when the counting function for one enumeration problem, evaluated at negative inputs, yields the counting function for another, related problem. We prove a combinatorial reciprocity result for the enumeration of non-intersecting paths in a linearly growing sequence of acyclic planar networks. We explain two applications of this theorem: reciprocity for fans of bounded Dyck paths, and reciprocity for Schur function evaluations with repeated values. This talk is based on joint work with Gjergji Zaimi.

Generalized parking function  [PDF]

The “classical” parking functions of length $n$ is counted by the formula $(n + 1)^{n-1}$. They corresponds bijectively to the standard Young tableaux (SYT) of skew-shape $\alpha+1^n/\alpha$, where $\alpha$ is any partition under $\lambda = (n-1,\dots,2,1)$. There is a natural symmetric group action on these parking functions, where the orbit is counted by the Catalan number $1/(n+1)\binom{2n}{n}$. The Frobenius character of this action over all SYT of shape $\alpha+1^n/\alpha$ is given by the skew Schur function $s_{(\alpha+1^n/\alpha)}(\mathbf{x})$. In this talk we generalize this notion to any partition $\lambda$ and study the combinatorics of the generalized parking function by relating them to non-crossing lattice paths. This is a joint work with François Bergeron and Yan Lanciault.

Left Regular Bands of Groups and the Mantaci-Reutenauer Algebra  [PDF]

In a highly influential paper, Bidigare, Hanlon and Rockmore showed that a number of popular Markov chains are random walks on the faces of a hyperplane arrangement. The analysis of these Markov chains takes advantage of the monoid structure on the set of faces. This theory was later extended by Brown to a larger class of monoids called left regular bands (LRBs).

This talk will explore a generalization called \emph{LRBs of Groups} (LRBGs) that delightfully mixes LRBs and group theory. The principal example throughout will be a LRBG defined by S. Hsiao, which links the braid arrangement with the Mantaci-Reutenauer algebra. The talk is based on joint work with Jose Bastidas and Sarah Brauner.

GABE UDELL, Cornell University
Degenerating brick manifolds and subdividing the associahedron  [PDF]

The associahedron is a convex polytope which pops up all over mathematics. Loday gave a realization of the associahedron as a lattice polytope; Loday's associahedron has subsequently been understood as an example of a brick polytope. Brick polytopes are defined from subword complexes and they give polytopal realizations of certain subword complexes. Escobar associated to each subword complex a smooth sub-variety of a Bott-Samelson variety, which she called a brick manifold, and she showed that the brick polytope is the moment polytope of the brick manifold. In particular, Escobar constructed the toric variety of Loday's associahedron as a brick manifold. We describe a degeneration of any brick manifold and show that in the special case of the toric variety of the associahedron, the degeneration induces a polyhedral subdivision of the associahedron into cubes.

This is joint work with Raj Gandhi.

PRATEEK VISHWAKARMA, University of Regina
Plücker inequalities for weakly separated coordinates in totally nonnegative Grassmannian  [PDF]

We show that the partial sums of the long Pl\"ucker relations for pairs of weakly separated Plücker coordinates oscillate around $0$ on the totally nonnegative part of the Grassmannian. Our result subsumes the classical oscillating inequalities by Gantmacher--Krein (1941) and recent results on totally nonnegative matrix inequalities by Fallat--Vishwakarma (2023). In fact we obtain a characterization of weak separability, by showing that no other pair of Pl\"ucker coordinates satisfies this property.

KAREN YEATS, University of Waterloo
Combinatorial interpretation of the coefficients of the BDG action  [PDF]

Causal set theory is a model of quantum gravity where the underlying spacetime is a locally finite poset. The Benincasa-Dowker-Glaser (BDG) action is an action on a causal set which corresponds to the classical Einstein-Hilbert action. L.Glaser gave formulas for the coefficients of the BDG action. I will give a combinatorial interpretation for these coefficients in terms of some lattice walks, and explain some consequences. No familiarity with causal set theory is required.

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