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.

The symmetric edge polytope of a graph is a symmetric lattice polytope defined in terms of the edges of the graph. These polytopes appear in different mathematical contexts and recently have attracted attention as a a family with interesting Ehrhart-theoretic properties. We will discuss a sharp lower bound for the number of edges of symmetric edge polytopes, expressed only in terms of invariants of the graph. Then we highlight a connection with the \(h^*\)-polynomial of such polytopes, and in particular, discuss implications for their conjectured gamma positivity.

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.

In 2011, Dyer put out a conjecture with an interesting consequence, that in order to understand the weak order of a Coxeter group, one can use the Bruhat order. Dyer formulated an operator which, conjecturally, would produce the join in the weak order when using the Hasse diagram of the Bruhat order. In this talk we describe this operator and give a (semi-)positive result to Dyer's conjecture.

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. arXiv link

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.

The geometry of the image of the nonnegative orthant under the power-sum polynomials maps is called the Vandermonde cell. We analyze the geometry of this object in a finite number of variables and concentrate on the limit as the number of variables approaches infinity. We explain how the geometry of the limit plays a crucial role in undecidability results in nonnegativity of symmetric polynomials, deciding validity of trace inequalities in linear algebra, and extremal combinatorics. We also show how differences in this geometry amount for the fact that undecidability does not hold for the normalized power sum map. Joint work with Jose Acevedo, Greg Blekherman, Sebastian Debus.

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.