Search

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

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

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 present a proof of a Littlewood–Richardson rule for the K-theory of odd orthogonal Grassmannians OG(n, 2n+1), as conjectured by Thomas–Yong (2009). Specifically, we prove that rectification using the jeu de taquin for increasing shifted tableaux introduced there, is well-defined and gives rise to an associative product. Recently, Buch–Ravikumar(2012) proved a Pieri rule for OG(n, 2n+1) that confirms a special case of the conjecture. Together, these results imply the aforementioned conjecture.

We present a randomized approximation algorithm for counting contingency tables , m × n non-negative integer matrices with given row sums R = ( r 1 ,…, r m ) and column sums C = ( c 1 ,…, c n ). We define smooth margins ( R , C ) in terms of the typical table and prove that for such margins the algorithm has quasi-polynomial N O (ln N ) complexity, where N = r 1 + … + r m = c 1 + … + c n . Various classes of margins are smooth, e.g., when m = O ( n ), n = O ( m ) and the ratios between the largest and the smallest row sums as well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1 + $ {sqrt{5}} $ )/2 ≈ 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log-concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010

We introduce a theory of jeu de taquin for increasing tableaux, extending fundamental work of Schützenberger (1977) for standard Young tableaux. We apply this to give a new combinatorial rule for the K-theory Schubert calculus of Grassmannians via K-theoretic jeu de taquin, providing an alternative to the rules of Buch and others. This rule naturally generalizes to give a conjectural root-system uniform rule for any minuscule flag variety G/P, extending recent work of Thomas and Yong. We also present analogues of results of Fomin, Haiman, Schensted and Schützenberger.

We present a combinatorial and computational commutative algebra methodology for studying singularities of Schubert varieties of flag manifolds. We define the combinatorial notion of *interval pattern avoidance*. For "reasonable" invariants P of singularities, we geometrically prove that this governs (1) the P-locus of a Schubert variety, and (2) which Schubert varieties are globally not P. The prototypical case is P="singular"; classical pattern avoidance applies admirably for this choice [Lakshmibai-Sandhya'90], but is insufficient in general. Our approach is analyzed for some common invariants, including Kazhdan-Lusztig polynomials, multiplicity, factoriality, and Gorensteinness, extending [Woo-Yong'05]; the description of the singular locus (which was independently proved by [Billey-Warrington '03], [Cortez '03], [Kassel-Lascoux-Reutenauer'03], [Manivel'01]) is also thus reinterpreted. Our methods are amenable to computer experimentation, based on computing with *Kazhdan-Lusztig ideals* (a class of generalized determinantal ideals) using Macaulay 2. This feature is supplemented by a collection of open problems and conjectures.

Fulton's universal Schubert polynomials give cohomology formulas for a class of degeneracy loci, which generalize Schubert varieties. The K-theoretic quiver formula of Buch expresses the structure sheaves of these loci as integral linear combinations of products of stable Grothendieck polynomials. We prove an explicit combinatorial formula for the coefficients, which shows that they have alternating signs. Our result is applied to obtain new expansions for the Grothendieck polynomials of Lascoux and Schützenberger.

Define a truncation rt (p) of a polynomial p in { x1,x2,x3,…} as the polynomial with all but the first t variables set to zero. In certain good cases, the truncation of a Schubert or Grothendieck polynomial may again be a Schubert or Grothendieck polynomial. We use this phenomenon to give subtraction-free formulas for certain Schubert structure constants in K ( Flags ( C^n)), in particular generalizing those studied by Kogan (2001) in which only cohomology was treated, and those studied by Buch (2002) on the Grassmannian case. The terms in the answer are computed using “marching” operations on permutation diagrams.

We prove a root system uniform, concise combinatorial rule for Schubert calculus of minuscule and cominuscule flag manifolds G/P (the latter are also known as compact Hermitian symmetric spaces). We connect this geometry to the poset combinatorics of Proctor, thereby giving a generalization of Schützenberger's jeu de taquin formulation of the Littlewood–Richardson rule that computes the intersection numbers of Grassmannian Schubert varieties. Our proof introduces cominuscule recursions, a general technique to relate the numbers for different Lie types.

We define and study the Plancherel–Hecke probability measure on Young diagrams; the Hecke algorithm of Buch–Kresch–Shimozono–Tamvakis–Yong is interpreted as a polynomial-time exact sampling algorithm for this measure. Using the results of Thomas–Yong on jeu de taquin for increasing tableaux, a symmetry property of the Hecke algorithm is proved, in terms of longest strictly increasing/decreasing subsequences of words. This parallels classical theorems of Schensted and of Knuth, respectively, on the Schensted and Robinson–Schensted–Knuth algorithms. We investigate, and conjecture about, the limit typical shape of the measure, in analogy with work of Vershik–Kerov, Logan–Shepp and others on the “longest increasing subsequence problem” for permutations. We also include a related extension of Aldous–Diaconis on patience sorting. Together, these results provide a new rationale for the study of increasing tableau combinatorics, distinct from the original algebraic-geometric ones concerning K-theoretic Schubert calculus.

We present a proof of a Littlewood–Richardson rule for the K-theory of odd orthogonal Grassmannians OG(n, 2n+1), as conjectured by Thomas–Yong (2009). Specifically, we prove that rectification using the jeu de taquin for increasing shifted tableaux introduced there, is well-defined and gives rise to an associative product. Recently, Buch–Ravikumar(2012) proved a Pieri rule for OG(n, 2n+1) that confirms a special case of the conjecture. Together, these results imply the aforementioned conjecture.

We define and study the Plancherel–Hecke probability measure on Young diagrams; the Hecke algorithm of Buch–Kresch–Shimozono–Tamvakis–Yong is interpreted as a polynomial-time exact sampling algorithm for this measure. Using the results of Thomas–Yong on jeu de taquin for increasing tableaux, a symmetry property of the Hecke algorithm is proved, in terms of longest strictly increasing/decreasing subsequences of words. This parallels classical theorems of Schensted and of Knuth, respectively, on the Schensted and Robinson–Schensted–Knuth algorithms. We investigate, and conjecture about, the limit typical shape of the measure, in analogy with work of Vershik–Kerov, Logan–Shepp and others on the “longest increasing subsequence problem” for permutations. We also include a related extension of Aldous–Diaconis on patience sorting. Together, these results provide a new rationale for the study of increasing tableau combinatorics, distinct from the original algebraic-geometric ones concerning K-theoretic Schubert calculus.

We prove a root system uniform, concise combinatorial rule for Schubert calculus of minuscule and cominuscule flag manifolds G/P (the latter are also known as compact Hermitian symmetric spaces). We connect this geometry to the poset combinatorics of Proctor, thereby giving a generalization of Schützenberger's jeu de taquin formulation of the Littlewood–Richardson rule that computes the intersection numbers of Grassmannian Schubert varieties. Our proof introduces cominuscule recursions, a general technique to relate the numbers for different Lie types.

We introduce a theory of jeu de taquin for increasing tableaux, extending fundamental work of Schützenberger (1977) for standard Young tableaux. We apply this to give a new combinatorial rule for the K-theory Schubert calculus of Grassmannians via K-theoretic jeu de taquin, providing an alternative to the rules of Buch and others. This rule naturally generalizes to give a conjectural root-system uniform rule for any minuscule flag variety G/P, extending recent work of Thomas and Yong. We also present analogues of results of Fomin, Haiman, Schensted and Schützenberger.