Mark Haiman's Home Page

Classes

Spring 2024

• Math 249—Algebraic Combinatorics

Fall 2023

• Math 1B—Calculus

Fall 2022

• Math 1A—Calculus
• Math 261A—Lie Groups

Fall 2021

• Math 1A—Calculus

Selected Research Papers

(with J. Blasiak, J. Morse, A. Pun and G. H. Seelinger) Dens, nests and the Loehr-Warrington conjecture
Combinatorial formula for a particular class of Catalanimals (symmetric functions introduced in LLT polynomials in the Schiffmann algebra, below) as sums over LLT polynomials indexed by certain configurations of nested lattice paths. Our formula proves the conjecture of Loehr and Warrington on powers of the operator ∇ applied to a Schur function, along with a new (m,n) version of the Loehr-Warrington formula, and provides a common generalization of these and other previous results. PDF, arXiv:2112.07070 (math.CO)

(with J. Blasiak, J. Morse, A. Pun and G. H. Seelinger) LLT polynomials in the Schiffmann algebra
Combinatorial construction of rational functions of a special form (which we call Catalanimals) that represent LLT polynomials in any of the distinguished copies Λ(X^m,n) of the algebra of symmetric functions inside the elliptic Hall algebra of Burban and Schiffmann. As a corollary, this gives raising operator formulas for powers of the operator ∇ applied to LLT polynomials. PDF, arXiv:2112.07063 (math.CO)

(with J. Blasiak, J. Morse, A. Pun and G. H. Seelinger) A shuffle theorem for paths under any line
Forum of Math, Pi 11 (2023), Article E5
Generalization of the shuffle theorem in which the combinatorial side is a sum over LLT polynomials indexed by lattice paths lying under the line between any points on the positive x and y axes. Proof uses a new method based on LLT series and a Cauchy formula for non-symmetric Hall-Littlewood polynoials. PDF, arXiv:2102.07931 (math.CO)

(with J. Blasiak, J. Morse, A. Pun and G. H. Seelinger) A proof of the extended delta conjecture
Forum of Math, Pi 11 (2023), Article E6
Proof of the conjecture in the title, using a continuation of methods from A shuffle theorem for paths under any line, above, and new results on the elliptic Hall algebra of Burban and Schiffmann. PDF, arXiv:2102.08815 (math.CO)

(with I. Grojnowski) Affine Hecke algebras and positivity of LLT and Macdonald polynomials
Proof of the positivity conjecture for LLT polynomials, and Macdonald polynomials as a corollary, using a new positivity theorem in Kazhdan-Lusztig theory. Definition and positivity of LLT polynomials associated with any reductive Lie group. Relation between LLT and generalized Hall-Littlewood polynomials, including the proof of a conjecture of Shimozono and Weyman. Postscript, PDF.

Cherednik algebras, Macdonald polynomials and combinatorics
Proceedings of the International Congress of Mathematicians, Madrid 2006, Vol. III, 843-872.
Exposition of Cherednik algebras and non-symmetric Macdonald polynomials (for all root systems), including a new proof of the duality theorem for Cherednik algebras; and synopsis of the results of A combinatorial formula for non-symmetric Macdonald polynomials, below. Postscript, PDF.

(with J. Haglund and N. Loehr) A combinatorial formula for non-symmetric Macdonald polynomials
Amer. J. Math. 130, No. 2 (2008), 359-383.
We give a combinatorial formula for the non-symmetric Macdonald polynomials E_μ(x;q,t). The formula generalizes our previous combinatorial interpretation of the integral form symmetric Macdonald polynomials J_μ(x;q,t). We prove the new formula by verifying that it satisfies a recurrence, due to Knop, that characterizes the non-symmetric Macdonald polynomials. Postscript, PDF, arXiv:math.CO/0601693

(with A. Woo) Geometry of q and q,t-analogs in combinatorial enumeration
Geometric Combinatorics, IAS/Park City Math. Series 13 (2007), 207-248.
Notes from a series of lectures at Park City Mathematics Institute, July 2004, on the connection between classical q-analogs in combinatorics and q,t-analogs coming from the theory of Macdonald polynomials. Postscript, PDF.

(with J. Haglund and N. Loehr) A Combinatorial Formula for Macdonald Polynomials
J. Amer. Math. Soc. 18 (2005), 735-761.
We prove a combinatorial formula for the Macdonald polynomial H_μ(x;q,t) which had been conjectured by Haglund. Corollaries to our main theorem include the expansion of H_μ(x;q,t) in terms of LLT polynomials, a new proof of the charge formula of Lascoux and Schutzenberger for Hall-Littlewood polynomials, a new proof of Knop and Sahi's combinatorial formula for Jack polynomials as well as a lifting of their formula to integral form Macdonald polynomials, and a new combinatorial rule for the Kostka-Macdonald coefficients K_λ,μ(q,t) in the case that μ is a partition with parts less than or equal to 2. Postscript, PDF, arXiv:math.CO/0409538, California Digital Library

(with J. Haglund, N. Loehr, J. B. Remmel and A. Ulyanov) A combinatorial formula for the character of the diagonal coinvariants
Duke Math. J. 126 (2005), no. 2, 195-232.
We conjecture a complete combinatorial formula for the character of the ring R_n of coinvariants for the diagonal action of the symmetric group. We prove that our formula has various properties consistent with the conjecture. In particular, using the theory of ribbon tableau generating functions of Lascoux, Leclerc and Thibon, we prove that our formula is a symmetric function (which is not obvious) and that it is Schur positive. We also show that earlier conjectures and theorems on the character and Hilbert series of R_n are special cases of this new conjecture. Postscript, PDF, arXiv:math.CO/0310424, California Digital Library

Commutative algebra of n points in the plane (with an appendix by Ezra Miller)
Trends in Commutative Algebra, MSRI Publications 51 (2004), 153-180.
Three lectures on commutative algebra questions arising from the geometry of configurations of n points in the affine plane. Lecture I: the ideal of the locus where some two points coincide. Lecture II: rings of invariants and coinvariants for the symmetric group action. Lecture III: the work of Jeremy Martin on the variety of slopes of the lines connecting the points. Postscript, PDF

Combinatorics, symmetric functions and Hilbert schemes
Current Developments in Mathematics 2002, no. 1 (2002), 39-111.
Survey article on the proof of the Macdonald positivity, n!, and (n+1)^n-1 conjectures using new results on the geometry of Hilbert schemes. Includes background material from combinatorics, symmetric function theory, representation theory and geometry, and discussion at the end of future directions, new conjectures and related work of Ginzburg, Kumar and Thomsen, Gordon, and Haglund and Loehr. Postscript, PDF

(with B. Sturmfels) Multigraded Hilbert Schemes
J. Alg. Geom. 13, no. 4 (2004), 725-769.
We introduce the multigraded Hilbert scheme, which parametrizes all homogeneous ideals with fixed Hilbert function in a polynomial ring that is graded by any abelian group. Our construction is widely applicable, it provides explicit equations, and it allows us to prove a range of new results, including Bayer's conjecture on equations defining Grothendieck's classical Hilbert scheme and the construction of a Chow morphism for toric Hilbert schemes. Postscript, PDF, arXiv:math.AG/0201271, California Digital Library

Notes on Macdonald polynomials and the geometry of Hilbert schemes
In Symmetric Functions 2001:  Surveys of Developments and Perspectives, Proceedings of the NATO Advanced Study Institute held in Cambridge, June 25-July 6, 2001, Sergey Fomin, editor.  Kluwer, Dordrecht (2002), 1-64.
Notes from a series of lectures given in the combinatorics seminar at UCSD, Spring 2001, giving a user-friendly introduction to the results presented in the papers Hilbert schemes, polygraphs, and the Macdonald positivity conjecture, and Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, below. They also contain information on the combinatorial description of the basis of the polygraph ring, which will form part of a future paper. Postscript, PDF

Vanishing theorems and character formulas for the Hilbert scheme of points in the plane
Erratum
Invent. Math. 149, no. 2 (2002), 371-407.
We derive the character formula for diagonal harmonics conjectured in A remarkable q,t-Catalan sequence and q-Lagrange inversion, below, from vanishing theorems for tautological bundles on the Hilbert scheme of points in the plane. In particular this implies that the space of diagonal harmonics has dimension (n+1)^n-1. The vanishing theorems are proved using results from Hilbert schemes, polygraphs, and the Macdonald positivity conjecture, below, together with a recent theorem of Bridgeland, King and Reid. Postscript, PDF, arXiv:math.AG/0201148

Hilbert schemes, polygraphs, and the Macdonald positivity conjecture
J. Amer. Math. Soc. 14 (2001), 941-1006.
The isospectral Hilbert scheme X_n of points in the plane is shown to be normal, Cohen-Macaulay, and Gorenstein. This implies the "n! conjecture" of Garsia and myself, and the positivity conjecture for the Kostka-Macdonald coefficients K_λ,μ. It also implies that the Hilbert scheme of points in the plane coincides with the Hilbert scheme of regular S_n orbits in C²ⁿ . Postscript, PDF, arXiv:math.AG/0010246

(with A. M. Garsia and G. Tesler) Explicit plethysic formulas for Macdonald q,t-Kostka coefficients
The Andrews Festschrift. Seminaire Lotharingien 42 (1999), electronic, 45pp.
A simple and explicit formula for the transformed Macdonald polynomial H_μ is given using the operator ∇ which has come to play a central role in the theory. From this we obtain new and simple proofs of plethystic formulas and integrality for q,t-Kostka coefficients, along with other results such as Sahi's interpolation theorem and Macdonald-Koornwinder reciprocity. Seminaire Lotharingien

(with F. Bergeron, A. M. Garsia, and G. Tesler) Identities and Positivity Conjectures for some remarkable Operators in the Theory of Symmetric Functions
Methods and Applications of Analysis 6, No. 3 (1999), 363-420.
Continued study of the operator ∇ which is central to plethystic formulas for Macdonald polynomials, the conjectured character formula for diagonal harmonics, and related matters. Theorems: ∇ is a polynomial operator; the conjectured character formula for diagonal harmonics is a polynomial. Positivity conjectures for a large class of related formulas. PDF

(with F. Bergeron, N. Bergeron, A. M. Garsia and G. Tesler) Lattice diagram polynomials and extended Pieri rules
Advances in Math. 142 (1999), 244-334.
Analog of the "n! conjecture" with Young diagrams replaced by general subsets D of NxN. When D is a Young diagram with a "hole" missing, we conjecture character formulas which are connected with the Pieri formulas for Macdonald polynomials. arXiv:math.CO/9809126

Macdonald polynomials and geometry
In New Perspectives in Geometric Combinatorics, MSRI Publications 37 (1999), 207-254.
Explication of the connection between Macdonald polynomials, the "n! conjecture," and the Hilbert scheme of points in the plane and related algebraic varieties. Theorem: n! conjecture implies Macdonald positivity conjecture. Additional results on diagonal harmonics. PostScript, PDF

t,q-Catalan numbers and the Hilbert scheme
Discrete Math. 193 (1998), 201-224.
Geometric interpretation of the t,q-Catalan number formula from A remarkable q,t-Catalan sequence and q-Lagrange inversion, below, using the Hilbert scheme of points in the plane. Theorem: the formula reduces to a polynomial in q, t. The "higher" Catalan polynomials C^m(q,t) have non-negative coefficients for m sufficiently large. PostScript, PDF

(with W. Brockman) Nilpotent orbit varieties and the atomic decomposition of the q-Kostka polynomials
Canad. J. Math. 50 (1998), no. 3, 525-537.
Theorem: There exist non-negative polynomials R_λ,ν(q) such that the q-Kostka polynomial K_λ,μ(q) is the sum of R_λ,ν(q) for all ν greater than or equal to μ in dominance order. The proof is by geometry and representation theory. The result was previously known from Lascoux and Schutzenberger's combinatorial theory of cyclage and "atoms." PostScript, PDF

(with A. M. Garsia) A random q,t-hook walk and a sum of Pieri coefficients
Journal of Combinatorial Theory (A) 82 (1998), no. 1, 74-111.
We modify the classical hook-walk process of Greene, Nijenhuis and Wilf by weighting the transition probabilities by powers of indeterminates q and t. This simple modification leads to identities involving the Pieri coefficients for Macdonald polynomials which generalize familiar enumerative identities for standard Young tableaux. PostScript (landscape mode, may not work), PDF

(with A. M. Garsia) A remarkable q,t-Catalan sequence and q-Lagrange inversion
J. Algebraic Combin. 5 (1996), no. 3, 191-244.
Conjectured exact formula, in terms of Macdonald polynomials, for the Frobenius series of the diagonal harmonics studied in Conjectures on the quotient ring by diagonal invariants, below. Theorem: various specializations of the master formula imply all the the combinatorial conjectures in the earlier paper. PostScript, PDF

(with A. M. Garsia) Some natural bigraded S_n -modules and q,t-Kostka coefficients
The Foata Festschrift: Electronic J. Combin. 3 (1996), no. 2, Research Paper 24, approx. 60 pp.
Detailed proofs of results announced in A graded representation model for Macdonald's polynomials, below, and further study of the modules introduced there.

(with S. Billey) Schubert polynomials for the classical groups
J. Amer. Math. Soc. 8 (1995), no. 2, 443-482.
Uniform and stable definition of Schubert polynomials for each family of classical groups, generalizing that of Lascoux and Schutzenberger for type A. Theorems: Analog of the Billey-Jockusch-Stanley formula; symmetric part is given by the generalized Edelman-Greene correspondence; Grassmannian cases reduce to Schur P- and Q-functions. PostScript, PDF, JSTOR

Conjectures on the quotient ring by diagonal invariants
J. Algebraic Combin. 3 (1994), no. 1, 17-76
Combinatorial conjectures and supporting theorems concerning the ring R_n = Q[x₁, y₁, ... ,x_n, y_n]/I, where I is the ideal generated by S_n invariants. PostScript, PDF. With tables of the Hilbert series of R_n for n up to 7 (PostScript) and the Frobenius series for n up to 6 (PostScript).

On realization of Björner's "continuous partition lattice" by measurable partitions
Trans. Amer. Math. Soc. 343 (1994), no. 2, 695-711.
Construction of a "continuous" partition lattice with properties analogous to the finite partition lattices as a lattice of measure-preserving measurable partitions of a unit Lebesgue space. Björner's earlier abstract construction embeds as the sublattice of "rational" measure-preserving partitions. PostScript, JSTOR

Hecke algebra characters and immanant conjectures
J. Amer. Math. Soc. 6 (1993), no. 3, 569-595.
Two conjectures on characters of the Hecke algebra of type A_n, evaluated on Kazhdan-Lusztig basis elements. Theorem: immanants of Jacobi-Trudi matrices are positive combinations of Schur functions. If Conjecture 1 holds, then "monomial" immanants are also Schur positive. PostScript, PDF, JSTOR

(with A. M. Garsia) A graded representation model for Macdonald's polynomials
Proc. Nat. Acad. Sci. U.S.A. 90 (1993), no. 8, 3607-3610.
The "n! conjecture," conjectured combinatorial-representation theoretic interpretation of the Macdonald q,t-Kostka coefficients, and sketch of results supporting the conjectures. PostScript, PDF, JSTOR

(with A. M. Garsia) Factorizations of Pieri rules for Macdonald polynomials Discrete Math. 139 (1995), no. 1-3, 219-256.
We introduce a heuristic embedding of the Macdonald polynomials P_μ(x; q,t) into a family of polynomials indexed by lattice square diagrams. This embedding leads to recursions which may be viewed as a factorization of the Stanley-Macdonald Pieri rules and shed some light into their intricate nature. In this manner we can prove some conjectures concerning the coefficients K_λ,μ(q,t). Special results for 2-row shapes and some examples involving more general shapes.

Noncommutative rational power series and algebraic generating functions
European J. Combin. 14 (1993), no. 4, 335-339.
Some combinatorial applications of the following theorem: the constant term of a rational formal power series in non-commuting indeterminates and their inverses (left or two-sided) is algebraic. The theorem follows from results of Chomsky and Schutzenberger. This is shown in the paper, but I learned afterwards that the same proof had been given earlier by Gerard Jacob: "Sur un theoreme de Shamir," Information and Control 27 (1975), 218-261. PostScript

Constructing the associahedron
Scanned image of an unpublished manuscript from fall 1984 in which it is shown that the simplicial complex whose vertices are the chords of an n-gon and whose facets are the triangulations is the face lattice of a polytope. This result was superseded first by a better construction of Carl Lee, and subsequently by the theory of secondary polytopes. The manuscript is here for whatever historical interest it may have. PostScript, PDF