My papers on the Mathematics ArXiV.
60. An estimation method
for game complexity
(with David Yong), preprint, version of January 29, 2019.
We study a method for estimating the game tree size of strategic games.
59. Reduced words, complexity,
and randomization
(with Cara Monical and Benjamin Pankow), preprint, version of January 30,
2019.
We study algorithmic and complexity aspects of reduced word enumeration.
58. Complexity, combinatorial
positivity, and Newton polyopes
(with Anshul Adve and Colleen Robichaux), preprint, version of October 24,
2018.
We discuss an algebraic combinatorics paradigm for
computation complexity. Our main results concern Schubert polynomials.
57. Tropicalization,
symmetric polynomials, and complexity
(with Alexander Woo), accepted to Journal of Symbolic Computation, version
of October 9, 2017.
We study the circuit complexity of some tropicalized symmetric
polynomials.
56. K-orbits and Barbasch-Evens-Magyar
varieties
(with Laura Escobar and Benjamin Wyser), preprint, version of August 22,
2017.
We construct and study Barbasch-Evens-Magyar varieties.
55. Vanishing of Littlewood-Richardson
polynomials is in P
(with Anshul Adve and Colleen Robichaux), to appear in Computational Complexity; version of
March 21, 2019.
We give a strongly polynomial time algorithm for deciding the vanishing
of Littlewood-Richardson polynomials.
54. Symmetric group representations and Z
(with Anshul Adve), C. R. Math. Acad. Sci. Paris 356 (2018), no. 1, 1--4. (Version of June
30, 2017.)
A remark on the representation theory of symmetric groups.
53. Newton polytopes and symmetric Grothendieck
polynomials
(with Laura Escobar), C. R. Math. Acad. Sci. Paris 355 (2017), no. 8, 831--834. (Version of
May 22, 2017.)
We prove symmetric Grothendieck polynomials have saturated Newton polytopes.
52. Newton polytopes in algebraic
combinatorics
(with Cara Monical and Neriman Tokcan), preprint, version of Mar 10, 2017.
We study Newton polytopes of various families of polynomials in algebraic
combinatorics.
51. Governing singularities of symmetric orbit
closures
(with Alexander Woo and Benjamin Wyser), Algebra and Number theory 12 (2018),
no. 1, 173-225.
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)xGL(q) acting on the classical flag variety.
50. Partition identities and quiver
representations
(with Richard Rimanyi and Anna Weigandt), J. Algebraic Comb.
47 (2018), no. 1, 129--169. (Version of June 1, 2017).
We establish a specific connection between classical partition
combinatorics and the theory of quiver representations.
49. Rhombic tilings and Bott-Samelson
varieties
(with Laura Escobar, Oliver Pechenik and Bridget Tenner),
Rhombic tilings and Bott-Samelson varieties. Proc. Amer. Math. Soc. 146 (2018), no. 5,
1921--1935. (Version of Jun 9, 2016.)
We observe a connection between Elnitsky's rhombic tilings and
Magyar's description of
Bott-Samelson
varieties.
48. Poset edge densities, nearly reduced words
and barely set-valued tableaux
(with Victor Reiner and Bridget Tenner), to appear in J. Combinatorial
Theory Series A, March 13,
2018.
We study a certain coincidence of expectations of down-degree of posets.
47. Genomic Tableaux
(with Oliver Pechenik), J. Algebraic Combinatorics, to appear,
version of March 28, 2016.
We describe a theory of genomic tableaux.
46. The prism tableau model for
Schubert polynomials
(with Anna Weigandt), J. Combin. Theory Ser. A 154 (2018), 551--582. (Version of September 8,
2015.)
We propose a new model for Schubert polynomials.
45. Equivariant K-theory of
Grassmannians
II: the Knutson-Vakil conjecture
(with Oliver Pechenik), to appear in Compositio Math., version of August
3, 2015.
We resolve a conjecture of A. Knutson-R. Vakil.
44. Equivariant K-theory of Grassmannians
(with Oliver Pechenik), preprint, June 5, 2015; accepted to
Forum of Math, Pi.
We give a combinatorial rule for multiplication of the basis of
Schubert structure sheaves in the equivariant K-theory ring of the
Grassmannian. (See also the announcement version below.)
43. Genomic Tableaux and
Combinatorial K-theory (with Oliver Pechenik)
to appear in the Proceedings of Formal Power Series and
Algebraic combinatorics 2015 , version of April 8, 2015.
Announcement of results on (equivariant) K-theory of Grassmannians
(and maximal orthogonal, Lagrangian Grassmannians).
42. Critique of Hirsch's citation
index:
a combinatorial Fermi problem
preprint (10 pages+appendix), accepted to Notices of the AMS ,
version of October 13, 2014.
We use the Euler-Gauss partition identity to offer a critique of
the bibliometric h-index.
41. Polynomials for symmetric
orbit closures in the flag variety (with Benjamin Wyser),
preprint (22 pages),
version of September 30, 2014.
We continue our study of polynomial representatives of orbit closures
in the flag variety for symmetric pairs (G,K) in type A.
40. The Joseph Greenberg problem:
combinatorics
and comparative linguistics
, preprint (6 pages), version of October 10, 2013.
We discuss some combinatorics related to work
of linguist J. Greenberg. We give an interpretation of the consensus range
of the number of indigenious language families of the Americas.
Best read
along with the video .
39. Polynomials for GL_{p} x
GL_{q} orbit closures in the flag variety
(with Benjamin Wyser), to appear in Selecta Math (25
pages), version of March 4, 2014.
We introduce polynomial representatives of GL_{p} x
GL_{q} orbit closures in the flag variety.
38. Root-theoretic Young diagrams
and Schubert calculus: planarity and the adjoint varieties
(with Dominic Searles), J. Algebra to appear (45 pages),
version of
August 29, 2013.
We study the existence of a root-system uniform and nonnegative
combinatorial rule for Schubert calculus. Our main cases are the adjoint
varieties of classical type. (An preliminary version appeared as an
extended abstract in FPSAC 2013.)
37. Combinatorial
rules
for three bases
of polynomials
(with Colleen Ross), Seminaire Lotharingien de Combinatoire (11 pages), 2015.
We present combinatorial rules (one theorem and two conjectures)
concerning three bases of Z[x1,x2,...].
Errata note added March 10, 2017: the published version has a misstatement
of
Conjectures 1.4 and 1.6. The version above has the correction.
36. Eigenvalues of Hermitian matrices and equivariant
cohomology of Grassmannians
(with David Anderson and Edward Richmond),
accepted to Compositio Math (14 pages),
version of April 2, 2013.
We establish a connection between the eigenvalue problem of S. Friedland
and equivariant Schubert calculus.
35. Singularities of Richardson varieties
(with Allen Knutson and Alexander Woo),
Math. Res. Letters (10 pages), version of September 14, 2012.
We prove essentially all singularity questions about Richardson varieties
reduce to the case of Schubert varieties.
34. Equivariant Schubert calculus and jeu de taquin
(with Hugh
Thomas),
Annales de l'Institut Fourier (31 pages), accepted pending minor
revisions,
version of July 11, 2012.
We develop equivariant analogues of jeu de taquin, in relation to Schubert calculus of Grassmannians.
33.
Patch ideals and Peterson varieties
(with Erik Insko),
Transformation Groups (23 pages), version of February
3, 2012.
We study patch ideals of Peterson varieties and some other subvarieties of
GL_{n}/B.
32.
Kazhdan-Lusztig
polynomials and drift configurations
(with Li Li),
Algebra and Number Theory , (25 pages), June 19, 2010.
We suggest a parallel between Kazhdan-Lusztig polynomials and H-polynomials of local rings
of Schubert varieties.
31. Some degenerations of
Kazhdan-Lusztig ideals and multiplicities of Schubert varieties
(with Li Li), Advances in Math , (31 pages), version
of July 1, 2011.
We prove a combinatorial rule for the Hilbert-Samuel multiplicities of covexillary Schubert
varieties at singular points. Generalizations of our method to general Schubert varieties
in the complete flag variety are suggested.
30. K-theoretic Schubert calculus
for OG(n,2n+1) and jeu de taquin for shifted increasing tableaux (with Edward
Clifford and Hugh Thomas), to appear in J. Reine Angew Math (Crelle)
(13 pages), Feb 15, 2012.
Using recent work of Buch--Ravikumar and Feigenbaum-Sergel we prove the conjectural
rule from [Thomas-Yong '09] for $K$-theory Schubert calculus for maximal odd orthogonal
Grassmannians.
29.
A Grobner basis for Kazhdan-Lusztig ideals (with Alexander Woo),
preprint
(40 pages), American J. Math , 2012.
We prove a Grobner basis theorem for Kazhdan-Lusztig ideals, and apply
this to the study of specializations of Schubert/Grothendieck polynomials,
and multiplicities of Schubert varieties.
28.
The direct sum map on Grassmannians and
Jeu de taquin for increasing tableaux
(with Hugh Thomas),
International Math. Res. Notices, (20 pages), 2010.
We establish analogues of Schutzenberger's fundamental theorems of
jeu de taquin for splitting coefficients defining the direct sum map, as
well as products of Schubert boundary ideal sheaves,
in K-theory of Grassmannians.
27. Presenting the cohomology
of a Schubert variety (with Victor Reiner and Alexander Woo),
Transactions of the AMS,
(22 pages), 2009.
We extend the short presentation of the cohomology ring of a
generalized flag manifold, due to [Borel '53], to a relatively short
presentation of the cohomology of any of its Schubert varieties.
26. An approximation algorithm
for contingency tables
(with Alexander Barvinok, Zur Luria and Alex
Samorodnitsky), accepted to Random
Structures and Algorithms , 2009 (45 pages).
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).
Update (July, 2008): My coauthor A. Barvinok
has further studied the typical table in
his paper.
25. Longest strictly increasing subsequences,
Plancherel measure and
the Hecke insertion algorithm
(with Hugh Thomas),
Advances in Applied Math (Dennis Stanton special
issue) (34 pages), 10/02/02. (Contains an appendix with Ofer
Zeitouni and myself.)
Companion Maple code
HeckeLIS.v0.1.txt.
We define and study the Plancherel-Hecke probability
measure on Young diagrams.
24. A jeu de taquin theory for increasing
tableaux,
with applications
to K-theoretic Schubert calculus
(with Hugh Thomas),
Algebra and Number Theory , 2008 (22 pages).
We introduce a theory of
jeu de taquin for increasing tableaux,
extending fundamental work of
[Sch\"{u}tzenberger '77] for standard Young tableaux.
23. An S_3 symmetric Littlewood-Richardson
rule
(with Hugh Thomas),
Mathematical Research Letters
, volume 15, no.5-6, 2008; (9 pages).
The classical Littlewood-Richardson coefficients carry a natural $S_3$ symmetry via
permutation of indices. Our ``carton rule'' for computing these numbers transparently and uniformly
explains these six symmetries; previous rules manifest at most three
of the six.
22. 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
approximates the number of
n x n non-negative
integer matrices (magic squares) with the row and column sums equal to
t.
21. Cominuscule tableau combinatorics
(with Hugh Thomas), (revised July 2013).
To appear in MSJ-SI 2012 Proceedings. 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.
20. 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.
19. A combinatorial rule for (co)minuscule
Schubert
calculus
(with Hugh Thomas),
Advances in Math , 2009.
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.
18.
Stable Grothendieck polynomials
and K-theoretic factor sequences (full version)
(with A. Buch, A. Kresch, M. Shimozono and H. Tamvakis),
Math.
Annalen, volume 340, number 2, 2008.
17. Tableau complexes (with
A.
Knutson and E. Miller), Israel Journal of Math
, 163 (2008), 317-343.
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''.
16. Multiplicity-free Schubert calculus
(with H.
Thomas),
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.
15. 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.
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.
14. 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 .
13. When is a Schubert variety
Gorenstein?
(with A. Woo),
Advances in Math , Vol 207 (2006), Issue 1 205--220.
Companion Maple
code available.
We determine
which Schubert varieties are Gorenstein in terms of a combinatorial
characterization using generalized pattern avoidance conditions.
12. Grobner geometry of Schubert transition formulae
and Littlewood-Richardson rules
(with A. Knutson), preprint.
11.
A formula for K-theory truncation Schubert calculus
(with A. Knutson),
International Mathematics Research Notices , 70 (2004),
3741-3756.
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)).
10. Lecture notes
on the K-theory of
the flag variety and the
Fomin-Kirillov
quadratic algebra (with C. Lenart), 2004.
We construct a commutative subalgebra of the Fomin-Kirillov quadratic algebra
and explain the
(conjectural)
connection
to the K-theory ring of the flag variety and the associated Schubert
structure constants.
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 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.
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.
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.
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.
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.
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
(Code for a particular paper is found
with the .ps file above.)
Maple 7 code to compute Schubert calculus in G/B
, website exclusive, 2006.
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).
(Warning: this was written
for Maple 7. I do not know if it works for later editions of Maple.)
(Code updated June 4, 2006.)
C++
code for estimating permanents, hafnians and the number of
forests in a graph, 2003.