Home

Teaching

Research

Publications

CV

Books

Inquiry-Based Enumerative Combinatorics: One, Two, Skip a Few... Ninety-Nine, One Hundred, Undergraduate Texts in Mathematics, Springer, 2019. More about this book

Eulerian Numbers, Birkhaüser Advanced Texts Basler Lehrbücher, Springer, New York, 2015. More about this book

Papers and Preprints

39. A more malicious maitre d' (with R. Acton, B. Shirman, and D. Toal), American Mathematical Monthly, 130 (2023), 728-745. abstract arXiv

Nearly 20 years later, the malicious maitre d' is back! This time he is adaptive, and walks with you to your table.

39. Monotone subsets in lattices and the Schensted shape of a Sós permutation (with K. Liechty), Combinatorial Theory, 2 (2022), paper no. 9, 41pp. abstract arXiv

The Schensted shape of a random permutation is a beautiful curve known as the Vershik-Kerov limit shape. As a test of randomness, one can take a data string and compare its Schensted shape to the Vershik-Kerov curve. In this paper, we characterize the Schensted shapes of Sós permutations and find their boundaries are piecewise linear. Not very random!

38. On the joint distribution of descents and signs of permutations (with J. Fulman, G. B. Kim, and S. Lee), Electronic Journal of Combinatorics, 28 (2021), paper no. 3.37, 30pp. abstract arXiv

We study the joint distribution of permutations by descents and sign. We prove central limit theorems for these distributions and point out applications to card shuffling.

37. Card shuffling and \(P\)-partitions (with J. Fulman), Discrete Mathematics, 344 (2021), paper no. 112448, 18pp. abstract arXiv

This expository paper highlights the connection between the combinatorial notion of \(P\)-partitions and card shuffling. Many of the results are collected from other sources, but some ideas presented are new.

36. Sós Permutations (with S. Bockting-Conrad, Y. Kashina, and B. E. Tenner), American Mathematical Monthly, 128 (2021), 407-422. abstract arXiv

This paper characterizes and enumerates those permutations generated by a real line modulo 1. That is, we let \(f(x) = \alpha x + \beta \mod 1\) for fixed real parameters \(\alpha\) and \( \beta\). Then for any \(n\) we define the Sós permutation to be the lexicographically first permutation \(\pi\) such that \( 0\leq f(\pi(0))\leq f(\pi(1))\leq \cdots \leq f(\pi(n)) < 1 \).

35. Broken legos and the pick-up sticks problem (with B. E. Tenner), Mathematics Magazine, 93, p. 175-185 (2020). abstract arXiv

This paper puts a new spin on the classic question: ``If I break a stick into three pieces, what is the probability that these three pieces can form the sides of a triangle?''

34. Root cones and the resonance arrangement (with S. Gutekunst and K. Meszaros), Electronic Journal of Combinatorics, 28 (2021), no. P.12, 39pp. abstract arXiv

This paper explores three hard counting problems and connections between them: 1) the number of threshold functions on \(n\) variables, 2) the number of maximal unbalanced families of an \(n\)-set, and 3) the number of chambers of polynomiality for the Konstant partition function. Each problem has a rich history and a dearth of exact enumerative data. All three have links to hyperplane arrangements and type A root system combinatorics.

33. Computing reflection length in an affine Coxeter group (with Joel Brewster Lewis, Jon McCammond, and Petra Schwer), Transactions of the American Mathematical Society, 371, p. 4097-4127 (2019). abstract arXiv

In any Coxeter group, the conjugates of elements in its Coxeter generating set are called reflections and the reflection length of an element is its length with respect to this expanded generating set. In this article we give a simple formula that computes the reflection length of any element in any affine Coxeter group and we provide a simple uniform proof.

32. The pinnacle set of a permutation (with Rob Davis, Sarah Nelson, and B. E. Tenner), Discrete Mathematics, 341, p. 3249-3270 (2018). abstract arXiv

Peak sets of a permutation record the indices of its peaks. These sets have been studied in a variety of contexts, including work by Billey, Burdzy, and Sagan, which enumerated permutations with prescribed peak sets. In this article, we look at a natural analogue of the peak set of a permutation, instead recording the values of the peaks. We define the "pinnacle set" of a permutation \(w\) to be the set \(\{ w(i) : i \mbox{ is a peak of } w \}.\) Although peak sets and pinnacle sets mark the same phenomenon, these objects differ in notable ways. In the work below, we characterize admissible pinnacle sets and study various enumerative questions related to these objects.

31. A two-sided analogue of the Coxeter complex, Electronic Journal of Combinatorics, 25 (2018). abstract arXiv

For any Coxeter system \( (W,S) \) of rank \( n,\) we introduce an abstract boolean complex (simplicial poset) of dimension \( 2n-1 \) that contains the Coxeter complex as a relative subcomplex. Faces are indexed by triples \( (I,w,J),\) where \( I \) and \( J \) are subsets of the set \( S \) of simple generators, and \( w \) is a minimal length representative for the parabolic double coset \( W_IwW_J.\) There is exactly one maximal face for each element of the group \( W.\) The complex is shellable and thin, which implies the complex is a sphere for the finite Coxeter groups. In this case, a natural refinement of the \(h\)-polynomial is given by the "two-sided" \(W\)-Eulerian polynomial, i.e., the generating function for the joint distribution of left and right descents in \(W. \)

30. Parabolic double cosets in Coxeter groups (with S. Billey, M. Konvalinka, W. Slofstra, and B. E. Tenner), Electronic Journal of Combinatorics, 25 (2018). abstract arXiv

Parabolic subgroups \(W_I\) of Coxeter systems \( (W,S), \) as well as their ordinary and double quotients \( W/W_I \) and \( W_I\backslash W/W_J \), appear in many contexts in combinatorics and Lie theory, including the geometry and topology of generalized flag varieties and the symmetry groups of regular polytopes. The set of ordinary cosets \(wW_I\), for \( I \subseteq S,\) forms the Coxeter complex of \( W,\) and is well-studied. In this article we look at a less studied object: the set of all double cosets \( W_IwW_J \) for \( I,J \subseteq S.\) Double coset are not uniquely presented by triples \( (I,w,J).\) We describe what we call the lex-minimal presentation, and prove that there exists a unique such object for each double coset. Lex-minimal presentations are then used to enumerate double cosets via a finite automaton depending on the Coxeter graph for \( (W,S).\) As an example, we present a formula for the number of parabolic double cosets with a fixed minimal element when \( W \) is the symmetric group \(S_n \) (in this case, parabolic subgroups are also known as Young subgroups). Our formula is almost always linear time computable in \(n,\) and we show how it can be generalized to any Coxeter group with little additional work. We spell out formulas for all finite and affine Weyl groups in the case that \(w\) is the identity element.

29. Unimodality via alternating gamma vectors (with C. Brittenham, A. Carroll, and C. Thomas), Electronic Journal of Combinatorics, 20 (2016). abstract arXiv

For a polynomial with palindromic coefficients, unimodality is equivalent to having a nonnegative \(g\)-vector. A sufficient condition for unimodality is having a nonnegative \(\gamma\)-vector, though one can have negative entries in the \(\gamma\)-vector and still have a nonnegative \(g\)-vector. In this paper we provide combinatorial models for three families of \(\gamma\)-vectors that alternate in sign. In each case, the \(\gamma\)-vectors come from unimodal polynomials with straightforward combinatorial descriptions, but for which there is no straightforward combinatorial proof of unimodality. By using the transformation from \(\gamma\)-vector to \(g\)-vector, we express the entries of the \(g\)-vector combinatorially, but as an alternating sum. In the case of the \(q\)-analogue of \(n!\), we use a sign-reversing involution to interpret the alternating sum, resulting in a manifestly positive formula for the \(g\)-vector. In other words, we give a combinatorial proof of unimodality. We consider this a "proof of concept" result that we hope can inspire a similar result for the other two cases, \(\prod_{j=1}^n (1+q^j)\) and the \(q\)-binomial coefficients.

28. The Steinberg torus of a Weyl group as a module over the Coxeter complex (with M. Aguiar), Journal of Algebraic Combinatorics, 42, 1135-1175, (2015). abstract arXiv

For a crystallographic root system there are three natural cell structures: the Coxeter complex, the affine Coxeter complex, and the Steinberg torus. Both the finite and affine Coxeter complexes can be seen in the Tits cone, with the affine faces on the interior and the finite faces on the boundary. We show how the faces on the boundary act on the faces in the interior. The Steinberg torus is obtained by taking a quotient of the affine Complex by the lattice of coroots, and the action of the boundary passes through this quotient. (See paper 11 below for more on the Steinberg torus.) By studying the action of the Weyl group, we obtain a module structure on the space spanned by affine descent classes over the space spanned by ordinary descent classes, i.e., over Solomon's descent algebra.

27. The generating function for total displacement (with M. Guay-Paquet), Electronic Journal of Combinatorics, 21, (2014). abstract arXiv

This paper computes the generating function for the depth of a permutation, studied in paper 23 below. This statistic, \(\sum_i \max\{w(i)-i, 0\}\), was studied in work of Diaconis and Graham, and appears in exercises in Knuth's "Art of Computer Programming." An expression for the generating function was previously unknown. The expression we find is a continued fraction, based on a map from permutations to Motzkin paths that takes depth to area.

26. Power series for up-down min-max permutations (with F. Heneghan), College Math Journal, 45 (2014), 83-91. abstract pdf

This paper, intended for a general mathematical audience, derives generating functions for a certain subset of alternating permutations. The work comes out of an undergraduate research project done by Heneghan and another student, Ashley Sliva.

25. Counting Dyck paths by area and rank (with S. Blanco), Annals of Combinatorics, 18 (2014), 171-197. abstract arXiv

This paper started by asking for the joint distribution of length and reflection length (or inversion number and number of cycles) for the interval \([e, (12\cdots n)]\) in the absolute order on the symmetric group. This interval is well-known to be isomorphic to the lattice of noncrossing partitions. It turned out the distribution was quite nice, though it did not translate to other, isomorphic intervals in the absolute order. The result was really about good ol' "Catalan combinatorics," which we thought was best understood in terms of Dyck paths. We obtain an interesting \((q,t)\)-refinement of the Catalan numbers, and show it gives a refined Catalan recurrence of Carlitz and Riordan. Also, there is a refined notion of \(\gamma\)-nonnegativity for this joint distribution, something seen recently in the "cycle type Eulerian polynomials" of Shareshian and Wachs.

24. How to write a permutation as a product of involutions (and why you might care) (with B. E. Tenner), Integers, 13 (2013), #A63. abstract INT

We were inspired to write this article after noticing a strange coincidence between the number of ways to write a permutation of cycle type \(\mu\) as a product of involutions, and the absolute sum \( \sum_{\lambda} |\chi^{\lambda}(\mu)|\) of irreducible characters of the symmetric group. For \(n \leq 7\) these numbers agree, but afterwards the number of involution products usually exceeds the absolute sum of characters. There are a striking number of partitions \(\mu\) for which the numbers agree, however.

23. The depth of a permutation (with B. E. Tenner), Journal of Combinatorics, 6, 145-178, (2015). abstract arXiv

This paper presents a new permutation statistic, which we call depth. Like the sorting index below, it measures the cost of sorting a permutation with transpositions. The definition makes sense in any Coxeter group, but for permutations we prove it is simply \(\sum_i \max\{w(i)-i, 0\}\). Depth is at least as big as reflection length, i.e., \(n\) minus the number of cycles, and no bigger than length, i.e., the number of inversions. We find that those permutations for which depth equals length are precisely the 321-avoiding permutations, and those for which depth equals reflection length are those permutations avoiding both 321 and 3412. These are known as "boolean" permutations.

22. On the shard intersection order of a Coxeter group, SIAM Journal on Discrete Mathematics, 27 (2013), 1880-1912. abstract arXiv

Nathan Reading's shard intersection order gives a new and interesting partial order to any Coxeter group. While not self-dual, its rank generating function is the \(W\)-Eulerian polynomial, and it contains the lattice of \(W\)-noncrossing partitions as a sublattice. Bancroft proved EL-shellability of the shard intersection order for the symmetric group. Here we prove it for types \(A_n, B_n,\) and \(D_n\).
Further we prove that the shard intersection order for the symmetric group admits a symmetric boolean decomposition; i.e., a partition of the poset into disjoint boolean pieces so that these pieces have the same center of symmetry, about the middle rank of the poset.

21. Two-sided Eulerian numbers via balls in boxes, Mathematics Magazine, 86 (2013), 159-176. abstract arXiv

This article provides an elementary approach to the study of the joint distribution of descents and inverse descents in the symmetric group. We refer to the coefficients of this distribution as "two-sided" Eulerian numbers, i.e., the number of permutations with prescribed numbers of descents and inverse descents. (For Coxeter groups, descents are actually "right descents" and inverse descents are "left descents"; hence, the term "two-sided" seems appropriate.) The first section highlights a classic "balls in boxes" approach to some basic facts about Eulerian numbers. The second section modifies the approach to study both descents and inverse descents simultaneously. The third section discusses a conjecture of Gessel.

20. Many proofs that the primes are infinite, (with J. M. Ash), Journal of Recreational Mathematics, 36 (2007), 294-298. abstract pdf

This math-club-style note suggests many ways to prove the infinitude of the primes. It asks the reader to consider the nature of proof, and what constitutes a "novel" proof. Incidentally, the reason this paper's publication date is 2007 is because the journal went out of print for about 5 years. Rather than have a five-year gap in their issues, the journal decided to pick up where they left off. Hence this paper ``appeared" before I had ever met my coauthor!

19. Bounding reflection length in an affine Coxeter group, (with J. McCammond) Journal of Algebraic Combinatorics, 34 (2011), 711-719. abstract arXiv

We prove in this paper that any element of an affine Coxeter group of rank \(n\) has reflection length at most \(2n\), and this bound is sharp. We conjecture that affine Coxeter groups are the only infinite Coxeter groups for which the reflection length is bounded.

18. The sorting index, Advances in Applied Mathematics, 47 (2011), 615-630. abstract arXiv

The sorting index of a permutation is a measure of the amount of work needed to put the letters of the permutation in order using the ``straight selection sort" algorithm. Interestingly, this statistic has the same distribution as inversion number, which is itself a measure of the work needed to sort a permutation. The motivation for this paper is the following: there is a common generalization of the formulas for the distribution of length and reflection length in a finite Coxeter group, but it does not give the joint distribution of these statistics. What is it the joint distribution of? This paper gives the answer in types \(A_n\) and \(B_n\), and half an answer in type \(D_n\).

17. The gamma vector of a barycentric subdivision, (with E. Nevo and B. E. Tenner) Journal of Combinatorial Theory, Series A, 118 (2011), 1364-1380. abstract arXiv

This paper continues the work of paper 16 below. The main result is that the \(\gamma\)-vectors of barycentric subdivisions of simplicial spheres are \(f\)-vectors of balanced simplicial complexes, confirming the conjecture of paper 16 in this case. In the final section, we also show that if the gamma vector is the \(f\)-vector of a simplicial complex, then both the \(h\)-vector and \(g\)-vectors are \(f\)-vectors of simplicial complexes. (This is more evidence of the strength of the \(\gamma\) vector.)

16. On gamma vectors satisfying the Kruskal-Katona inequalities, (with E. Nevo) Discrete and Computational Geometry, 45 (2011), 503-521. abstract arXiv

The Kruskal-Katona inequalities characterize the \(f\)-vectors of simplicial complexes. We show that several families of flag simplicial spheres have \(gamma\)-vectors that satisfy these inequalities, suggesting an interpretation for the \(\gamma\)-nonnegativity of flag spheres conjectured by Gal. We conjecture that the \(\gamma\)-vector of a flag homology sphere is the \(f\)-vector of a (balanced) simplicial complex.

15. Cyclic sieving for longest reduced words in the hyperoctahedral group, (with L. Serrano) Electronic Journal of Combinatorics, 17 (2010) #R67. abstract EJC

We show that the set of reduced expressions for the longest element of the hyperoctahedral group exhibits the cyclic sieving phenomenon. This was first suggested by Rhoades, as a corollary to his CSP result for rectangular Young tableaux. We fill in the details of his argument, and show also that the polynomial used in the CSP can be characterized combinatorially, in terms of major index on the set of reduced expressions.

14. Euler-Mahonian distributions of type \(B_n\), (with L. M. Lai) Discrete Mathematics, 311 (2011), 645-650. abstract arXiv

This short note gives a bijective proof of a result of Adin, Brenti, and Roichman regarding type \(B_n\) analogues of the "Euler-Mahonian" distribution (i.e., the joint distribution of descents and major index).

13. A non-crossing standard monomial theory, (with P. Pylyavskyy and D. Speyer) Journal of Algebra, 324 (2010), 951-969. abstract arXiv

One of the uses for semi-standard Young tableaux is as an indexing set for a basis of the Plücker algebra (the "standard monomial basis"), and here we show how Pylyavskyy's non-crossing tableaux give a different basis. The approach is more geometric than algebraic; we describe a family of triangulations of the cone of Gelfand-Tsetlin patterns given by what we call "driving rules", each of which results in a basis of the Plücker algebra. Two special cases are studied in detail: the (standard) non-nesting case and the non-crossing case, which is new. The simplicial complexes arising from the driving rules are also discussed as interesting objects in their own right.

12. Promotion and cyclic sieving via webs, (with P. Pylyavskyy and B. Rhoades) Journal of Algebraic Combinatorics, 30 (2009), 19-41. abstract arXiv

We show that Schützenberger's action of jeu-de-taquin promotion on two and three row rectangular (standard) Young tableaux can be realized by cyclic rotation of certain planar graphs introduced by Kuperberg, called webs. We also show that this action admits the so-called cyclic sieving phenomenon. Further, the correspondence between rotation of webs and promotion of tableaux allows for a simpler proof of a result of Rhoades, at least in the special case of two and three row rectangles.

11. Affine descents and the Steinberg torus, (with K. Dilks and J. R. Stembridge) Advances in Applied Mathematics, 42 (2009), 423-444. abstract arXiv

This paper studies a descent-like statistic in irreducible Weyl groups. We show that the generating function for this statistic is the h-polynomial of a simplicial torus (the Steinberg torus) defined as the quotient of the affine Coxeter complex by the coroot lattice. We exhibit several interesting properties of these generating functions, including \(\gamma\)-nonnegativity (a property that implies symmetry and unimodality of the coefficients). Go here for pictures of Steinberg tori.

10. Colored posets and colored quasisymmetric functions, (with S. Hsiao) Annals of Combinatorics, 14 (2010), 251-289. abstract arXiv

We take the viewpoint that the algebras of quasisymmetric functions and peak functions are best understood in terms of the algebra of (equivalence classes of finite) labeled posets. \(P\)-partitions carry much of the structure of the algebra of posets through to the quasisymmetric functions. This paper introduces colored posets and colored \(P\)-partitions, both enriched and ordinary. We show the algebra of colored quasisymmetric functions is terminal in the category of colored combinatorial Hopf algebras.

9. The m-colored composition poset, (with B. Drake) Electronic Journal of Combinatorics 14 (2007) #R23. abstract EJC

In this paper we generalize the composition poset introduced by Bjorner and Stanley. Analogies are drawn with Young's lattice of partitions. Just as Young's lattice is connected to the symmetric functions, the composition poset is connected to quasisymmetric functions.

8. Conway's napkin problem, (with A. Claesson) American Mathematical Monthly, 114 (2007) 217-231. abstract arXiv

In this highly accessible article, we bring the tools of enumerative combinatorics to bear on a problem of Conway (as presented in Peter Winkler's book).

7. Enriched \(P\)-partitions and peak algebras, Advances in Mathematics, 209 (2007), 561-610. abstract arXiv

This paper modifies Gessel's \(P\)-partition approach to descent algebras to apply to peak algebras. Instead of Stanley's \(P\)-partitions, we use Stembridge's enriched \(P\)-partitions. The paper contains many interesting formulas in the group algebras of the symmetric or hyperoctahedral groups, including a summary of the results of paper 4 (below).

6. Enumerating segmented patterns in compositions and encoding with restricted permutations. (with S. Kitaev and T. McAllister) Integers, 6 (2006) #A34. abstract Integers

Enumeration of permutation patterns is a widely studied problem. Here we begin exploration of analogous questions for compositions.

5. A note on three types of quasisymmetric functions, Electronic Journal of Combinatorics 12 (2005) #R61. abstract EJC

This short paper outlines Gessel's \(P\)-partition approach to descent algebras, via duality with quasisymmetric functions.

4. Cyclic descents and \(P\)-partitions, Journal of Algebraic Combinatorics 22 (2005) 343-375. abstract arXiv

This paper uses analogs of \(P\)-partitions to produce formulas for orthogonal idempotents in various commutative subalgebras of Solomon's descent algebra.

3. An arctic circle theorem for groves. (with D. Speyer) Journal of Combinatorial Theory, Series A 111 (2005) 137-164. abstract arXiv

Groves are combinatorial objects based on the cube recurrence, which is closely related to the more widely studied octahedron recurrence. This paper explores the large scale behavior of a randomly selected grove, by analogy with the model of domino tilings of Aztec diamonds.

2. A reciprocity theorem for monomer-dimer coverings. (with N. Anzalone, J. Baldwin, and I. Bronshtein) Discrete Mathematics and Theoretical Computer Science, AB (2003) 179-194. abstract DMTCS

This paper generalizes work of Propp regarding the notion of "combinatorial reciprocity."

1. Polynomials over finite fields whose values are squares. Rose-Hulman Undergraduate Mathematics Journal 2 (2001), no. 1. abstract

I wrote this survey paper as an undergraduate.

Other work - probably won't appear elsewhere

Descents, peaks, and \(P\)-partitions, Ph.D. dissertation, Brandeis University, 2006. pdf

Most of the contents of the dissertation can be found in papers 4 and 7 above. The tricky part was getting the file to have exactly 100 pages!

The Hopf algebras of type B quasisymmetric functions and peak functions, (with S. Hsiao), 2006. arXiv

This short note establishes that the type B quasisymmetric functions have the structure of a Hopf algebra and the type B peak functions (as defined in paper 7 above) form a Hopf subalgebra.