Papers by Richard P. Stanley

If you have trouble downloading any of the files (all are PostScript), or would prefer a hard copy, please e-mail me at: rstan (at math.mit.edu).

Complete list of publications

Some curious sequences constructed with the greedy algorithm (with A. M. Odlyzko) (5 pages)
Unpublished notes dated January, 1978, concerning sequences of integers containing no three terms in arithmetic progression.
Hyperplane arrangements, interval orders and trees (20 pages)
Proc. Nat. Acad. Sci. 93 (1996), 2620--2625.
Some connections between the three objects of the title are investigated.
Hipparchus, Plutarch, Schröder and Hough (12 pages)
American Mathematical Monthly 104 (1997), 344-350.
A solution to an ancient combinatorial riddle.
Graph colorings and related symmetric functions: ideas and applications (28 pages)
Discrete Mathematics 193 (1998), 267-286.
A sequel to "A symmetric function generalization of the chromatic polynomial of a graph," Advances in Math. 111 (1995), 166-194.
Hyperplane arrangements, parking functions and tree inversions (14 pages)
in Mathematical Essays in Honor of Gian-Carlo Rota (B. Sagan and R. Stanley, eds.), Birkhäuser, Boston/Basel/Berlin, 1998, pp. 359-375.
Connections between the three objects of the title, and a generalization involving k-parking functions and rooted k-forests.
A q-deformation of a trivial symmetric group action (with Phil Hanlon) (26 pages)
Transactions of the American Mathematical Society 350 (1998), 4445-4459.
Solutions to problems raised by Varchenko and Zagier concerning a q-deformation of the element of the group algebra of the symmetric group S_n equal to the sum of all the elements of S_n.
Polygon dissections and standard Young tableaux (4 pages)
Journal of Combinatorial Theory, series A 76 (1996), 175-177.
A simple bijection between dissections of a convex (n+2)-gon with d diagonals not interecting in their interiors and standard Young tableaux of shape (d+1, d+1, 1^n-1-d).
Lê numbers of arrangements and matroid identities (16 pages)
(with D. B. Massey, R. Simion, D. Vertigan, D. J. A. Welsh, and G. M. Ziegler), J. Combinatorial Theory, Series B 70 (1997), 118-133.
Some identities involving the Möbius function of a matroid, motivated by the Lê number of a hypersurface singularity.
Parking functions and noncrossing partitions (14 pages)
Electronic J. Combinatorics 4 , R20 (1997).
Some connections between parking functions, noncrossing partitions, symmetric functions, and a local action of the symmetric group.
Deformations of Coxeter hyperplane arrangements (with Alexander Postnikov) (41 pages, version of 29 March 2000)
J. Combinatorial Theory (A), to appear.
Devoted mainly to the computation of the characteristic polynomial of some hyperplane arrangements related to the braid arrangement and other Coxeter arrangements. Includes the connection between the Linial arrangement, alternating trees, local binary search trees, and other combinatorial objects. Also included is a "Riemann hypothesis" for the characteristic polynomial of the Linial arrangement and related arrangements.
Flag-symmetry of the poset of shuffles and a local action of the symmetric group (with Rodica Simion) (34 pages)
Discrete Math. 204 (1999), 369-396.
New combinatorial properties of Curtis Greene's poset of shuffles.
A combinatorial miscellany (PDF file) (with Anders Björner) (95 pages)
L'Enseignement Math., to appear.
An expository paper of various topics in algebraic and enumerative combinatorics, intended for both mathematicians and nonmathematicians. Includes discussions of integer partitions, plane partitions, the Schensted algorithm, increasing and decreasing subsequences, reduced decompositions, enumeration of tilings, combinatorics and topology, evasiveness, complexity of sorting and distinctness, and face numbers of polytopes.
Spanning trees and a conjecture of Kontsevich (13 pages, publication version)
Annals of Combinatorics 2 (1999), 351-363.
Kontsevich conjectured that the number of zeros over the field F_q of a certain polynomial connected with the spanning trees of a graph G is a polynomial function of q. We have not been able to settle this conjecture, but we show the connection with such topics as the Matrix-Tree Theorem and orthogonal geometry. A sequel to this paper was written by John Stembridge and appears in the same issue of Annals of Combinatorics. Update.
Domino tilings with barriers (with Jim Propp) (10 pages)
J. Combinatorial Theory (A) 87 (1999), 347-356 .
Proves a result about the independence of certain random domino tilings of the Aztec diamond.
Positivity problems and conjectures in algebraic combinatorics (35 pages, version of 24 September 1999)
In Mathematics: Frontiers and Perspectives (V. Arnold, M. Atiyah, P. Lax, and B. Mazur, eds.), American Mathematical Society, Providence, RI, 2000, pp. 295-319.
A survey of problems and conjectures in algebraic combinatorics related to showing that certain numbers are nonnegative. The three main areas covered are (1) f-vectors, (2) representation theory and symmetric functions, and (3) real zeros and total positivity. Update (14 September 2004).
A polytope related to empirical distributions, plane trees, parking functions, and the associahedron (with Jim Pitman) (40 pages)
Discrete and Computational Geometry, 27 (2002), 603-634.
The title says it all, except there are also connections with plane partitions.
A generalized riffle shuffle and quasisymmetric functions (19 pages, version of 31 May 2001)
Annals of Combinatorics, 5 (2001), 479-491.
This paper concerns a probability distribution on the symmetric group generalizing the riffle shuffle of Bayer, Diaconis, and others. There are close connections with the theory of quasisymmetric and symmetric functions.
A note on the symmetric powers of the standard representation of S_n (with David Savitt) (7 pages)
Electronic J. Combinatorics 7, R6 (2000).
The main result is that the dimension of the space spanned by the characters of the symmetric powers of the standard n-dimensional representation of the symmetric group S_n is asymptotic to n²/2.
Rodica Simion, January 18, 1955 -- January 7, 2000 (5 pages)
Pi Mu Epsilon Journal 11 (2000), 83-86.
An appreciation of a truly special person.
Recent progress in algebraic combinatorics (23 pages, version of 19 March 2002)
Bull. Amer. Math. Soc. 40 (2003), 55-68.
A survey of recent work on (1) the saturation conjecture for Littlewood-Richardson coefficients, (2) the n! and (n+1)^n-1 conjectures, and (3) longest increasing subsequences of permutations.
On the enumeration of skew Young tableaux (15 pages)
Advances in Applied Math. 30 (2003), 283-294.
Exact formulas and asymptotic estimates for the number of skew Young tableaux of shape a/b where (1) b is fixed and a has size n, and (2) both a and b are fixed.
The rank and minimal border strip decompositions of a skew partition (31 pages)
J. Combinatorial Theory (A) 100 (2002), 349-375.
Some properties of the rank of a skew partition (originally defined by Nazarov and Tarasov) and a related investigation of the minimal border strip decompositions and minimal border strip tableaux of a skew partition. Update.
Irreducible symmetric group characters of rectangular shape (11 pages, version of 17 December 2002)
Sém. Lotharingien de Combinatoire (electronic) 50 (2003), B50d.
A new formula for the values of an irreducible symmetric character corresponding to a partition of rectangular shape, and some comments and conjectures on a generalization.
Rodica Simion and shuffle posets (3 pages)
Advances in Applied Math. 28 (2002), 282-284.
Reminiscences on the only joint paper I wrote with Rodica Simion.
Some remarks on sign-balanced and maj-balanced posets (30 pages, version of 14 January 2004) (PDF file)
Advances in Applied Math. 34 (2005), 880-902.
An investigation of (labelled) posets for which exactly half the linear extensions have an even number of inversions (i.e., are even permutations) and posets for which exactly half the linear extensions have even major index.
Recent developments in algebraic combinatorics (30 pages)
Israel J. Math. 143 (2004), 317-340.
A continuation of "Recent progress in algebraic combinatorics" above, with three sections: (1) the Laurent phenomenon, (2) Gromov-Witten invariants and toric Schur functions, and (3) toric h-vectors and intersection cohomology.
The mathematical knight (with N. Elkies) (23 pages) (pdf)
The Mathematical Intelligencer 25, no. 1 (Winter 2003), 22--34
A survey of chess problems and puzzles, featuring the knight, that would be of interest to mathematicians.
A map on the space of rational functions (with G. Boros, J. Little, V. Moll, and E. Mosteig) (16 pages)
Rocky Mountain J. Math., to appear
A study of the dynamical properties of a certain map F defined on the space of rational functions. The long time behavior of a subclass involves properties of Eulerian polynomials.
A super-class walk on upper-triangular matrices (with E. Arias-Castro and P. Diaconis) (26 pages)
J. Algebra 278 (2004), 739-765.
An analysis of a random walk on the group of n×n upper-triangular matrices over a finite field, based on the character theory of Andre, Carter, and Yan.
Properties of some character tables related to the symmetric groups (with C. Bessenrodt and J. Olsson) (16 pages, version of 27 February 2004)
J. Algebraic Combinatorics 21 (2005), 163-177.
Determination of invariants like the Smith normal form and the determinant for certain integral matrices which arise from the character tables of the symmetric groups S_n and their double covers.
An application of set theory to cosmology (one page) (PDF)
Correction of a defective theory of cosmology.
Bottom Schur functions (with P. Clifford) (16 pages)
Electronic J. Combinatorics 11(1) (2004), R67.
Properties of the symmetric function consisting of the terms of least degree of a Schur function, when we define the degree of the power sum p_i to be 1.
Coefficients and roots of Ehrhart polynomials (with M. Beck, J. De Loera, M. Develin, and J. Pfeifle) (Note. File is over 15MB due to complicated graphics.) (24 pages)
Contemp. Math. 374 (2005), 15-36.
Restrictions on the coefficients and zeros of various classes of Ehrhart polynomials of integer polytopes, and a conjecture on the Ehrhart polynomial of a cyclic polytope.
Tilings (pdf) (with F. Ardila ) (21 pages)
A survey of tilings in the plane for a nonmathematial audience. Based on a Clay Public Lecture at the IAS/Park City Mathematics Institute in July, 2004.
Crossings and nestings of matchings and partitions (with William Y. C. Chen (陈永川), Eva Y. P. Deng (邓玉平), Rosena R. X. Du (杜若霞), and Catherine H. Yan (颜华菲)) (24 pages) (version of 9 November 2005)
Trans. Amer. Math. Soc. 359 (2007), 1555-1575.
Applications of oscillating tableaux and vacillating tableaux to the enumeration of matchings and set partitions with conditions on crossings and nestings.
Ordering events in Minkowski space (18 pages) (version of 11 June 2005)
Advances in Applied Math., to appear.
Given k points in (n+1)-dimensional Minkowski space, in how many orders can they occur in different reference frames? What sets of orders are possible? These questions are investigated using the theory of hyperplane arrangements.
Chains in the Bruhat order (with Alexander Postnikov) (36 pages)
J. Algebraic Combinatorics, to appear.
An investigation of a family of polynomials whose values are degrees of Schubert varieties in the generalized complex flag manifold G/B. The polynomials are given by weighted sums over saturated chains in the Bruhat order.
Queue problems revisited (pdf) (12 pages)
Suomen Tehtäväniekat 59, no. 4 (2005), 193-203.
A paper that will be mainly of interest to mathematical chess problem aficionados. It does include several classes of posets whose number of linear extensions can be computed explicitly.
The descent set and connectivity set of a permutation (12 pages)
J. Integer Sequences 8 (2005), article 05.3.8.
The connectivity set of a permutation is defined and is shown to be a kind of dual to the descent set.
An analogue of Young's lattice for compositions (with Anders Björner) (20 pages, version of 4 November 2005)
Combinatorial, algebraic, and topological properties of a graded poset whose elements of rank n are indexed by compositions of n.
Longest alternating subsequences of permutations (19 pages, version of 15 November 2005)
Combinatorial and statistical properties of the length of the longest alternating subsequence of a permutation of 1,2,...,n.
Increasing and decreasing subsequences and their variants (34 pages, pdf file).
Proc. Internat. Cong. Math. (Madrid, 2006), to appear.
A survey paper on the subject of the title. Includes such variants as pattern avoidance, alternating subsequences, and matchings. This is the final version as it will appear in the Proceedings, except that reference [114] will be updated.
Alternating permutations and symmetric functions (37 pages, version of 18 August 2006)
J. Combinatorial Theory Series A, to appear.
The theory of symmetric functions is used to enumerate various classes of alternating permutations, such as those with a given cycle type. Update.
A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group (6 pages, version of 26 July 2006)
A conjectured generalization of the main result of "Irreducible symmetric group characters of rectangular shape". The formula for rectangular shapes is (conjecturally) generalized to arbitrary shapes. Update.

Richard Stanley's Home Page