Search

The Robinson-Schensted-Knuth correspondence (RSK) is a bijection between nonnegative integer matrices and pairs of Young tableaux. We study it as a linear operator on the coordinate ring of matrices., Comment: 36 pages

Matrix Schubert varieties (Fulton '92) carry natural actions of Levi groups. Their coordinate rings are thereby Levi-representations; what is a combinatorial counting rule for the multiplicities of their irreducibles? When the Levi group is a torus, (Knutson-Miller '04) answers the question. We present a general solution, a common refinement of the multigraded Hilbert series, the Cauchy identity, and the Littlewood-Richardson rule. Our result applies to any ``bicrystalline'' algebraic variety; we define these using the operators of (Kashiwara '95) and of (Danilov-Koshevoi '05, van Leeuwen '06). The proof introduces a ``filtered'' generalization of the Robinson-Schensted-Knuth correspondence., Comment: 32 pages

An algorithm is presented that generates sets of size equal to the degree of a given variety defined by a homogeneous ideal. This algorithm suggests a versatile framework to study various problems in combinatorial algebraic geometry and related fields., Comment: 15 pages

Abhyankar defined an ideal to be Hilbertian if its Hilbert polynomial coincides with its Hilbert function for all nonnegative integers. In 1984, he proved that the ideal of (r+1)-order minors of a generic p x q matrix is Hilbertian. We give a different proof and a generalization to the Schubert determinantal ideals introduced by Fulton in 1992. Our proof reduces to a simple upper bound for the Castelnuovo-Mumford regularity of these ideals. We further indicate the pervasiveness of the Hilbertian property in Schubert geometry., Comment: With thanks to Allen Knutson and Jenna Rajchgot for feedback about v1, v2 contains additional results and background material. 12 pages

We prove a short, root-system uniform, combinatorial classification of Levi-spherical Schubert varieties for any generalized flag variety $G/B$ of finite Lie type. We apply this to the study of multiplicity-free decompositions of a Demazure module into irreducible representations of a Levi subgroup., Comment: 11 pages. Minor corrections made in v2. To appear in Advances in Mathematics

This chapter combines an introduction and research survey about Schubert varieties. The theme is to combinatorially classify their singularities using a family of polynomial ideals generated by determinants., Comment: 58 pages

A minimal presentation of the cohomology ring of the flag manifold $GL_n/B$ was given in [A. Borel, 1953]. This presentation was extended by [E. Akyildiz-A. Lascoux-P. Pragacz, 1992] to a non-minimal one for all Schubert varieties. Work of [Gasharov-Reiner, 2002] gave a short, i.e. polynomial-size, presentation for a subclass of Schubert varieties that includes the smooth ones. In [V. Reiner-A. Woo-A. Yong, 2011], a general shortening was found; it implies an exponential upper bound of $2^n$ on the number of generators required. That work states a minimality conjecture whose significance would be an exponential lower bound of $\sqrt{2}^{n+2}/\sqrt{\pi n}$ on the number of generators needed in worst case, giving the first obstructions to short presentations. We prove the minimality conjecture. Our proof uses the Hopf algebra structure of the ring of symmetric functions., Comment: 19 pages, 4 figures, to appear in J. London. Math. Soc

We study the Castelnuovo-Mumford regularity of tangent cones of Schubert varieties. Conjectures about this statistic are presented; these are proved for the covexillary case. This builds on work of L. Li and the author on these tangent cones, as well as that of J. Rajchgot-Y. Ren-C. Robichaux-A. St. Dizier-A. Weigandt and J. Rajchgot-C. Robichaux-A. Weigandt on tableau rules for computing regularity of some matrix Schubert varieties., Comment: 10 pages

Explicit minimal generators for Fulton's Schubert determinantal ideals are determined along with some implications., Comment: 6 pages

The Newell-Littlewood numbers are tensor product multiplicities of Weyl modules for the classical groups in the stable range. Littlewood-Richardson coefficients form a special case. Klyachko connected eigenvalues of sums of Hermitian matrices to the saturated LR-cone and established defining linear inequalities. We prove analogues for the saturated NL-cone: an eigenvalue interpretation; a minimal list of defining linear inequalities; a description by Extended Horn inequalities, as conjectured in part II of this series; and a factorization of NL-numbers, on the boundary., Comment: 21 pagesv2 has a significantly shorter argument for a stronger version of Theorem 1.5, using a result of R. King

A Schubert variety in the complete flag manifold $GL_n/B$ is Levi-spherical if the action of a Borel subgroup in a Levi subgroup of a standard parabolic has a dense orbit. We give a combinatorial classification of these Schubert varieties. This establishes a conjecture of the latter two authors, and a new formulation in terms of standard Coxeter elements. Our proof uses the theory of key polynomials (type A Demazure module characters)., Comment: 30 pages

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 x n grid. In contrast, we show that computing these coefficients explicitly is #P-complete., Comment: 30 pages. This paper was split off from 1810.10361v1, with a new title and abstract. That earlier preprint has been replaced by a conference proceedings version 1810.10361v2, with a different title and abstract; it contains complexity discussion and a related conjecture not found here. To appear in Advances in Math

This report formulates a conjectural combinatorial rule that positively expands Grothendieck polynomials into Lascoux polynomials. It generalizes one such formula expanding Schubert polynomials into key polynomials, and refines another one expanding stable Grothendieck polynomials., Comment: 9 pages

The Kostka semigroup consists of pairs of partitions with at most r parts that have positive Kostka coefficient. For this semigroup, Hilbert basis membership is an NP-complete problem. We introduce KGR graphs and conservative subtrees, through the Gale-Ryser theorem on contingency tables, as a criterion for membership. In our main application, we show that if a partition pair is in the Hilbert basis then the partitions are at most r wide. We also classify the extremal rays of the associated polyhedral cone; these rays correspond to a (strict) subset of the Hilbert basis. In an appendix, the second and third authors show that a natural extension of our main result on the Kostka semigroup cannot be extended to the Littlewood-Richardson semigroup. This furthermore gives a counterexample to a recent speculation of P. Belkale concerning the semigroup controlling nonvanishing conformal blocks., Comment: 27 pages. Conjectures 5.3 and 5.5 have been recently resolved in the affirmative by J. Kim (arXiv:2105.07015). Conjecture 5.8 has been resolved in the negative by the second and third authors in a new Appendix B. This furthermore resolves in the negative a recent speculation of P. Belkale (arXiv:2005.12457v3)

We define and study proper permutations. Properness is a geometrically natural necessary criterion for a Schubert variety to be Levi-spherical. We prove the probability that a random permutation is proper goes to zero in the limit., Comment: 8 pages

We connect generalized permutahedra with Schubert calculus. Thereby, we give sufficient vanishing criteria for Schubert intersection numbers of the flag variety. Our argument utilizes recent developments in the study of Schubitopes, which are Newton polytopes of Schubert polynomials. The resulting tableau test executes in polynomial time., Comment: 13 pages

The Newell-Littlewood numbers $N_{\mu,\nu,\lambda}$ are tensor product multiplicities of Weyl modules for classical Lie groups, in the stable limit. For which triples of partitions $(\mu,\nu,\lambda)$ does $N_{\mu,\nu,\lambda}>0$ hold? The Littlewood-Richardson coefficient case is solved by the Horn inequalities (in work of A. Klyachko and A. Knutson-T. Tao). We extend these celebrated linear inequalities to a much larger family, suggesting a general solution., Comment: 11 pages. To appear in Algebraic Combinatorics

The key polynomials, defined by A. Lascoux-M.-P. Sch\"utzenberger, are characters for the Demazure modules of type A. We classify multiplicity-free key polynomials. The proof uses two combinatorial models for key polynomials. The first is due to A. Kohnert. The second is by S. Assaf-D. Searles, in terms of quasi-key polynomials. Our argument proves a sufficient condition for a quasi-key polynomial to be multiplicity-free., Comment: 20 pages

For a finite Coxeter system and a subset of its diagram nodes, we define spherical elements (a generalization of Coxeter elements). Conjecturally, for Weyl groups, spherical elements index Schubert varieties in a flag manifold G/B that are spherical for the action of a Levi subgroup. We evidence the conjecture, employing the combinatorics of Demazure modules, and work of R. Avdeev-A. Petukhov, M. Can-R. Hodges, R. Hodges-V. Lakshmibai, P. Karuppuchamy, P. Magyar-J. Weyman-A. Zelevinsky, N. Perrin, J. Stembridge, and B. Tenner. In type A, we establish connections with the key polynomials of A. Lascoux- M.-P. Sch\"utzenberger, multiplicity-freeness, and split-symmetry in algebraic combinatorics. Thereby, we invoke theorems of A. Kohnert, V. Reiner-M. Shimozono, and C. Ross-A. Yong., Comment: 27 pages, corrections made to examples 1.4, 1.5, 2.16. Minor corrections made in v3. To appear in Journal of Lie Theory

The Newell-Littlewood numbers are defined in terms of their celebrated cousins, the Littlewood-Richardson coefficients. Both arise as tensor product multiplicities for a classical Lie group. They are the structure coefficients of the K. Koike-I. Terada basis of the ring of symmetric functions. Recent work of H. Hahn studies them, motivated by R. Langlands' beyond endoscopy proposal; we address her work with a simple characterization of detection of Weyl modules. This motivates further study of the combinatorics of the numbers. We consider analogues of ideas of J. De Loera-T. McAllister, H. Derksen-J. Weyman, S. Fomin-W. Fulton-C.-K. Li-Y.-T. Poon, W. Fulton, R. King-C. Tollu-F. Toumazet, M. Kleber, A. Klyachko, A. Knutson-T. Tao, T. Lam-A. Postnikov-P. Pylyavskyy, K. Mulmuley-H. Narayanan-M. Sohoni, H. Narayanan, A. Okounkov, J. Stembridge, and H. Weyl., Comment: 35 pages

This chapter concerns edge labeled Young tableaux, introduced by H. Thomas and the third author. It is used to model equivariant Schubert calculus of Grassmannians. We survey results, problems, conjectures, together with their influences from combinatorics, algebraic and symplectic geometry, linear algebra, and computational complexity. We report on a new shifted analogue of edge labeled tableaux. Conjecturally, this gives a Littlewood-Richardson rule for the structure constants of the D. Anderson-W. Fulton ring, which is related to the equivariant cohomology of isotropic Grassmannians., Comment: 39 pages

We collect Atiyah-Bott Combinatorial Dreams (A.B.C.Ds) in Schubert calculus. One result relates equivariant structure coefficients for two isotropic flag manifolds, with consequences to the thesis of C. Monical. We contextualize using work of N. Bergeron-F. Sottile, S. Billey-M. Haiman, P. Pragacz, and T. Ikeda-L. Mihalcea-I. Naruse. The relation complements a theorem of A. Kresch-H. Tamvakis in quantum cohomology. Results of A. Buch-V. Ravikumar rule out a similar correspondence in K-theory., Comment: 11 pages

We looked at a method for estimating the complexity measure of game tree size (the number of legal games). It seems effective for a number of children's games such as Tic-Tac-Toe, Connect Four and Othello., Comment: 4 pages

A reduced word of a permutation $w$ is a minimal length expression of $w$ as a product of simple transpositions. We examine the computational complexity, formulas and (randomized) algorithms for their enumeration. In particular, we prove that the Edelman-Greene statistic, defined by S. Billey-B. Pawlowski, is typically exponentially large. This implies a result of B. Pawlowski, that it has exponentially growing expectation. Our result is established by a formal run-time analysis of A. Lascoux-M.-P. Sch\"utzenberger's transition algorithm. The more general problem of Hecke word enumeration, and its closely related question of counting set-valued standard Young tableaux, is also investigated. The latter enumeration problem is further motivated by work on Brill-Noether varieties due to M. Chan-N. Pflueger and D. Anderson-L. Chen-N. Tarasca., Comment: 23 pages. v2: added reference to University of Washington PhD thesis of B. Pawlowski, which proves a stronger version of Theorem 1.1

The nonvanishing problem asks if a coefficient of a polynomial is nonzero. Many families of polynomials in algebraic combinatorics admit combinatorial counting rules and simultaneously enjoy having saturated Newton polytopes (SNP). Thereby, in amenable cases, nonvanishing is in the complexity class $NP\cap coNP$ of problems with "good characterizations". This suggests a new algebraic combinatorics viewpoint on complexity theory. This report discusses the case of Schubert polynomials. These form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. We give a tableau criterion for nonvanishing, 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 x n grid, together with a theorem of A. Fink, K. M\'{e}sz\'{a}ros, and A. St. Dizier, which proved a conjecture of C. Monical, N. Tokcan, and the third author., Comment: 12 pages. v2 is the conference proceedings version. The remaining material of v1 (proofs, the theorem on #P-completeness) is split off into a subsequent arXiv post. That post has a different title ("An efficient algorithm for deciding vanishing of Schubert polynomial coefficients"), abstract, and discussion of the general "nonvanishing problem" removed

D. Grigoriev-G. Koshevoy recently proved that tropical Schur polynomials have (at worst) polynomial tropical semiring complexity. They also conjectured tropical skew Schur polynomials have at least exponential complexity; we establish a polynomial complexity upper bound. Our proof uses results about (stable) Schubert polynomials, due to R. P. Stanley and S. Billey-W. Jockusch-R. P. Stanley, together with a sufficient condition for polynomial complexity that is connected to the saturated Newton polytope property., Comment: 8 pages

We define the Barbasch-Evens-Magyar varieties. We show they are isomorphic to the smooth varieties defined in [D.~Barbasch-S.~Evens '94] that map generically finitely to symmetric orbit closures, thereby giving resolutions of singularities in certain cases. Our definition parallels [P.~Magyar '98]'s construction of the Bott-Samelson varieties [H.~C.~Hansen '73, M.~Demazure '74]. From this alternative viewpoint, one deduces a graphical description in type $A$, stratification into closed subvarieties of the same kind, and determination of the torus-fixed points. Moreover, we explain how these manifolds inherit a natural symplectic structure with Hamiltonian torus action. We then express the moment polytope in terms of the moment polytope of a Bott-Samelson variety., Comment: 22 pages, 5 figures. Accepted for publication at Pacific J. Math

J. DeLoera-T. McAllister and K. D. Mulmuley-H. Narayanan-M. Sohoni independently proved that determining the vanishing of Littlewood-Richardson coefficients has strongly polynomial time computational complexity. Viewing these as Schubert calculus numbers, we prove the generalization to the Littlewood-Richardson polynomials that control equivariant cohomology of Grassmannians. We construct a polytope using the edge-labeled tableau rule of H. Thomas-A. Yong. Our proof then combines a saturation theorem of D. Anderson-E. Richmond-A. Yong, a reading order independence property, and E. Tardos' algorithm for combinatorial linear programming., Comment: 10 pages

We discuss implications of the following statement about the representation theory of symmetric groups: every integer appears infinitely often as an irreducible character evaluation, and every nonnegative integer appears infinitely often as a Littlewood-Richardson coefficient and as a Kronecker coefficient., Comment: 4 pages

Symmetric Grothendieck polynomials are inhomogeneous versions of Schur polynomials that arise in combinatorial $K$-theory. A polynomial has saturated Newton polytope (SNP) if every lattice point in the polytope is an exponent vector. We show Newton polytopes of these Grothendieck polynomials and their homogeneous components have SNP. Moreover, the Newton polytope of each homogeneous component is a permutahedron. This addresses recent conjectures of C. Monical-N. Tokcan-A. Yong and of A. Fink-K. M\'esz\'aros-A. St. Dizier in this special case., Comment: 4 pages, 1 figure

A polynomial has saturated Newton polytope (SNP) if every lattice point of the convex hull of its exponent vectors corresponds to a monomial. We compile instances of SNP in algebraic combinatorics (some with proofs, others conjecturally): skew Schur polynomials; symmetric polynomials associated to reduced words, Redfield--Polya theory, Witt vectors, and totally nonnegative matrices; resultants; discriminants (up to quartics); Macdonald polynomials; key polynomials; Demazure atoms; Schubert polynomials; and Grothendieck polynomials, among others. Our principal construction is the Schubitope. For any subset of [n] x [n], we describe it by linear inequalities. This generalized permutahedron conjecturally has positive Ehrhart polynomial. We conjecture it describes the Newton polytope of Schubert and key polynomials. We also define dominance order on permutations and study its poset-theoretic properties., Comment: 30 pages

We develop interval pattern avoidance and Mars-Springer ideals to study singularities of symmetric orbit closures in a flag variety. This paper focuses on the case of the Levi subgroup GL_p x GL_q acting on the classical flag variety. We prove that all reasonable singularity properties can be classified in terms of interval patterns of clans., Comment: 47 pages

We present a particular connection between classical partition combinatorics and the theory of quiver representations. Specifically, we give a bijective proof of an analogue of A. L. Cauchy's Durfee square identity to multipartitions. We then use this result to give a new proof of M. Reineke's identity in the case of quivers $Q$ of Dynkin type $A$ of arbitrary orientation. Our identity is stated in terms of the lacing diagrams of S. Abeasis - A. Del Fra, which parameterize orbits of the representation space of $Q$ for a fixed dimension vector., Comment: 26 pages

S.~Elnitsky (1997) gave an elegant bijection between rhombic tilings of $2n$-gons and commutation classes of reduced words in the symmetric group on $n$ letters. P.~Magyar (1998) found an important construction of the Bott-Samelson varieties introduced by H.C.~Hansen (1973) and M.~Demazure (1974). We explain a natural connection between S.~Elnitsky's and P.~Magyar's results. This suggests using tilings to encapsulate Bott-Samelson data (in type $A$). It also indicates a geometric perspective on S.~Elnitsky's combinatorics. We also extend this construction by assigning desingularizations to the zonotopal tilings considered by B.~Tenner (2006)., Comment: 9 pages, 5 figures; results and authors added

In certain finite posets, the expected down-degree of their elements is the same whether computed with respect to either the uniform distribution or the distribution weighting an element by the number of maximal chains passing through it. We show that this coincidence of expectations holds for Cartesian products of chains, connected minuscule posets, weak Bruhat orders on finite Coxeter groups, certain lower intervals in Young's lattice, and certain lower intervals in the weak Bruhat order below dominant permutations. Our tools involve formulas for counting nearly reduced factorizations in 0-Hecke algebras; that is, factorizations that are one letter longer than the Coxeter group length., Comment: to appear in Journal of Combinatorial Theory, Series A

We explain how genomic tableaux [Pechenik-Yong '15] are a semistandard complement to increasing tableaux [Thomas-Yong '09]. From this perspective, one inherits genomic versions of jeu de taquin, Knuth equivalence, infusion and Bender-Knuth involutions, as well as Schur functions from (shifted) semistandard Young tableaux theory. These are applied to obtain new Littlewood-Richardson rules for K-theory Schubert calculus of Grassmannians (after [Buch '02]) and maximal orthogonal Grassmannians (after [Clifford-Thomas-Yong '14], [Buch-Ravikumar '12]). For the unsolved case of Lagrangian Grassmannians, sharp upper and lower bounds using genomic tableaux are conjectured., Comment: 30 pages, color figures

The Schubert polynomials lift the Schur basis of symmetric polynomials into a basis for Z[x1,x2,...]. We suggest the "prism tableau model" for these polynomials. A novel aspect of this alternative to earlier results is that it directly invokes semistandard tableaux; it does so as part of a colored tableau amalgam. In the Grassmannian case, a prism tableau with colors ignored is a semistandard Young tableau. Our arguments are developed from the Groebner geometry of matrix Schubert varieties., Comment: 23 pages

In 2005, A. Knutson--R. Vakil conjectured a puzzle rule for equivariant K-theory of Grassmannians. We resolve this conjecture. After giving a correction, we establish a modified rule by combinatorially connecting it to the authors' recently proved tableau rule for the same Schubert calculus problem., Comment: 11 pages. Significant use of color figures

We address a unification of the Schubert calculus problems solved by [A. Buch '02] and [A. Knutson-T. Tao '03]. That is, we prove a combinatorial rule for the structure coefficients in the torus-equivariant K-theory of Grassmannians with respect to the basis of Schubert structure sheaves. We thereby deduce the conjectural rule of [H. Thomas-A. Yong '13] for the same coefficients. Both rules are positive in the sense of [D. Anderson-S. Griffeth-E. Miller '11] (and moreover in a stronger form). Our work is based on the combinatorics of genomic tableaux and a generalization of [M.-P. Schutzenberger '77]'s jeu de taquin., Comment: 93 pages