Papers etc. by Alexander Yong

28. An approximation algorithm for contingency tables (with Alexander Barvinok, Zur Luria and Alex Samorodnitsky), submitted (45 pages), 03/27/08.

We present a randomized approximation algorithm for counting contingency tables, m x 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.

Update (July, 2006): My coauthor A. Barvinok has further studied the typical table in his paper.

We define and study the Plancherel-Hecke probability measure on Young diagrams; the Hecke algorithm of [Buch-Kresch-Shimozono-Tamvakis-Yong '06] is interpreted as a polynomial-time exact sampling algorithm for this measure. Using the results of [Thomas-Yong '07] 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 '61] and of [Knuth '70], 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 '77], [Logan-Shepp '77] and others on the ``longest increasing subsequence problem'' for permutations. We also include a related extension of [Aldous-Diaconis '99] 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 introduce a theory of jeu de taquin for increasing tableaux, extending fundamental work of [Sch\"{u}tzenberger '77] 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 '02] and others. This rule naturally generalizes to give a conjectural root-system uniform rule for any minuscule flag variety $G/P$, extending [Thomas-Yong '06]. We also present positive and negative results concerning analogues of ideas of Fomin, Haiman, Schensted and Sch\"{u}tzenberger.

25. An S_3 symmetric Littlewood-Richardson rule (with Hugh Thomas), Mathematical Research Letters , to appear, 2008; (9 pages).

The classical Littlewood-Richardson coefficients C(lambda,mu,nu) carry a natural $S_3$ symmetry via permutation of indices. Our ``carton rule'' for computing these numbers transparently and uniformly explains these six symmetries; previously formulated Littlewood-Richardson rules manifest at most three of the six.

24. Counting magic squares in quasi-polynomial time (with Alexander Barvinok and Alexander Samorodnitsky), preprint (30 pages), 2007.
Companion Maple code contingency.txt. Here is a supplemental webpage comparing various ways of enumerating contingency tables and magic squares.

We present a randomized algorithm, which, given positive integers $n$ and $t$ and a real number 0< &epsilon <1 computes the number |&Sigma(n, t)| of n x n non-negative integer matrices (magic squares) with the row and column sums equal to t within relative error &epsilon. The computational complexity of the algorithm is polynomial in &epsilon^{-1} and quasi-polynomial in N=nt, that is, of the order N^(log(N)). A simplified version of the algorithm works in time polynomial in &epsilon^{-1} and N and estimates |&Sigma(n, t)| within a factor of N^(log(N)). This simplified version has been implemented. We present results of the implementation, state some conjectures, and discuss possible generalizations.

23. Ecological coalescent theory and particle systems (with Nicolas Lanchier and Claudia Neuhauser), preprint.

22. Cominuscule tableau combinatorics (with Hugh Thomas), submitted, 2007. Here is the Maple code to check Lemma 2.4 for Lie types E6 and E7.

We continue our study of "cominuscule tableau combinatorics" by generalizing constructions of M. Haiman, S. Fomin and M.-P. Schützenberger. In particular, we extend the "dual equivalence" ideas of [Haiman, 1992] to reformulate the generalized Littlewood-Richardson rule for cominuscule G/P Schubert calculus from [Thomas-Yong, 2006]; this reformulation avoids certain arbitrary choices demanded by the original version. Also, we apply dual equivalence to give an alternative and independent proof of the jeu de taquin results of [Proctor, 2004] needed in our earlier work. Further, we extend Fomin's "growth diagram" description of jeu de taquin; the inherent symmetry of these diagrams leads to a generalization of Schützenberger's "evacuation involution".

We think of these results as characteristic of our viewpoint that the tableau combinatorics making the cohomology of Grassmannians attractive should have natural cominuscule generalizations. This principle incorporates the standard maxim that the Young tableau combinatorics of Schur polynomials should have "shifted analogues" for Schur $P-$ and $Q-$ polynomials (although this is often used with representation theory of the symmetric group, rather than geometry of flag manifolds, in mind).

21. What is a Young tableau?
Notices of the AMS , Volume 54, Number 2, February 2007.

A short expository piece on Young tableaux and their basic theorems.

20. A combinatorial rule for (co)minuscule Schubert calculus (with Hugh Thomas), accepted to Advances in Math , pending minor revisions, 2007.
Companion Maple code cominrule.v1.0.txt. Here's an extra note about comparing cominrule.v1.0.txt with Schubert.v0.2.txt, given below.

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 '04], thereby giving a generalization of the [Sch\"{u}tzenberger `77] jeu de taquin formulation of the Littlewood-Richardson rule, which computes the intersection numbers of Grassmannian Schubert varieties. Our proof introduces _cominuscule recursions_, a general technique to relate the numbers for different Lie types. A discussion about connections of the rule to (geometric) representation theory is also briefly entertained.

19. Stable Grothendieck polynomials and K-theoretic factor sequences (full version) (with A. Buch, A. Kresch, M. Shimzono and H. Tamvakis), accepted to Math. Annalen, 2007.

We formulate a nonrecursive combinatorial rule for the expansion of the stable Grothendieck polynomials of [Fomin-Kirillov '94] in the basis of stable Grothendieck polynomials for partitions. This gives a common generalization, as well as new proofs of the rule of [Fomin-Greene '98] for the expansion of the stable Schubert polynomials into Schur polynomials, and the $K$-theoretic Grassmannian Littlewood-Richardson rule of [Buch '02].

Our main technique is a generalization of the Robinson-Schensted and Edelman-Greene insertion algorithms. Our results are applied to prove a number of new formulas and properties for K-theoretic quiver polynomials, and the Grothendieck polynomials of [Lascoux-Sch\"{u}tzenberger '82]. In particular, we provide the first $K$-theoretic analogue of the factor sequence formula of [Buch-Fulton '99] for the cohomological quiver polynomials.

This is the complete version of the announcement (presented at FPSAC 2005).

18. Tableau complexes (with A. Knutson and E. Miller), to appear in Israel Journal of Math , 163 (2008), 317-343. A picture (due to A. Knutson).

Let X, Y be finite sets and T a set of functions from X->Y, which we will call ``tableaux''. We define a simplicial complex whose facets, all the same dimension, correspond to these tableaux, and call it a ``tableau complex''. Tableau complexes have many nice properties, and are frequently homeomorphic to balls, which we prove using vertex decompositions of Billera-Provan.

In our motivating example, the facets are labeled by semistandard Young tableaux, and the interior faces by Buch's ``set-valued'' semistandard tableaux. In the Young tableaux case, one such vertex decomposition parallels Lascoux's transition formula for vexillary double Grothendieck polynomials. Consequently, we obtain formulae (both old and new) for these polynomials. In particular, we present a common generalization of the formulae of Wachs and Buch, each of which imply the classical tableau formula for Schur polynomials.

17. Multiplicity-free Schubert calculus (with H. Thomas), to appear in Canadian Math. Bulletin, 2007.

We give a short combinatorial classification of which products of Schubert classes in the Grassmannian are multiplicity-free. This answers a question of W. Fulton, and extends work of J. Stembridge.

16. Governing singularities of Schubert varieties (with A. Woo), accepted Journal of Algebra (section on computational algebra), 2007.
Companion Macaulay 2 code Schubsingular.v0.2.m2

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'04]; 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.

Update (Nov 11, 2006): 1. My coauthor A. Woo has extended the interval pattern avoidance ideas of the above paper here.

Update (April 6, 2007): N. Perrin has proved our Gorenstein locus conjecture for the case of minuscule G/P flag varieties. See this paper.

15. Grobner geometry of vertex decompositions and of flagged tableaux (with A. Knutson and E. Miller), Journal fur die reine und angewandte Mathematik (Crelle's Journal) , accepted, 2007.

We relate a classic algebro-geometric degeneration technique, dating at least to [Hodge 1941], to the notion of vertex decompositions of simplicial complexes. The good case is when the degeneration is reduced, and we call this a geometric vertex decomposition .

Our main example is the family of vexillary matrix Schubert varieties , whose ideals are also known as (one-sided) ladder determinantal ideals. We show that these have geometric vertex decompositions into simpler varieties of the same type. From this, together with the combinatorics of the pipe dreams of [Fomin--Kirillov 1996], we derive a new formula for the numerators of their multigraded Hilbert series, the double Grothendieck polynomials, in terms of flagged set-valued tableaux . This unifies work of [Wachs 1985] on flagged tableaux, and [Buch 2002] on set-valued tableaux, giving geometric meaning to both.

This work focuses on diagonal term orders, giving results that complement those of [Knutson--Miller 2004], where it was shown that the generating minors form a Groebner basis for any antidiagonal term order and any matrix Schubert variety. We show here that under a diagonal term order, the only matrix Schubert varieties for which these minors form Groebner bases are the vexillary ones, reaching an end toward which the ladder determinantal literature had been building.

14. When is a Schubert variety Gorenstein? (with A. Woo),
Advances in Math , Vol 207 (2006), Issue 1 205--220. Companion Maple code available.

A variety is Gorenstein if it is Cohen-Macaulay and its canonical sheaf is a line bundle. This property, which measures the ``pathology'' of the singularities of a variety, is thus stronger than Cohen-Macaulayness, but is also weaker than smoothness. We determine which Schubert varieties are Gorenstein in terms of a combinatorial characterization using generalized pattern avoidance conditions. We also give an explicit description as a line bundle of the canonical sheaf of a Gorenstein Schubert variety.

13. Truncation Schubert calculus formulae for isotropic flag manifolds (with F. Sottile), in preparation.

12. Grobner geometry of Schubert transition formulae and Littlewood-Richardson rules (with A. Knutson), preprint.

See slides for a talk which discusses this (as well as related work below).

11. A formula for K-theory truncation Schubert calculus (with A. Knutson),
International Mathematics Research Notices , 70 (2004), 3741-3756.

Define a truncation r_{t}(p) of a polynomial p in {x_1,x_2,...} 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 formulae for certain Schubert structure constants in K(Flags(C^n)), in particular generalizing those from [Kogan, '00] in which only cohomology was treated, and from [Buch, '02] on the Grassmannian case. The terms in the answer are computed using "marching" operations on permutation diagrams.

10. Lecture notes on the K-theory of the flag variety and the Fomin-Kirillov quadratic algebra (with C. Lenart), 2004.

We contribute to the study of the Fomin-Kirillov quadratic algebra, in connection with the Schubert calculus of the flag variety. We construct a commutative subalgebra and explain the (conjectural) connection to the K-theory ring of the flag variety and the associated Schubert structure constants.

These are extended lecture notes based on talks given by my coauthor Cristian Lenart at the University of Michigan Combinatorics Seminar and at the Combinatorial Commutatative Algebra section of the San Francisco AMS meeting, April 2003.

Update (Feb 12, 2006): 1. My coauthor C. Lenart has reported on our work in his paper "K-theory of the flag variety and the Fomin-Kirillov quadratic algebra" (published in the Journal of Algebra). 2. Conjecture 3.5 of our text above (as also reported in Lenart's paper) has been proved by A.N. Kirillov and T. Maeno (published in IMRN).

9. Quiver coefficients are Schubert structure constants (with A. Buch and F. Sottile),
Mathematical Research Letters , Volume 12, Issue 4, 567-574 (2005).

We give an explicit natural identification between the quiver coefficients of Buch and Fulton, the Schubert splitting coefficients studied in "Schubert polynomials and quiver formulas" (see below), and the Schubert structure constants for flag manifolds. More generally this is achieved in K-theory. This leads to a new explanation of the alternation in sign of the K-theory quiver coefficients (via a theorem of Brion) as well as new combinatorial formulas for what they count.

8. Grothendieck polynomials and Quiver formulas (with A. Buch, A. Kresch and H. Tamvakis),
American Journal of Math , 127 (2005), 551-567.

We give a formula that proves that ``splitting coefficients'' for Grothendieck polynomials alternate in sign according to degree. Recently, work of A. Buch implies that the quiver coefficients of Buch and Fulton, as well as the K-quiver coefficients of Buch may be realized as special cases of these splitting coefficients. Our main tool is a new Cauchy formula for ``Universal Grothendieck polynomials'', which represents the structure sheaf of a general type of degeneracy loci for maps of vector bundles over a nonsingular variety X, and whose rank conditions come from a permutation. We also show that the monomial coefficients for the Grothendieck polynomials of Fomin-Kirillov are naturally K-quiver coefficients.

7. On Combinatorics of Degeneracy Loci and H*(G/B), a dissertation submitted to the Rackham graduate school, University of Michigan, 2003. Companion Maple code for part 2 available. (Includes an implementation of the classical Monk-Chevalley formula for arbitrary Lie type.)

Contains: 1. the content of the paper 6 below; 2. a Grobner based construction of an alternative (combinatorial) linear basis for H*(G/B) related to the Schubert calculus of a generalized flag manifold.

6. On Combinatorics of Quiver Component Formulas,
Journal of Algebraic Combinatorics , 21, 351-371, 2005.

Buch and Fulton conjectured the nonnegativity of the quiver coefficients appearing in their formula for a quiver variety. Knutson, Miller and Shimozono proved this conjecture as an immediate consequence of their ``component formula''. We present an alternative proof of the component formula by substituting combinatorics for Grobner degeneration. We relate the component formula to the work of Buch, Kresch, Tamvakis and the author, where a ``splitting'' formula for Schubert polynomials in terms of quiver coefficients was obtained. We prove analogues of this latter result for the type BCD-Schubert polynomials of Billey and Haiman. The shape of these formulas suggests that it should be interesting to pursue the underlying geometry (degeneracy locus/Schubert calculus).

5. Schubert polynomials and Quiver formulas (with A. Buch, A. Kresch and H. Tamvakis),
Duke Math Journal , Volume 122, Issue 1, 125-143 (2004).

Fulton's Universal Schubert polynomials represent general degeneracy loci for maps of vector bundles with rank conditions coming from a permutation. The Buch-Fulton Quiver formula expresses this polynomial as an integer linear combination of products of Schur polynomials in the differences of the bundles. We present a positive combinatorial formula for the coefficients. Our formula counts sequences of semi-standard Young tableaux satisfying certain conditions. In particular, this gives the first explicit, nonrecursive formula for the quantum Schubert polynomials of any partial flag variety.

4. Degree bounds in quantum Schubert calculus
Proceedings of the AMS , Volume 131, Number 9, 2649-2655 (2003).

We give a combinatorial proof of a conjecture of Fulton (after Fulton-Woodward) for the smallest degree of q that appears in the expansion of the product of two Schubert classes in the (small) quantum cohomology ring of a Grassmannian. We present a combinatorial proof of this result, and provide an alternative characterization of this smallest degree in terms of the rim hook formula of Bertram, Ciocan-Fontanine and Fulton for the quantum product.

3. Tree-like properties of cycle factorizations (with I.P. Goulden)
Journal of Combinatorial Theory Series A, 98 , 106-117 (2002).

We provide a bijection between the set of factorizations, that is, ordered (n-1)-tuples of transpositions in ${\mathcal S}_{n}$ whose product is (12...n), and labelled trees on $n$ vertices. We prove a refinement of a 1959 theorem and question of Dénes that establishes new tree-like properties of factorizations. In particular, we show that a certain class of transpositions of a factorization correspond naturally under our bijection to leaf edges of a tree. Moreover, we give a generalization of this fact. We make some remarks about Hurwitz numbers.

2. Dyck paths and a bijection for multisets of hook numbers (with I.P. Goulden),
Discrete Math, 254 , no.1-3, 153-164 (2002).

We give a bijective proof of a conjecture of Regev and Vershik on the equality of two multisets of hook numbers of certain skew-Young diagrams. The bijection proves a result that is stronger and more symmetric than the original conjecture, by means of a construction involving Dyck paths, a particular type of lattice path.

1. Seeing the factorizations for the trees, M.Math. thesis (1999), University of Waterloo. Available upon request.

Contains 1. the results of paper ``2'' above; and 2. a Prufer type code for factorizations providing the first direct bijective proof that n^{n-2} counts the number of factorizations of the long cycle.

More software

At the end of the 2002 CRM Workshop on "Computational Lie Theory", a "wish list" of software as compiled. One of these wishes was for code to compute Schubert calculus for arbitrary G/B.

This code implements Allen Knutson's recursion for Schubert calculus (in the classical setting). To my knowledge, this is the first (and only) publically available code for Schubert calculus computations in general Lie type. (More efficient algorithms are available in type A.)

I make it public merely as a service to the community, in view of the (surprising) lack of such code. I hope that it will provide an early benchmark for future improvement. (Warning: this was written for Maple 7. I do not know if it works for later editions of Maple.) (Code updated June 4, 2006.)