AlCoVE: an Algebraic Combinatorics Virtual Expedition

We will describe and study a natural symmetric function refinement of the h-polynomial for a wide class of polyhedral complexes having all faces isomorphic to product of associahedra. Similar considerations can be obtained by replacing the basic blocs (associahedra) by other families, such as permutahedra.

One "tree isomorphism problem" asks whether trees are distinguished by their chromatic symmetric function (CSF). Since the question was raised by Stanley in a 1995 article, various researchers have been able to determine that the CSF recovers substantial information about trees -- for example, degree sequence, path sequence, number of subtrees, leaf components, internal vertices, etc. I will describe recent joint work with Johnston, Lawson, Orellana, Pan and Sato in which we studied the CSF of unicyclic graphs expressed in the star basis of symmetric functions. We obtain several results analogous to prior work on trees including recovery of graph data and identification of families of unicyclic graphs that can be distinguished from the star expansion. On the other hand, some results identify obstacles to unicyclic graph recovery from CSF data, leading to a family of pairs unicyclic graphs of increasing girth which have the same CSF. These contrasting results highlight the depth and mystery of the tree isomorphism problem.

With a handful of Maple commands, we made several observations about some classical combinatorial objects, and we were led to questions to which there do not seem to be immediate answers. At least, we would like to bring to your judgement if there are. Here are the familiar names: the q-Catalan numbers, the q-binomial coefficients, the q-derangement numbers, the number of permutations of \(\{1, 2, \ldots, n\}\) for which the longest increasing subsequences are of length k, the partition function \(p(n)\), and the cumulative partition function \(s(n)=p(1)+p(2) + \cdots + p(n)\), convexity, infinite convexity, log-concavity, infinite log-concavity, etc. The Ramanujan polynomials also come on the scene. Then it's time to wonder whether the old dogs have new tricks, and Maple might give us a clue.

Abstract TBA.

Canon permutations are multiset permutations in which the subwords formed by the first occurrences, second occurrences, and so on, all coincide (for example, 331412432142). They are motivated from pattern-avoidance considerations analogous to those behind Stirling and quasi-Stirling permutations. Elizalde showed that their descent polynomials factor elegantly as a product of two palindromic polynomials: an Eulerian polynomial and a Narayana polynomial. We explain this phenomenon using Stanley’s theory of \((P, \omega)\)-partitions, along the way generalizing Elizalde's results. This approach yields a new family of palindromic polynomials arising from descent statistics on multisets, which we conjecture to be \(\gamma\)-positive. For descent polynomials of regular canon permutations, the poset perspective also provides a combinatorial interpretation of their \(\gamma\)-coefficients via a Foata--Strehl-type action due to Brändén. This talk is based on joint work with Matthias Beck.

Abstract TBA.

The Tsetlin library is a random shuffling process on permutations of n letters, where each letter i is brought to the front with probability x_i. I will discuss a q-deformation of the Tsetlin library by replacing the symmetric group action on permutations by the action of the type A Iwahori-Hecke algebra. The stationary distribution and spectrum of this Markov chain can be computed via a relation to a Markov chain on complete flags over the finite field. We prove that for a natural choice of x_i the total variation distance mixing time of the q-Tsetlin library on permutations of n is \(O(n)\) compared to \(\Theta(n \log n)\) for the Tsetlin library at q = 1.

There is more than one way to compactify a moduli space. The "muticolored spaces" are a way of compactifying the space of all choices of n distinct points on a projective line up to isomorphism, by assigning each point a "color" that dictates what happens in the limit when marked points collide. We give an overview of a recent discovery, joint with Vance Blankers and Jake Levinson, of a combinatorial way to simplify an alternating sum formula for an intersection theory problem on multicolored spaces, using a sign reversing involution. This method gave the first proof that the answer was always positive, and yields combinatorial bounds in terms of matchings on graphs.

Every combinatorial formula has its q-analogue, often involving q-binomials. But some q-analogues seem to open a new world of finer and richer combinatorics, whereas others obscure the beauty of the original formula. On the other hand, q-binomials are a tool to study an instance of the problem of plethysm, but which q-binomial identities reflect a deeper property of plethysms? We develop a framework to give a partial answer to this question.

Secretly, we will be presenting progress towards a categorification of quantum \(\mathfrak{sl}_2\) joint with Á. Martínez, M. Szwej, and M. Wildon.

The weak Bruhat order is a natural partial order on permutations, but even very basic global questions about it are surprisingly difficult. In this talk I will discuss the probability that two independent uniformly random permutations are comparable in weak Bruhat order. We prove that this probability has asymptotic form \(\exp((−1/2 + o(1)) n \log n)\), which significantly improves the previous best upper and lower bounds of Hammett and Pittel. I will explain how the problem can be reduced to counting linear extensions of permutation posets, and how this leads to a partition-based analysis through the Robinson–Schensted–Knuth correspondence and Plancherel measure. The argument also uses the Baik–Deift–Johansson theorem on longest increasing subsequences of random permutations.

Abstract TBA.

Schubert coefficients are nonnegative integers that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. It is a major open problem whether they have a combinatorial interpretation. In this talk we discuss the closely related problem of determining the positivity of Schubert coefficients from a computational complexity perspective. This is joint work with Igor Pak.