Algebraic, Geometric, and Topological Combinatorics Abstracts

The k-random-to-random shuffle is a Markov chain that works as follows: one removes k cards from a deck at random and reinserts those k cards into new, uniformly random positions. To understand the convergence behavior of this process, one would like to know its eigenvalues—a surprisingly difficult question that remained open for more than a decade. It was resolved by Dieker–Saliola (k = 1) and Lafrenière (k > 1) in 2019, but the formulas for k > 1 were abstract enough that the second-largest eigenvalue was only conjectured.

In this talk, I will describe work with Commins, Grinberg, and Saliola that gives a q-deformation of this process to the type A Iwahori–Hecke algebra, where one may understand the parameter q as encoding a probability. We prove that the eigenvalues are always polynomials in q with nonnegative integer coefficients and can be expressed as certain evaluations of supersymmetric functions. This allows us to verify—and generalize—Lafrenière’s conjecture for the second-largest eigenvalue.

We introduce flag positroid pipe dreams (FPPs), combinatorial objects that serve a similar purpose for flag positroids as Le-diagrams do for positroids. FPPs are in bijection with intervals in the Bruhat order and hence index Richardson cells in the decomposition of the nonnegative flag variety. We give a characterization of quotients of flag positroids with consecutive ranks in terms of partial FPPs, and given a full FPP, we can recover the constituents of a full flag positroid in terms of their Le-diagrams. We also address a problem of Chen et al. on a characterization of positroid quotients in terms of the cyclic-shift operators of Benedetti, Chavez, and Tamayo.

A polygon P is pseudo-integral if, as in the case of integral polygons, the Ehrhart function of P is a polynomial. Such triangles arise in algebraic geometry, where their duals determine fake weighted projective planes, and in symplectic geometry, where they reveal the “staircase” structure of the minimum radius of embeddings of certain symplectic ellipsoids.

We prove that a rational pseudo-integral triangle with exactly one lattice point in its interior has at most 9 lattice points on its boundary, as with integral triangles. We further show that such a triangle never has exactly 7 lattice points on its boundary. In addition, we construct convex pseudo-integral polygons with i interior lattice points and b boundary lattice points for all positive integral values of (i,b) such that b ≤ 5i + 4. This contrasts with integral polygons, which must satisfy b ≤ 2i + 7 by a result of Scott. Computations by Bohnert confirm that when the vertices of P are all in ⅓ℤ², our construction attains the maximum possible number of boundary lattice points for pseudo-integral polygons with i ≤ 5 interior lattice points.

This is joint work with Jason Williford.

Homology classes in the complete flag variety GL_n/B correspond to linear functionals on the ring of symmetric coinvariants. In this talk, I will describe recent work with Nantel Bergeron, Lucas Gagnon, Philippe Nadeau, and Vasu Tewari on how linear maps between flag varieties corresponding to “setting variables to zero” give rise to an unusually combinatorially Schubert-positive subvariety of the flag variety—the “quasisymmetric flag variety.”

For an integer s ≥ 2, a subset S ⊆ [n] is s-stable if min{j − i, n + i − j} ≥ s for every i,j ∈ S with i < j. Denote the family of all s-stable subsets of size k of [n] by C_s(n,k). Schrijver proved in 1978 that whenever n ≥ 2k, the chromatic number of the Kneser graph KG(C₂(n,k)) is n − 2k + 2.

Generalizing this result, Meunier conjectured in 2011 that for all n ≥ sk, the corresponding chromatic number for s-stable sets is n − sk + s. The conjecture was proved by P. Chen for even s, and by J. Jonsson for s ≥ 4 and sufficiently large n. We prove the conjecture when s = 3 and n is sufficiently large, or when k = s = 3. To this end, we prove a version of the Hilton–Milner theorem for s-stable sets. We also present a topological approach toward Meunier’s conjecture.

Joint work with Wei-Chia Chen and Alex Parker.

The Robinson–Schensted (RS) correspondence admits diagrammatic interpretations via Fomin’s growth diagrams and Viennot’s shadow-line construction. Work of Spaltenstein, Springer, Steinberg, and van Leeuwen connected this combinatorial construction to the relative-position map of Springer fibers. Motivated by Kazhdan–Lusztig cell theory, various generalizations of the Robinson–Schensted correspondence to affine type A have been studied. Prominent examples include Shi’s insertion algorithm and the affine matrix-ball construction.

In this talk, we introduce a new combinatorial construction of the affine RS correspondence via growth diagrams and shadow lines that is, in a sense, dual to Shi’s insertion and the affine matrix-ball construction. We conjecture that the growth diagrams we construct admit a natural geometric realization in terms of relative positions of affine flags, similar to the interpretation given by Steinberg and van Leeuwen in the classical case.

Joint work with Sylvester Zhang.

We answer an old question of Anders Björner by providing a basis for the rank-selected homology of any geometric lattice. This basis, which we call the ribbon basis, is a matroid analogue of the polytabloid basis for a Specht module of ribbon shape. We prove that the action of Young symmetrizers on our ribbon basis satisfies a fundamental property of polytabloid bases. Using this feature of ribbon bases, we prove representation-theoretic stability for the rank-selected homology of both the Boolean lattice and the partition lattice, doing so in a way that gives sharp uniform representation-stability bounds in both cases. The sharp bound for the partition lattice proves a conjecture of Hersh and Reiner.

This is joint work with Sheila Sundaram.

We show that the toric ideal of the Fano matroid polytope does not have a quadratic Gröbner basis. This resolves in the negative a strong version of White’s conjecture from matroid theory. This result was found independently by De Loera, Ferroni, Morales, and Rambau.

Our approach is based on a new characterization of regular unimodular flag triangulations, which reduces the problem to an instance of SMT involving Boolean and real variables. We then use an SMT solver to prove unsatisfiability. Using this approach, we also show that all 8-element matroids that do not have the Fano matroid or its dual as a minor, with the possible exception of the matroid T₈, have toric ideals that admit quadratic Gröbner bases.

In recent years, the introduction of Chow rings of matroids has led to breakthroughs in matroid theory, including proofs of combinatorial inequalities such as the Heron–Rota–Welsh and Mason conjectures.

Chow polynomials of posets generalize the Hilbert–Poincaré polynomial of the Chow ring of matroids. While no such ring-theoretic interpretation is known for general posets, several properties surprisingly still hold for the coefficients of this polynomial, including positivity, unimodality, and palindromicity. This observation has led to the conjecture that Chow rings should also generalize to arbitrary posets and, among other requirements, satisfy the Hard Lefschetz property.

As a step toward this conjecture, we show that the Chow polynomial of any poset satisfies the numerical constraints imposed by the Hilbert series of Hard Lefschetz algebras. Consequently, for any poset there exists an algebra with the Hard Lefschetz property—and even the full Kähler package—that has the Chow polynomial as its Hilbert–Poincaré polynomial. Equivalently, this shows that the coefficients of the Chow polynomial are the h-vector of a simple polytope.

This is joint work with Adam Schweitzer.

Consider principal minors of positive-definite matrices. Is there a ratio of their products that is bounded for real symmetric positive-definite matrices but unbounded for complex Hermitian positive-definite matrices? I’ll discuss an answer involving tropical geometry, Grassmannians, matroids, and submodular functions.