Papers and publications

Wtih Juan Gil, Jordan Tirrell and Michael Weiner:
"From Dyck paths to standard Young tableaux," 19 pp., submitted.
Show/Hide abstract.
The number of Dyck paths of semilength $n$ is certainly not equal to the number of standard Young tableaux (SYT) with $n$ boxes. We investigate several ways to add structure or restrict these sets so as to obtain equinumerous sets. Our most sophisticated bijective proof starts with Dyck paths whose $k$ascents for $k>1$ are labeled by connected matchings on $[k]$ and arrives at SYT with at most $2k1$ rows. Along the way, this bijection visits $k$noncrossing and $k$nonnesting partial matchings, oscillating tableaux and involutions with decreasing subsequences of length at most $2k1$. In addition, we present bijections from eight other types of Dyck and Motzkin paths to certain classes of SYT.

With Daniel Birmajer, Juan Gil and Michael Weiner:
"Enumeration of colored Dyck paths via partial Bell polynomials," 10 pp., Proceedings of the 8th International Conference on Lattice Path Combinatorics and Applications, to appear.
Show/Hide abstract.
We consider a class of lattice paths with certain restrictions on their ascents and down steps and use them as building blocks to construct various families of Dyck paths. We let every building block $P_j$ take on $c_j$ colors and count all of the resulting colored Dyck paths of a given semilength. Our approach is to prove a recurrence relation of convolution type, which yields a representation in terms of partial Bell polynomials that simplifies the handling of different colorings. This allows us to recover multiple known formulas for Dyck paths and related lattice paths in a unified manner.

With Emmanuel Briand, Rosa Orellana and Mercedes Rosas:
"Commutation and normal ordering for operators on symmetric functions," 23 pp., submitted.
Show/Hide abstract.
We study the commutation relations and normal ordering between families of operators on symmetric functions. These operators can be naturally defined by the operations of multiplication, Kronecker product, and their adjoints. As applications we give a new proof of the skew LittlewoodRichardson rule and prove an identity about the Kronecker product with a skew Schur function.

With Sergi Elizalde:
"The structure of the consecutive pattern poset,", International Mathematics Research Notices, to appear, 29 pp.
Show/Hide abstract.
The consecutive pattern poset is the infinite partially ordered set of all permutations where $\sigma\le\tau$ if $\tau$ has a subsequence of adjacent entries in the same relative order as the entries of $\sigma$. We study the structure of the intervals in this poset from topological, posettheoretic, and enumerative perspectives. In particular, we prove that all intervals are rankunimodal and strongly Sperner, and we characterize disconnected and shellable intervals. We also show that most intervals are not shellable and have Möbius function equal to zero.

With Sara Billey:
"The contributions of Stanley to the fabric of symmetric and quasisymmetric functions,", chapter in The Mathematical Legacy of Richard P. Stanley, P. Hersh, T. Lam, P. Pylyavskyy, and V. Reiner (Eds.), American Mathematical Society, 2016, 83–104.
Show/Hide abstract.
We weave together a tale of two rings, SYM and QSYM, following one gold
thread spun by Richard Stanley. The lesson we learn from this tale is
that "Combinatorial objects like to be counted by quasisymmetric
functions."

"Comparing skew Schur functions: a quasisymmetric perspective," Journal of Combinatorics, 5 (1) (2014), 51–85.
Show/Hide abstract.
Reiner, Shaw and van Willigenburg showed that if two skew Schur functions $s_A$ and $s_B$ are equal, then the skew shapes $A$ and $B$ must have the same ``row overlap partitions.''
Here we show that these row overlap equalities are also implied by a much weaker condition than skew Schur equality: that $s_A$ and $s_B$ have the same support when expanded in the fundamental quasisymmetric basis $F$. Surprisingly, there is significant evidence supporting a conjecture that the converse is also true.
In fact, we work in terms of inequalities, showing that if the $F$support of $s_A$ contains that of $s_B$, then the row overlap partitions of $A$ are dominated by those of $B$, and again conjecture that the converse also holds. Our evidence in favor of these conjectures includes their consistency with a complete determination of all $F$support containment relations for $F$multiplicityfree skew Schur functions. We conclude with a consideration of how some other quasisymmetric bases fit into our framework.

With Einar Steingrímsson: "On the topology of the permutation pattern poset," Journal of Combinatorial Theory (Series A), 134 (2015), 1–35.
Show/Hide abstract.
The set of all permutations, ordered by pattern containment, forms a poset. This paper presents the first explicit major results on the topology of intervals in this poset. We show that almost all (open) intervals in this poset have a disconnected subinterval and are thus not shellable. Nevertheless, there seem to be large classes of intervals that are shellable and thus have the homotopy type of a wedge of spheres. We prove this to be the case for all intervals of layered permutations that have no disconnected subintervals of rank 3 or more. We also characterize in a simple way those intervals of layered permutations that are disconnected. These results carry over to the poset of generalized subword order when the ordering on the underlying alphabet is a rooted forest. We conjecture that the same applies to intervals of separable permutations, that is, that such an interval is shellable if and only if it has no disconnected subinterval of rank 3 or more. We also present a simplified version of the recursive formula for the Möbius function of decomposable permutations given by Burstein et al.

With Ryan Ward: "Equality of Ppartition generating functions," Annals of Combinatorics, 18 (3) (2014), 489–514.
Show/Hide abstract.
To every labeled poset $(P,\omega)$, one can associate a quasisymmetric generating function for its $(P,\omega)$partitions. We ask: when do two labeled posets have the same generating function? Since the special case corresponding to skew Schur function equality is still open, a complete classification of equality among $(P,\omega)$ generating functions is likely too much to expect. Instead, we determine necessary conditions and separate sufficient conditions for two labeled posets to have equal generating functions. We conclude with a classification of all equalities for labeled posets with small numbers of linear extensions.

With Stephanie van Willigenburg: "Maximal supports and Schurpositivity among connected skew shapes," European Journal of Combinatorics, 33 (6) (2012), 1190–1206.
Show/Hide abstract.
The Schurpositivity order on skew shapes is defined by $B \leq A$ if the difference $s_A  s_B$ is Schurpositive. It is an open problem to determine those connected skew shapes that are maximal with respect to this ordering. A strong necessary condition for the Schurpositivity of $s_A s_B$ is that the support of $B$ is contained in that of $A$, where the support of $B$ is defined to be the set of partitions $\lambda$ for which $s_\lambda$ appears in the Schur expansion of $s_B$. We show that to determine the maximal connected skew shapes in the Schurpositivity order and this support containment order, it suffices to consider a special class of ribbon shapes. We explicitly determine the support for these ribbon shapes, thereby determining the maximal connected skew shapes in the support containment order.

With Bruce Sagan: "The Möbius function of generalized subword order,"
Advances in Mathematics, 229 (5) (2012), 2741–2766.
Show/Hide abstract.
Let $P$ be a poset and let $P^*$ be the set of all finite length words over $P$. Generalized subword order is the partial order on $P^*$ obtained by letting $u\le w$ if and only if there is a subword $u$' of $w$ having the same length as $u$ such that each element of $u$ is less than or equal to the corresponding element of $u$' in the partial order on $P$. Classical subword order arises when $P$ is an antichain, while letting $P$ be a chain gives an order on compositions. For any finite poset $P$, we give a simple formula for the Möbius function of $P^*$ in terms of the Möbius function of $P$. This permits us to rederive in an easy and uniform manner previous results of Björner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in $P^*$ for any finite $P$ of rank at most 1.

With Sami Assaf and an appendix by Thomas Lam:
"A Pieri Rule for Skew Shapes," Journal of Combinatorial Theory (Series A), 118 (1) (2011), 277–290.
Show/Hide abstract.
The Pieri rule expresses the product of a Schur function and a single row Schur function in terms of Schur functions. We extend the classical Pieri rule by expressing the product of a skew Schur function and a single row Schur function in terms of skew Schur functions. Like the classical rule, our rule involves simple additions of boxes to the original skew shape.
Our proof is purely combinatorial and extends the combinatorial proof of the classical case.

With Bruce Sagan:
"Infinite Logconcavity: Developments and Conjectures," Advances in Applied Mathematics, 44 (1) (2010), 1–15.
Show/Hide abstract.
Given a sequence $(a_k) = a_0, a_1, a_2,\ldots$ of real numbers,
define a new sequence $\mathcal{L}(a_k) = (b_k)$ where $b_k = a_k^2  a_{k1} a_{k+1}$. So $(a_k)$ is logconcave if and only if $(b_k)$ is a nonnegative sequence. Call $(a_k)$ infinitely logconcave if $\mathcal{L}^i(a_k)$ is nonnegative for all
$i \geq 1$. Boros and Moll conjectured that the rows of Pascal's triangle are infinitely logconcave. Using a computer and a stronger version of logconcavity, we prove their conjecture for the $n$th row for all $n \leq 1450$. We also use our methods to give a simple proof of a recent result of Uminsky and Yeats about regions of infinite logconcavity. We investigate related questions about the columns of Pascal's triangle, $q$analogues, symmetric functions, realrooted polynomials, and Toeplitz matrices. In addition, we offer several conjectures.

With Stephanie van Willigenburg:
"Positivity Results on Ribbon Schur Function Differences," European Journal of Combinatorics, 30 (5) (2009), 1352–1369.
Show/Hide abstract.
There is considerable current interest in
determining when the difference of two skew Schur functions is Schur positive. While the general solution for ribbon Schur functions
seems out of reach at present,
we determine
necessary and sufficient conditions for multiplicityfree ribbons,
i.e. those whose expansion as a linear combination of Schur functions has all coefficients either
zero or one. In particular, we show that the poset that results from ordering such ribbons according
to Schur positivity is essentially a product of two chains.

"Necessary Conditions for SchurPositivity," Journal of Algebraic Combinatorics, 28 (4) (2008), 495–507.
Show/Hide abstract.
In recent years, there has been considerable interest in
showing that certain conditions on skew shapes A and B
are sufficient for
the difference s_{A}  s_{B}
of their skew Schur functions
to be Schurpositive.
We determine necessary conditions
for the difference to be Schurpositive. Our conditions are motivated by those
of Reiner, Shaw and van Willigenburg that are necessary for
s_{A} = s_{B}, and we deduce a
strengthening of their result as a special case.

With Stephanie van Willigenburg:
"Towards a Combinatorial Classification of Skew Schur Functions," Transactions of the American Mathematical Society, 361 (8) (2009), 4437–4470.
Show/Hide abstract.
We present a single operation for constructing skew diagrams whose
corresponding skew Schur functions are equal. This combinatorial operation
naturally generalises and unifies all results of this type to date.
Moreover, our operation suggests a closely related condition that we
conjecture is necessary and sufficient for skew diagrams to yield equal
skew Schur functions.

With Christophe Reutenauer:
"PPartitions and a MultiParameter Klyachko Idempotent,"
Electronic Journal of Combinatorics, 11 (2) (2005), #R21, 18 pp.
Special volume in honor of Richard Stanley on the occasion of his 60th
birthday.
Show/Hide abstract.
Because they
play a role in our understanding of
the symmetric group algebra, Lie idempotents
have received considerable attention.
The Klyachko idempotent has attracted interest from combinatorialists,
partly because its definition involves the major index of permutations.
For the symmetric group S_{n}
we look at the symmetric group algebra with coefficients from the
field of rational functions in
n variables q_{1}, q_{2}, ... , q_{n}.
In this setting, we can define an nparameter generalization
of the Klyachko idempotent, and we show it is a Lie idempotent
in the appropriate sense. Somewhat surprisingly, our proof that it
is a Lie element emerges from Stanley's theory of Ppartitions.

With François Bergeron:
"Some Positive Differences of Products of Schur Functions."
Show/Hide abstract.
There is also an
update.
The product s_{μ} s_{ν} of two Schur functions is one of the most famous examples of a Schurpositive function, i.e. a symmetric function which, when written as a linear combination of Schur functions, has all positive coefficients. We ask when expressions of the form
s_{λ} s_{ρ}  s_{μ} s_{ν} are Schurpositive. This general question seems to be a difficult one, but a conjecture of Fomin, Fulton, Li and Poon says that it is the case at least when λ and ρ are obtained from μ and ν by redistributing the parts of μ and ν in a specific, yet natural, way. We show that their conjecture is true in several significant cases. We also formulate a skewshape extension of their conjecture, and prove several results which serve as evidence in favor of
this extension. Finally, we take a more global view by studying two classes of partially ordered sets suggested by these questions.

With Charles R. Johnson, Stefan Leichenauer and Roberto Costas:
"Principal Minor Sums of (A+tB)^{m},"
Linear Algebra and its Applications, 411 (2005), 386–389.
Special issue on determinants and the legacy of Sir Thomas Muir.
Show/Hide abstract.
The question is raised whether the sum of the kbyk
principal minors of the titled matrix is a polynomial (in t)
with positive coefficients, when A and B are
positivedefinite. This would generalize a conjecture made
by BessisMoussaVillani, as stated by Lieb and Seiringer. We give
a variety of evidence for this further question, some of which is new.

"Cylindric Skew Schur Functions,"
Advances in Mathematics, 205 (1) (2006), 275–312.
Show/Hide abstract.
Cylindric skew Schur functions, which are
a generalisation of skew Schur functions,
arise naturally in the study of Ppartitions.
Also, recent work of A. Postnikov shows they
have a strong connection with a problem of considerable current
interest: that of finding a combinatorial
proof of the nonnegativity of the 3point GromovWitten invariants.
After explaining these motivations, we study cylindric skew Schur functions
from the point of view of Schurpositivity.
Using a result of I. Gessel and C. Krattenthaler,
we generalise a formula of A. Bertram, I. CiocanFontanine
and W. Fulton, thus
giving an expansion of an arbitrary cylindric skew Schur
function in terms of skew
Schur functions.
While we show that no nontrivial cylindric skew Schur functions
are Schurpositive, we conjecture that this
can be reconciled using the new concept
of cylindric Schurpositivity.

"Edge Labellings of Partially Ordered Sets," Ph.D. thesis, MIT, 2003.
Show/Hide abstract.
There is also an
update.
It is well known that if a finite graded lattice of rank n is
supersolvable, then it has an ELlabelling where the labels along any
maximal chain form a permutation of ${1,2,...,n}$. We call such
a labelling an $S_n$ ELlabelling and we show that a finite graded
lattice of rank n is supersolvable if and only if it has such
a labelling. This result can be used to show that a graded lattice is
supersolvable if and only if it has a maximal chain of left modular
elements. (An example of an $S_n$ ELlabelling is shown below.)
Our next goal is to extend these equivalences to lattices that need
not be graded and, furthermore, to bounded posets that
need not be lattices. In joint work with Hugh Thomas, we define
left modularity in this setting, as well as a natural extension
of $S_n$ ELlabellings, known as interpolating labellings.
We also suitably extend the
definition of lattice supersolvability to arbitrary bounded graded posets.
We show that these extended definitions preserve the appropriate
equivalences.
Finally, we move to the study of $P$partitions.
Here, edges are labelled as either "strict" or "weak" depending on
an underlying labelling of the elements of the poset.
A wellknown conjecture of R. Stanley states that the quasisymmetric
generating function for $P$partitions is symmetric if and only
if $P$ is isomorphic to a Schur labelled skew shape poset.
In characterizing these skew shape posets in terms of their local
structure, C. Malvenuto made significant progress on this conjecture.
We generalize the definition of $P$partitions by letting the
set of strict
edges be arbitrary. Using cylindric diagrams, we extend
Stanley's conjecture and Malvenuto's characterization to this setting.
We conclude by proving both conjectures for large classes of posets.
March 2004.
Conjecture 5.4.6, the extension of Stanley's Conjecture, is false.
In other words, there exist oriented posets that are not isomorphic to
cylindric skew shapes but whose generating functions are symmetric.
The smallest counterexamples have 7 vertices, and are shown below.
These examples
were found using
John Stembridge's posets package for Maple.

With Hugh Thomas:
"Poset EdgeLabellings and Left Modularity,"
European Journal of Combinatorics, 27 (1) (2006), 101–113.
A bonus section not included in the published version
introduces the nonstraddling partitions of [n], a subset
of the nonnesting partitions of [n].
Show/Hide abstract.
It is known that a graded lattice of rank $n$ is supersolvable if and only
if it has an ELlabelling where the labels along any maximal chain are
exactly
the numbers $1,2,\ldots,n$ without repetition. These labellings are called
$S_n$ ELlabellings, and having such a labelling is also equivalent to
possessing a maximal chain of left modular elements. In the case of an
ungraded lattice, there is a natural extension of $S_n$ ELlabellings,
called interpolating labellings. We show that admitting an interpolating
labelling is again equivalent to possessing a maximal chain of left modular
elements. Furthermore, we work in the setting of a general bounded poset
as all the above results generalize to this case.
We conclude by applying our results to show that the
lattice of nonstraddling partitions, which is not graded in general, has a
maximal chain of left modular elements.
 "ELlabelings, Supersolvability and 0Hecke Algebra Actions on Posets,"
Journal of Combinatorial Theory (Series A), 101 (1) (2003), 69–89.
Show/Hide abstract.
It is well known that if a finite graded lattice of rank $n$ is supersolvable,
then it has an ELlabeling where the labels along any maximal chain form
a permutation. We call such a labeling an $S_n$ ELlabeling and we show
that a finite graded lattice of rank n is supersolvable
if and only if it has such a labeling. We next consider finite graded posets
of rank n with unique top and bottom elements that have an $S_n$
ELlabeling. We describe a type A 0Hecke
algebra action on the maximal chains of such posets. This action
is local and gives a representation of these Hecke algebras whose character
has characteristic that is closely related to Ehrenborg's flag
quasisymmetric function. We ask what other classes of posets have such
an action and in particular we show that finite graded lattices of rank
n have such an action if and only if they have an $S_n$ ELlabeling.