List of papers ordered by topic. Some papers are listed several times as they cover two or more major topics.  The full list of papers in reverse chronological order is in the CV. 

Computational Complexity Theory 

Computational Complexity in Algebraic Combinatorics, Current Developments in Mathematics 2023.

Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives and brought us some beautiful formulas and combinatorial interpretations. The flagship hook-length formula counts the number of Standard Young Tableaux, which also gives the dimension of the irreducible Specht modules of the Symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory.
We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, that could formally explain the beauty we see and the difficulties we encounter in finding further formulas and ``combinatorial interpretations''. A 85-year-old such problem asks for a positive combinatorial formula for the Kronecker coefficients of the Symmetric group, another one pertains to the plethysm coefficients of the General Linear group.
In the opposite direction, the study of Kronecker and plethysm coefficients leads to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation theoretic multiplicities in further detail, possibly asymptotically.

Positivity of the Symmetric group characters is as hard as the polynomial time hierarchy (with Ch. Ikenmeyer, I. Pak)  Proc. 34th SODA, SIAM, 2023

We prove that deciding the vanishing of the character of the symmetric group is C_=P-complete. We use this hardness result to prove that the the square of the character is not contained in #P, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is PP-complete under many-one reductions, and hence PH-hard under Turing-reductions. 

On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions (with J. Dorfler, Ch. Ikenemeyer), SIAM Journal on Applied Algebra and Geometry 4 (2), 354-376. Presented at 46th Int. Col. on Automata, Languages, and Programming (ICALP) 2019, doi: 10.4230/LIPIcs.ICALP.2019.51.

Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. The papers also conjecture that the vanishing behavior of these multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and Bürgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. This paper provides for the first time a setting where separating with multiplicities can be achieved, while the separation with occurrences is provably impossible. Our setting is surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite's reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases.

Geometric Complexity Theory and Matrix Powering (with Fulvio Gesmundo, Christian Ikenmeyer) Diff. Geom. and Its Applications 55(2017), pp 106--127. 

Valiant's famous determinant versus permanent problem is the flagship problem in algebraic complexity theory. Mulmuley and Sohoni (Siam J Comput 2001, 2008) introduced geometric complexity theory, an approach to study this and related problems via algebraic geometry and representation theory. Their approach works by multiplying the permanent polynomial with a high power of a linear form (a process called padding) and then comparing the orbit closures of the determinant and the padded permanent. This padding was recently used heavily to show no-go results for the method of shifted partial derivatives (Efremenko, Landsberg, Schenck, Weyman, 2016) and for geometric complexity theory (Ikenmeyer Panova, FOCS 2016 and B\"urgisser, Ikenmeyer Panova, FOCS 2016). Following a classical homogenization result of Nisan (STOC 1991) we replace the determinant in geometric complexity theory with the trace of a variable matrix power. This gives an equivalent but much cleaner homogeneous formulation of geometric complexity theory in which the padding is removed. This radically changes the representation theoretic questions involved to prove complexity lower bounds. We prove that in this homogeneous formulation there are no orbit occurrence obstructions that prove even superlinear lower bounds on the complexity of the permanent. This is the first no-go result in geometric complexity theory that rules out superlinear lower bounds in some model. Interestingly---in contrast to the determinant---the trace of a variable matrix power is not uniquely determined by its stabilizer.

No occurrence obstructions in geometric complexity theory (with Peter Burgisser, Christian Ikenmeyer), J. Amer. Math. Soc. 32 (2019), pp. 163-193 , doi.org/10.1090/jams/908  . Extended abstract at FOCS 2016. 

The permanent versus determinant conjecture is a major problem in complexity theory that is equivalent to the separation of the complexity classes VP_{ws} and VNP. Mulmuley and Sohoni (SIAM J Comput, 2008) suggested to study a strengthened version of this conjecture over the complex numbers that amounts to separating the orbit closures of the determinant and padded permanent polynomials. In that paper it was also proposed to separate these orbit closures by exhibiting occurrence obstructions, which are irreducible representations of GL_{n^2}(C), which occur in one coordinate ring of the orbit closure, but not in the other. We prove that this approach is impossible. We alsoshow positivity for a certain class of plethysm coefficients.

Rectangular Kronecker coefficients and plethysms in geometric complexity theory (with Christian Ikenmeyer), Adv. Math. 319(2017), pp. 40--66. Extended abstract at FOCS 2016. 

We prove that in the geometric complexity theory program the vanishing of rectangular Kronecker coefficients cannot be used to prove superpolynomial determinantal complexity lower bounds for the permanent polynomial. Moreover, we prove the positivity of rectangular Kronecker coefficients for a large class of partitions where the side lengths of the rectangle are at least quadratic in the length of the partition. We also compare rectangular Kronecker coefficients with their corresponding plethysm coefficients, which leads to a new lower bound for rectangular Kronecker coefficients. Moreover, we prove that the saturation of the rectangular Kronecker semigroup is trivial, we show that the rectangular Kronecker positivity stretching factor is 2 for a long first row, and we completely classify the positivity of rectangular limit Kronecker coefficients that were introduced by Manivel in 2011.

On the complexity of computing Kronecker coefficients (with Igor Pak).  Comput. Complexity,  26 (2017), no. 1, pp.1--36.

We study the complexity of computing the Kronecker coefficients g(λ,μ,ν). We give explicit bounds in terms of the number of parts ℓ in the partitions, their largest part size N and the smallest second part M of the three partitions. When M = O(1), i.e. one of the partitions is hook-like, the bounds are linear in logN, but depend exponentially on ℓ. Moreover, similar bounds hold even when M=e^O(ℓ). By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(logN) time for a bounded number ℓ of parts and without restriction on M. Related problems of computing Kronecker coefficients when one partition is a hook, and computing characters of S_n are also considered.

Kronecker coefficients of the Symmetric Group

The Newton polytope of the Kronecker product (with Chenchen Zhao), submitted 2023.

We study the Kronecker product of two Schur functions sλ∗sμ, defined as the image of the characteristic map of the product of two Sn irreducible characters. We prove special cases of a conjecture of Monical--Tokcan--Yong that its monomial expansion has a saturated Newton polytope. Our proofs employ the Horn inequalities for positivity of Littlewood-Richardson coefficients and imply necessary conditions for the positivity of Kronecker coefficients.

Computational Complexity in Algebraic Combinatorics, Current Developments in Mathematics 2023 Proceedings.

Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives and brought us some beautiful formulas and combinatorial interpretations. The flagship hook-length formula counts the number of Standard Young Tableaux, which also gives the dimension of the irreducible Specht modules of the Symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory.
We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, that could formally explain the beauty we see and the difficulties we encounter in finding further formulas and ``combinatorial interpretations''. A 85-year-old such problem asks for a positive combinatorial formula for the Kronecker coefficients of the Symmetric group, another one pertains to the plethysm coefficients of the General Linear group.
In the opposite direction, the study of Kronecker and plethysm coefficients leads to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation theoretic multiplicities in further detail, possibly asymptotically.

Complexity and asymptotics of structure constants, to appear in Open Problems in Algebraic Combinatorics (OPAC 2022) Proceedings

Kostka, Littlewood-Richardson, Kronecker, and plethysm coefficients are fundamental quantities in algebraic combinatorics, yet many natural questions about them stay unanswered for more than 80 years. Kronecker and plethysm coefficients lack ``nice formulas'', a notion that can be formalized using computational complexity theory. Beyond formulas and combinatorial interpretations, we can attempt to understand their asymptotic behavior in various regimes, and inequalities they could satisfy. Understanding these quantities has applications beyond combinatorics. On the one hand, the asymptotics of structure constants is closely related to understanding the [limit] behavior of vertex and tiling models in statistical mechanics. More recently, these structure constants have been involved in establishing computational complexity lower bounds and separation of complexity classes like VP vs VNP, the algebraic analogs of P vs NP in arithmetic complexity theory. Here we discuss the outstanding problems related to asymptotics, positivity, and complexity of structure constants focusing mostly on the Kronecker coefficients of the symmetric group and, less so, on the plethysm coefficients.
This expository paper is based on the talk presented at the Open Problems in Algebraic Combinatorics coneference in May 2022. 

All Kronecker coefficients are reduced Kronecker coefficients (with Ch. Ikenmeyer), submitted 2023.

We settle the question of where exactly the reduced Kronecker coefficients lie on the spectrum between the Littlewood-Richardson and Kronecker coefficients by showing that every Kronecker coefficient of the symmetric group is equal to a reduced Kronecker coefficient by an explicit construction. This implies the equivalence of a question by Stanley from 2000 and a question by Kirillov from 2004 about combinatorial interpretations of these two families of coefficients. Moreover, as a corollary, we deduce that deciding the positivity of reduced Kronecker coefficients is 

NP-hard, and computing them is #P-hard under parsimonious many-one reductions. 

Durfee squares, symmetric partitions and bounds on Kronecker coefficients (with I. Pak).

We resolve two open problems on Kronecker coefficients g(λ,μ,ν) of the symmetric group. First, we prove that for partitions λ,μ,ν with fixed Durfee square size, the Kronecker coefficients grow at most polynomially. Second, we show that the maximal Kronecker coefficients g(λ,λ,λ) for self-conjugate partitions λ grow superexponentially. We also give applications to explicit special cases. 

Breaking down the reduced Kronecker coefficients (with I.Pak),  Comptes Rendus Mathématique, to appear. 

We resolve three interrelated problems on reduced Kronecker coefficients  g¯(α,β,γ). First, we disprove the saturation property which states that g¯(Nα,Nβ,Nγ)>0 implies g¯(α,β,γ)>0 for all N>1. Second, we estimate the maximal g¯(α,β,γ), over all |α|+|β|+|γ|=n. Finally, we show that computing g¯(λ,μ,ν) is strongly #P-hard, i.e. #P-hard when the input (λ,μ,ν) is in unary. 

Upper bounds on Kronecker coefficients with few rows (with I. Pak), Linear Algebra and Its Applications 602 (2020), pp. 157-178.

We present three different upper bounds for Kronecker coefficients g(λ,μ,ν) in terms of Kostka numbers, contingency tables and Littlewood--Richardson coefficients. We then give various examples, asymptotic applications, and compare them with existing lower bounds.  Short version of paper,  with some finer error terms.

Counting partitions inside a rectangle. (with S. Melczer, R. Pemantle), SIAM J. Disc. Math. (2020). Extended Abstract at FPSAC 2019, Disc. Math. Theoretical Comp.  Sci. Proceedings.

We consider the number of partitions of n whose Young diagrams fit inside an m x l rectangle; equivalently, we study the coefficients of the q-binomial coefficient (m+l choose m)_q. We obtain sharp asymptotics throughout the regime l=Theta(m) and n=Theta(m^2). Previously, sharp asymptotics were derived by Takacs only in the regime where |n-lm/2|=O(\sqrt{lm(l+m)}) using a local central limit theorem. Our approach is to solve a related large deviation problem: we describe the tilted measure that produces configurations whose bounding rectangle has the given aspect ratio and is filled to the given proportion. Our results are sufficiently sharp to yield the first asymptotic estimates on the consecutive differences of these numbers when n is increased by one and m,l remain the same, hence significantly refining Sylvester's unimodality theorem and the asymptotics of two-row Kronecker coefficients.

Bounds on the largest Kronecker and induced multiplicities of finite groups (with I. Pak, D. Yeliussizov), Comm. Algebra (April 2019), doi.org/10.1080/00927872.2018.1555837.

We give new bounds and asymptotic estimates on the largest Kronecker and induced multiplicities of finite groups. The results apply to large simple groups of Lie type and other groups with few conjugacy classes.

On the largest Kronecker and Littlewood--Richardson coefficients (with I. Pak, D. Yeliussizov), J. Comb. Theory Ser. A, 165 (2019), pp. 44--77 , doi.org/10.1016/j.jcta.2019.01.008. 

We give new bounds and asymptotic estimates for Kronecker and Littlewood--Richardson coefficients. Notably, we resolve Stanley's questions on the shape of partitions attaining the largest Kronecker and Littlewood--Richardson coefficients. We apply the results to asymptotics of the number of standard Young tableaux of skew shapes.

Rectangular Kronecker coefficients and plethysms in geometric complexity theory (with Christian Ikenmeyer), Adv. Math. 319(2017), pp. 40--66. Extended abstract at FOCS 2016. 

We prove that in the geometric complexity theory program the vanishing of rectangular Kronecker coefficients cannot be used to prove superpolynomial determinantal complexity lower bounds for the permanent polynomial. Moreover, we prove the positivity of rectangular Kronecker coefficients for a large class of partitions where the side lengths of the rectangle are at least quadratic in the length of the partition. We also compare rectangular Kronecker coefficients with their corresponding plethysm coefficients, which leads to a new lower bound for rectangular Kronecker coefficients. Moreover, we prove that the saturation of the rectangular Kronecker semigroup is trivial, we show that the rectangular Kronecker positivity stretching factor is 2 for a long first row, and we completely classify the positivity of rectangular limit Kronecker coefficients that were introduced by Manivel in 2011.

Bounds on Kronecker and q-binomial coefficients (with I. Pak), J. Combin. Theory Ser. A 147 (2017), pp. 1--17.

We present a lower bound on the Kronecker coefficients of the symmetric group via the characters of Sn, which we apply to obtain various explicit estimates. Notably, we extend Sylvester's unimodality of q-binomial coefficients (n choose k)_q as polynomials in q to derive sharp bounds on the differences of their consecutive coefficients. 

This paper was preceeded by the following: Bounds on the Kronecker coefficients( with I. Pak). It contains a proof of k-stability of the Kronecker coefficients generalizing the (usual) stability, and giving a new upper bound on the Kronecker coefficients.

Strict unimodality of q-binomial coefficients (with Igor Pak). C. R. Math. Acad. Sci. Paris 351(2013), no. 11-12, pp.415--418. http://dx.doi.org/10.1016/j.crma.2013.06.008. 

We prove strict unimodality of the q-binomial (Gaussian) coefficients as polynomials in q. The proof is based on the combinatorics of certain Young tableaux and the semigroup property of Kronecker coefficients of S_n representations.

Unimodality via Kronecker products (with Igor Pak). J. of Alg. Comb. (2014), 40(4), pp. 1103-1120. 

We present new proofs and generalizations of unimodality of the q-binomial coefficients \binom{n}{k}_q as polynomials in q. We use an algebraic approach by interpreting the differences between numbers of certain partitions as Kronecker coefficients of representations of S_n. Other applications of this approach include strict unimodality of the diagonal q-binomial coefficients and unimodality of certain partition statistics.

On the complexity of computing Kronecker coefficients (with Igor Pak).  Comput. Complexity,  26 (2017), no. 1, pp.1--36.

We study the complexity of computing the Kronecker coefficients g(λ,μ,ν). We give explicit bounds in terms of the number of parts ℓ in the partitions, their largest part size N and the smallest second part M of the three partitions. When M = O(1), i.e. one of the partitions is hook-like, the bounds are linear in logN, but depend exponentially on ℓ. Moreover, similar bounds hold even when M=e^O(ℓ). By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(logN) time for a bounded number ℓ of parts and without restriction on M. Related problems of computing Kronecker coefficients when one partition is a hook, and computing characters of S_n are also considered.

Kronecker products, characters, partitions, and the tensor square conjectures  (with Igor Pak and Ernesto Vallejo), Adv. in Math. 288 (2016), pp. 702--731. Extended Abstract at FPSAC 2014.

We study the remarkable Saxl conjecture which states that tensor squares of certain irreducible representations of the symmetric groups S_n contain all irreducibles as their constituents. Our main result is that they contain representations corresponding to hooks and two row Young diagrams. For that, we develop a new sufficient condition for the positivity of Kronecker coefficients in terms of characters, and use combinatorics of rim hook tableaux combined with known results on unimodality of certain partition functions. We also present connections and speculations on random characters of S_n. 

Asymptotic Algebraic Combinatorics

 Durfee squares, symmetric partitions and bounds on Kronecker coefficients (with I. Pak).

We resolve two open problems on Kronecker coefficients g(λ,μ,ν) of the symmetric group. First, we prove that for partitions λ,μ,ν with fixed Durfee square size, the Kronecker coefficients grow at most polynomially. Second, we show that the maximal Kronecker coefficients g(λ,λ,λ) for self-conjugate partitions λ grow superexponentially. We also give applications to explicit special cases. 

Sorting probability for large Young diagrams (with S.H. Chan, I. Pak), Discrete Analysis (2021).

For a finite poset P=(X,≺), let L denote the set of linear extensions of P. The sorting probability δ(P) is defined as 

δ(P):=min_{x,y∈X} |P[L(x)≤L(y)] − P[L(y)≤L(x)]|,

where L∈L is a uniform linear extension of P. We give asymptotic upper bounds on sorting probabilities for posets associated with large Young diagrams and large skew Young diagrams, with bounded number of rows. 

Upper bounds on Kronecker coefficients with few rows (with I. Pak), Linear Algebra and Its Applications 602 (2020), pp. 157-178.

We present three different upper bounds for Kronecker coefficients g(λ,μ,ν) in terms of Kostka numbers, contingency tables and Littlewood--Richardson coefficients. We then give various examples, asymptotic applications, and compare them with existing lower bounds.  Short version of paper,  with some finer error terms.

Counting partitions inside a rectangle. (with S. Melczer, R. Pemantle), SIAM J. Disc. Math. (2020). Extended Abstract at FPSAC 2019, Disc. Math. Theoretical Comp.  Sci. Proceedings.

We consider the number of partitions of n whose Young diagrams fit inside an m x l rectangle; equivalently, we study the coefficients of the q-binomial coefficient (m+l choose m)_q. We obtain sharp asymptotics throughout the regime l=Theta(m) and n=Theta(m^2). Previously, sharp asymptotics were derived by Takacs only in the regime where |n-lm/2|=O(\sqrt{lm(l+m)}) using a local central limit theorem. Our approach is to solve a related large deviation problem: we describe the tilted measure that produces configurations whose bounding rectangle has the given aspect ratio and is filled to the given proportion. Our results are sufficiently sharp to yield the first asymptotic estimates on the consecutive differences of these numbers when n is increased by one and m,l remain the same, hence significantly refining Sylvester's unimodality theorem.

Asymptotics of principal evaluations of Schubert polynomials for layered permutations (with A. Morales, I. Pak), Proc. Amer. Math. Soc, doi.org/10.1090/proc/14369 (2018).

Denote by u(n) the largest principal specialization of the Schubert polynomial: u(n):=max_{w in S_n} Sch_w(1,..,1) Stanley conjectured in [arXiv:1704.00851] that there is a limit as n goes to infinity of n^{-2} log u(n), and asked for a limiting description of permutations achieving the maximum u(n). Merzon and Smirnov conjectured in [arXiv:1410.6857] that this maximum is achieved on layered permutations. We resolve both Stanley's problems restricted to layered permutations.

Bounds on the largest Kronecker and induced multiplicities of finite groups (with I. Pak, D. Yeliussizov), Comm. Algebra (April 2019), doi.org/10.1080/00927872.2018.1555837.

We give new bounds and asymptotic estimates on the largest Kronecker and induced multiplicities of finite groups. The results apply to large simple groups of Lie type and other groups with few conjugacy classes.

On the largest Kronecker and Littlewood--Richardson coefficients (with I. Pak, D. Yeliussizov), J. Comb. Theory Ser. A, 165 (2019), pp. 44--77 , doi.org/10.1016/j.jcta.2019.01.008. 

We give new bounds and asymptotic estimates for Kronecker and Littlewood--Richardson coefficients. Notably, we resolve Stanley's questions on the shape of partitions attaining the largest Kronecker and Littlewood--Richardson coefficients. We apply the results to asymptotics of the number of standard Young tableaux of skew shapes.

External powers of tensor products as representations of general linear groups (with Piotr Sniady) Alg. Comb. 1(2018), no. 1, pp 81--94.

We consider the decomposition into irreducible components of the external power Lambda^p(C^m x C^n) regarded as a GL_mxGL_n-module. The Young diagrams from each pair (lambda,mu) which contributes to this decomposition turn out to be conjugate one to the other, i.e.e. mu=lambda'. We show that the Young diagram lambda which corresponds to a randomly selected irreducible component (lambda,lambda') has the same distribution as the Young diagram which consists of the boxes with entries =p of a random Young tableau of rectangular shape with m rows and n columns. This observation allows treatment of the asymptotic version of this decomposition in the limit as m,n,p tend to infinity.

Asymptotics of the number of standard Young tableaux of skew shape (with A. Morales, I. Pak) Europ. J. Comb.70(2018), pp. 26--49 

We give new bounds and asymptotic estimates on the number of standard Young tableaux of skew shape in a variety of special cases. Our approach is based on Naruse's hook-length formula. We also compare our bounds with the existing bounds on the numbers of linear extensions of the corresponding posets.

Lozenge tilings with free boundaries, Lett. Math. Phys. (2015), 105(11), pp. 1551--1586. Extended abstract -- FPSAC 2015 Proceedings in Discrete Math and Theoretical Computer Science. 

We study lozenge tilings of a domain with partially free boundary. In particular, we consider a trapezoidal domain (half hexagon), s.t. the horizontal lozenges on the long side can intersect it anywhere to protrude halfway across. We show that the positions of the horizontal lozenges near the opposite flat vertical boundary have the same joint distribution as the eigenvalues from a Gaussian Unitary Ensemble (the GUE-corners/minors process). We also prove the existence of a limit shape of the height function, which is also a vertically symmetric plane partition. Both behaviors are shown to coincide with those of the corresponding doubled fixed-boundary hexagonal domain. We also consider domains where the different sides converge to ∞ at different rates and recover again the GUE-corners process near the boundary.

Bounds on Kronecker and q-binomial coefficients (with I. Pak), J. Combin. Theory Ser. A 147 (2017), pp. 1--17.

We present a lower bound on the Kronecker coefficients of the symmetric group via the characters of Sn, which we apply to obtain various explicit estimates. Notably, we extend Sylvester's unimodality of q-binomial coefficients (n choose k)_q as polynomials in q to derive sharp bounds on the differences of their consecutive coefficients. 

This paper was preceeded by the following: 

Bounds on the Kronecker coefficients( with I. Pak). It contains a proof of k-stability of the Kronecker coefficients generalizing the (usual) stability, and giving a new upper bound on the Kronecker coefficients.

Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory (with V. Gorin). Ann. Probab. (2015), 43(6), pp. 3052 -- 3132. Extended abstract in DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013). 

We develop a new method for studying the asymptotics of symmetric polynomials of representation--theoretic origin as the number of variables tends to infinity. Several applications of our method are presented: We prove a number of theorems concerning characters of infinite-dimensional unitary group and their $q$-deformations. We study the behavior of uniformly random lozenge tilings of large polygonal domains and find the GUE-eigenvalues distribution in the limit. We also investigate similar behavior for Alternating Sign Matrices (equivalently, six--vertex model with domain wall boundary conditions). Finally, we compute the asymptotic expansion of certain observables in $O(n=1)$ dense loop model.

Probability and Statistical Mechanics

 Log-concavity in planar random walks (with S. H. Chan, I. Pak), Combinatorica, to appear. 

We prove log-concavity of exit probabilities of lattice random walks in certain planar regions.

Sorting probability of Catalan posets (with S.H. Chan, I. Pak),  Adv. Appl. Math (2021).

We show that the sorting probability of the Catalan poset  satisfies δ=O(n^{−5/4}). 

Sorting probability for large Young diagrams (with S.H. Chan, I. Pak), Discrete Analysis (2021).

For a finite poset P=(X,≺), let L denote the set of linear extensions of P. The sorting probability δ(P) is defined as 

δ(P):=min_{x,y∈X} |P[L(x)≤L(y)] − P[L(y)≤L(x)]|,

where L∈L is a uniform linear extension of P. We give asymptotic upper bounds on sorting probabilities for posets associated with large Young diagrams and large skew Young diagrams, with bounded number of rows. 

Counting partitions inside a rectangle. (with S. Melczer, R. Pemantle), SIAM J. Disc. Math. (2020). Extended Abstract at FPSAC 2019, Disc. Math. Theoretical Comp.  Sci. Proceedings.

We consider the number of partitions of n whose Young diagrams fit inside an m x l rectangle; equivalently, we study the coefficients of the q-binomial coefficient (m+l choose m)_q. We obtain sharp asymptotics throughout the regime l=Theta(m) and n=Theta(m^2). Previously, sharp asymptotics were derived by Takacs only in the regime where |n-lm/2|=O(\sqrt{lm(l+m)}) using a local central limit theorem. Our approach is to solve a related large deviation problem: we describe the tilted measure that produces configurations whose bounding rectangle has the given aspect ratio and is filled to the given proportion. Our results are sufficiently sharp to yield the first asymptotic estimates on the consecutive differences of these numbers when n is increased by one and m,l remain the same, hence significantly refining Sylvester's unimodality theorem.

Hook formulas for skew shapes III. Multivariate and product formulas (with Alejandro Morales, Igor Pak),  Alg. Comb.  2 (2019), no. 5, pp. 815--861. Extended Abstract at FPSAC 2018, DMTCS Proceedings.

We give new product formulas for the number of standard Young tableaux of certain skew shapes and for the principal evaluation of the certain Schubert polynomials. These are proved by utilizing symmetries for evaluations of factorial Schur functions, extensively studied in the first two papers in the series "Hook formulas for skew shapes" [arxiv:1512.08348, arxiv:1610.04744]. We also apply our technology to obtain determinantal and product formulas for the partition function of certain weighted lozenge tilings, and give various probabilistic and asymptotic applications.

Lozenge tilings with free boundaries, Lett. Math. Phys. (2015), 105(11), pp. 1551--1586. Extended abstract -- FPSAC 2015 Proceedings in Discrete Math and Theoretical Computer Science. 

We study lozenge tilings of a domain with partially free boundary. In particular, we consider a trapezoidal domain (half hexagon), s.t. the horizontal lozenges on the long side can intersect it anywhere to protrude halfway across. We show that the positions of the horizontal lozenges near the opposite flat vertical boundary have the same joint distribution as the eigenvalues from a Gaussian Unitary Ensemble (the GUE-corners/minors process). We also prove the existence of a limit shape of the height function, which is also a vertically symmetric plane partition. Both behaviors are shown to coincide with those of the corresponding doubled fixed-boundary hexagonal domain. We also consider domains where the different sides converge to ∞ at different rates and recover again the GUE-corners process near the boundary.

Pfaffian formulas for spanning tree probabilities(with D.B.Wilson), Combin. Probab. Comput. 26 (2017), no. 1, 118--137.

We show that certain topologically defined uniform spanning tree probabilities for graphs embedded in an annulus can be computed as linear combinations of Pfaffians of matrices involving the line-bundle Green's function, where the coefficients count cover-inclusive Dyck tilings of skew Young diagrams. 

Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory (with V. Gorin). Ann. Probab. (2015), 43(6), pp. 3052 -- 3132. Extended abstract in DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013). 

We develop a new method for studying the asymptotics of symmetric polynomials of representation--theoretic origin as the number of variables tends to infinity. Several applications of our method are presented: We prove a number of theorems concerning characters of infinite-dimensional unitary group and their $q$-deformations. We study the behavior of uniformly random lozenge tilings of large polygonal domains and find the GUE-eigenvalues distribution in the limit. We also investigate similar behavior for Alternating Sign Matrices (equivalently, six--vertex model with domain wall boundary conditions). Finally, we compute the asymptotic expansion of certain observables in $O(n=1)$ dense loop model.

Dyck tilings, linear extensions, descents, and inversions ( with J.S. Kim, K.Meszaros, D.B. Wilson). J.  Comb. Theory, Series A,  122, Feb 2014, pp. 9-27. Extended abstract in Discrete Math and Theoretical Computer Science, FPSAC 2012 Proceedings. 

Dyck tilings were introduced by Kenyon and Wilson in their study of double-dimer pairings. They are certain kinds of tilings of skew Young diagrams with ribbon tiles shaped like Dyck paths. We give two bijections between "cover-inclusive" Dyck tilings and linear extensions of tree posets. The first bijection maps the statistic (area + tiles)/2 to inversions of the linear extension, and the second bijection maps the "discrepancy" between the upper and lower boundary of the tiling to descents of the linear extension.

Tableaux and plane partitions of truncated shapes; Adv. in Applied Math., 49, Issues 35,(2012),p.196-217 Extended abstract at FPSAC 2011, (best student paper award) Discrete Mathematics and Theoretical Computer Science proceedings AO, 2011, p.753-764

We consider a new kind of straight and shifted plane partitions/Young tableaux --- ones whose diagrams are no longer of partition shape, but rather Young diagrams with boxes erased from their upper right ends. We find formulas for the number of standard tableaux in certain cases, namely a shifted staircase without the box in its upper right corner, i.e. truncated by a box, a rectangle truncated by a staircase and a rectangle truncated by a square minus a box. The proofs involve finding the generating function of the corresponding plane partitions using interpretations and formulas for sums of restricted Schur functions and their specializations. The number of standard tableaux is then found as a certain limit of this function.

Combinatorics and enumeration of Standard Young Tableaux 

Minimal skew semistandard tableaux and the Hillman--Grassl correspondence (with A. H. Morales, G.Y. Park), submitted 2023.

Standard tableaux of skew shape are fundamental objects in enumerative and algebraic combinatorics and no product formula for the number is known. In 2014, Naruse gave a formula (NHLF) as a positive sum over excited diagrams of products of hook-lengths. Subsequently, Morales, Pak, and Panova gave a q-analogue of this formula in terms of skew semistandard tableaux (SSYT). They also showed, partly algebraically, that the Hillman--Grassl map, restricted to skew semistandard tableaux, is behind their q-analogue. We study the problem of circumventing the algebraic part and proving the bijection completely combinatorially, which we do for border strips. For a skew shape, we define minimal semistandard Young tableaux, that are in correspondence with excited diagrams via a new description of the Hillman--Grassl bijection and have an analogue of excited moves. Lastly, we relate the minimal skew SSYT with the terms of the Okounkov-Olshanski formula (OOF) for counting standard tableaux of skew shape. Our construction immediately implies that the summands in the NHLF are less than the summands in the OOF and we characterize the shapes where both formulas have the same number of summands.

Hook formulas for skew shapes IV. Increasing tableaux and factorial Grothendieck polynomials (with. A.H. Morales, I. Pak), J. Mathematical Sciences 261 (2022). 

We present a new family of hook-length formulas for the number of standard increasing tableaux which arise in the study of factorial Grothendieck polynomials. In the case of straight shapes our formulas generalize the classical hook-length formula and Stanley's formula. For skew shapes, our formulas generalize the Naruse hook-length formula and its q-analogues, which were studied in previous papers of the series.

Hook formulas for skew shapes III. Multivariate and product formulas (with Alejandro Morales, Igor Pak),  Alg. Comb.  2 (2019), no. 5, pp. 815--861. Extended Abstract at FPSAC 2018, DMTCS Proceedings.

We give new product formulas for the number of standard Young tableaux of certain skew shapes and for the principal evaluation of the certain Schubert polynomials. These are proved by utilizing symmetries for evaluations of factorial Schur functions, extensively studied in the first two papers in the series "Hook formulas for skew shapes" [arxiv:1512.08348, arxiv:1610.04744]. We also apply our technology to obtain determinantal and product formulas for the partition function of certain weighted lozenge tilings, and give various probabilistic and asymptotic applications.

Asymptotics of the number of standard Young tableaux of skew shape (with A. Morales, I. Pak) Europ. J. Comb.70(2018), pp. 26--49 

We give new bounds and asymptotic estimates on the number of standard Young tableaux of skew shape in a variety of special cases. Our approach is based on Naruse's hook-length formula. We also compare our bounds with the existing bounds on the numbers of linear extensions of the corresponding posets.

Hook formulas for skew shapes II. Combinatorial proofs and enumerative applications (with Alejandro Morales, Igor Pak), SIAM J. Discrete Math. 31 (2017), no. 3, pp.1953--1989 

The Naruse hook-length formula is a recent general formula for the number of standard Young tableaux of skew shapes, given as a positive sum over excited diagrams of products of hook-lengths. In 2015 we gave two different q-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. In this paper we give an elementary proof of Naruse's formula based on the case of border strips. For special border strips, we obtain curious new formulas for the Euler and q-Euler numbers in terms of certain Dyck path summations.

Hook formulas for skew shapes I. q-analogues and bijections (with Alejandro Morales, Igor Pak), J. Combin. Theory Ser. A , 154(2018), pp. 350--405.. Extended abstract at FPSAC 2016. 

The celebrated hook-length formula gives a product formula for the number of standard Young tableaux of a straight shape. In 2014, Naruse announced a more general formula for the number of standard Young tableaux of skew shapes as a positive sum over excited diagrams of products of hook-lengths. We give an algebraic and a combinatorial proof of Naruse's formula, by using factorial Schur functions and a generalization of the Hillman--Grassl correspondence, respectively. The main new results are two different q-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. We establish explicit bijections between these objects and families of integer arrays with certain nonzero entries, which also proves the second formula.

Tableaux and plane partitions of truncated shapes; Adv. in Applied Math., 49, Issues 35,(2012),p.196-217 Extended abstract at FPSAC 2011, (best student paper award) Discrete Mathematics and Theoretical Computer Science proceedings AO, 2011, p.753-764

We consider a new kind of straight and shifted plane partitions/Young tableaux --- ones whose diagrams are no longer of partition shape, but rather Young diagrams with boxes erased from their upper right ends. We find formulas for the number of standard tableaux in certain cases, namely a shifted staircase without the box in its upper right corner, i.e. truncated by a box, a rectangle truncated by a staircase and a rectangle truncated by a square minus a box. The proofs involve finding the generating function of the corresponding plane partitions using interpretations and formulas for sums of restricted Schur functions and their specializations. The number of standard tableaux is then found as a certain limit of this function.

Bijective enumeration of permutations starting with a longest increasing subsequence,  22nd International Conference on Formal Power Series and Algebraic Combinatorics Proceedings, Discrete Math. Theor. Comp. Sci. Proc. (2010), pp. 973--982.

We prove a formula for the number of permutations in $S_n$ such that their first $n-k$ entries are increasing and their longest increasing subsequence has length $n-k$. This formula first appeared as a consequence of character polynomial calculations in recent work of Adriano Garsia and Alain Goupil. We give two `elementary' bijective proofs of this result and of its $q$-analogue, one proof using the RSK correspondence and one only permutations.

Polynomiality of some hook-length statistics, The Ramanujan Journal (2012) 27, Issue 3, pp 349-356. 

We prove an equation conjectured by Okada regarding hook-lengths of partitions, namely that \frac{1}{n!} \sum_{\lambda \vdash n} f_{\lambda}^2 \sum_{u \in \lambda} \prod_{i=1}^{r}(h_u^2 - i^2) = \frac{1}{2(r+1)^2} \binom{2r}{r}\binom{2r+2}{r+1} \prod_{j=0}^{r} (n-j), where $f_{\lambda}$ is the number of standard Young tableaux of shape $\lambda$ and $h_u$ is the hook length of the square $u$ of $\lambda$. We also obtain other similar formulas.

Special polynomials in Algebraic Combinatorics: chromatic symmetric functions, Schubert polynomials etc

Hook formulas for skew shapes IV. Increasing tableaux and factorial Grothendieck polynomials (with. A.H. Morales, I. Pak), J. Mathematical Sciences 261 (2022). 

We present a new family of hook-length formulas for the number of standard increasing tableaux which arise in the study of factorial Grothendieck polynomials. In the case of straight shapes our formulas generalize the classical hook-length formula and Stanley's formula. For skew shapes, our formulas generalize the Naruse hook-length formula and its q-analogues, which were studied in previous papers of the series.

Chromatic symmetric functions of Dyck paths and q-rook theory  (with L. Colmernarejo, A.H. Morales), European J. Combinatorics, to appear. Extended abstract at FPSAC 2021.

The chromatic symmetric function (CSF) of Dyck paths of Stanley and its Shareshian-Wachs q-analogue have important connections to Hessenberg varieties, diagonal       harmonics and LLT polynomials. In the, so called, abelian case they are also curiously related to placements of non-attacking rooks by results of Stanley-Stembridge          (1993) and Guay-Paquet (2013). For the  q-analogue, these results have been generalized by Abreu-Nigro (2020) and Guay-Paquet (private communication), using q-hit numbers. Among our main results is a new proof of Guay-Paquet's elegant identity expressing the q-CSFs in a CSF basis with q-hit coefficients. We further show its equivalence to the Abreu-Nigro identity expanding the q-CSF in the elementary symmetric functions. In the course of our work we establish that the q-hit numbers in these expansions differ from the originally assumed Garsia-Remmel q-hit numbers by certain powers of  q. We prove new identities for these q-hit numbers, and establish connections between the three different variants. 

Asymptotics of principal evaluations of Schubert polynomials for layered permutations (with A. Morales, I. Pak), Proc. Amer. Math. Soc, doi.org/10.1090/proc/14369 (2018).

Denote by u(n) the largest principal specialization of the Schubert polynomial: u(n):=max_{w in S_n} Sch_w(1,..,1) Stanley conjectured in [arXiv:1704.00851] that there is a limit as n goes to infinity of n^{-2} log u(n), and asked for a limiting description of permutations achieving the maximum u(n). Merzon and Smirnov conjectured in [arXiv:1410.6857] that this maximum is achieved on layered permutations. We resolve both Stanley's problems restricted to layered permutations.

LLT polynomials, chromatic quasisymmetric functions and graphs with cycles (with Per Alexandersson), Disc. Math. 341(12) (2018), pp. 3453--3482. 

We use a Dyck path model for unit-interval graphs to study the chromatic quasisymmetric functions introduced by Shareshian and Wachs, as well as vertical strip --- in particular, unicellular LLT polynomials. We show that there are parallel phenomena regarding e-positivity of these two families of polynomials. In particular, we give several examples where the LLT polynomials behave like a "mirror image" of the chromatic quasisymmetric counterpart. The Dyck path model is also extended to circular arc digraphs to obtain larger families of polynomials. This circular extensions of LLT polynomials has not been studied before. A lot of the combinatorics regarding unit interval graphs carries over to this more general setting, and we prove several statements regarding the e-coefficients of chromatic quasisymmetric functions and LLT polynomials. In particular, we believe that certain e-positivity conjectures hold in all these families above. Furthermore, we study vertical-strip LLT polynomials, for which there is no natural chromatic quasisymmetric counterpart. These polynomials are essentially modified Hall--Littlewood polynomials, and are therefore of special interest. In this more general framework, we are able to give a natural combinatorial interpretation for the e-coefficients for the line graph and the cycle graph, in both the chromatic and the LLT setting.

Hook formulas for skew shapes I. q-analogues and bijections (with Alejandro Morales, Igor Pak), J. Combin. Theory Ser. A , 154(2018), pp. 350--405.. Extended abstract at FPSAC 2016. 

The celebrated hook-length formula gives a product formula for the number of standard Young tableaux of a straight shape. In 2014, Naruse announced a more general formula for the number of standard Young tableaux of skew shapes as a positive sum over excited diagrams of products of hook-lengths. We give an algebraic and a combinatorial proof of Naruse's formula, by using factorial Schur functions and a generalization of the Hillman--Grassl correspondence, respectively. The main new results are two different q-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. We establish explicit bijections between these objects and families of integer arrays with certain nonzero entries, which also proves the second formula.

Schur times Schubert via the Fomin-Kirillov algebra (with K. Meszaros, A. Postnikov). Electronic J. Comb.  21, Issue 1 (2014).

We study multiplication of any Schubert polynomial \S_w by a Schur polynomial s_\lambda (the Schubert polynomial of a Grassmannian permutation) and the expansion of this product in the ring of Schubert polynomials. We derive explicit nonnegative combinatorial expressions for the expansion coefficients for certain special partitions , including hooks and the 22 box. We also prove combinatorially the existence of such nonnegative expansion when the Young diagram of is a hook plus a box at the (2,2) corner. We achieve this by evaluating Schubert polynomials at the Dunkl elements of the Fomin-Kirillov algebra and proving special cases of the nonnegativity conjecture of Fomin and Kirillov. This approach works in the more general setup of the (small) quantum cohomology ring of the complex flag manifold and the corresponding (3-point) Gromov-Witten invariants. We provide an algebro-combinatorial proof of the nonnegativity of the Gromov-Witten invariants in these cases, and present combinatorial expressions for these coefficients.

Bijections, injections and combinatorial interpretations

Positivity of the Symmetric group characters is as hard as the polynomial time hierarchy (with Ch. Ikenmeyer, I. Pak)

We prove that deciding the vanishing of the character of the symmetric group is C_=P-complete. We use this hardness result to prove that the the square of the character is not contained in #P, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is PP-complete under many-one reductions, and hence PH-hard under Turing-reductions. 

Effective poset inequalities (with S.H. Chan, I. Pak).

We explore inequalities on linear extensions of posets and make them effective in different ways. First, we study the Björner–Wachs inequality and generalize it to inequalities on order polynomials and their q-analogues via direct injections and FKG inequalities. Second, we give an injective proof of the Sidorenko inequality with computational complexity significance, namely that the difference is in #P. Third, we generalize actions of Coxeter groups on restricted linear extensions, leading to vanishing and uniqueness conditions for the generalized Stanley inequality.  We also establish several inequalities for order polynomials of posets.  

Extensions of the Kahn--Saks inequality for posets of width two (with S. H Chan, I. Pak), submitted.

The Kahn--Saks inequality is a classical result on the number of linear extensions of finite posets. We give a new proof of this inequality for posets of width two using explicit injections of lattice paths. As a consequence we obtain a q-analogue, a multivariate generalization and an equality condition in this case. We also discuss the equality conditions of the Kahn--Saks inequality for general posets and prove several implications between conditions conjectured to be equivalent.

The cross-product conjecture for width two posets (with S.H. Chan, I. Pak),  Trans. Amer. Math. Soc. (2022).

 The cross--product conjecture (CPC) of Brightwell, Felsner and Trotter (1995) is a two-parameter quadratic inequality for the number of linear extensions of a poset   P=(X,≺) with  given value differences on three distinct elements in X. We give two different proofs of this inequality for posets of width two. The first proof is algebraic and  generalizes CPC to a  four-parameter family. The second proof is combinatorial and extends CPC to a q-analogue. Further applications include relationships between CPC and other poset inequalities.

 A minimaj-preserving crystal on ordered multiset partitions (with Georgia Benkart, Laura Colmenarejo, Pamela E. Harris, Rosa Orellana, Anne Schilling, Martha Yip), Adv. Appl. Math. 98(2018), pp 96--115.

We provide a crystal structure on the set of ordered multiset partitions, which recently arose in the pursuit of the Delta Conjecture. This conjecture was stated by Haglund, Remmel and Wilson as a generalization of the Shuffle Conjecture. Various statistics on ordered multiset partitions arise in the combinatorial analysis of the Delta Conjecture, one of them being the minimaj statistic, which is a variant of the major index statistic on words. Our crystal has the property that the minimaj statistic is constant on connected components of the crystal. In particular, this yields another proof of the Schur positivity of the graded Frobenius series of the generalization R_{n,k} due to Haglund, Rhoades and Shimozono of the coinvariant algebra R_n. The crystal structure also enables us to demonstrate the equidistributivity of the minimaj statistic with the major index statistic on ordered multiset partitions.

Why is π < 2 φ ? (with A. Morales, I. Pak) Amer. Math Monthly, 125 (2018) - Issue 8, paper.

We give a combinatorial proof of the inequality in the title in terms of Fibonacci numbers and Euler numbers. The result is motivated by Sidorenko's theorem on the number of linear extensions of the poset and its complement. We conclude with some open problems. 

External powers of tensor products as representations of general linear groups (with Piotr Sniady) Alg. Comb. 1(2018), no. 1, pp 81--94.

We consider the decomposition into irreducible components of the external power Lambda^p(C^m x C^n) regarded as a GL_mxGL_n-module. The Young diagrams from each pair (lambda,mu) which contributes to this decomposition turn out to be conjugate one to the other, i.e.e. mu=lambda'. We show that the Young diagram lambda which corresponds to a randomly selected irreducible component (lambda,lambda') has the same distribution as the Young diagram which consists of the boxes with entries =p of a random Young tableau of rectangular shape with m rows and n columns. This observation allows treatment of the asymptotic version of this decomposition in the limit as m,n,p tend to infinity.

Hook formulas for skew shapes I. q-analogues and bijections (with Alejandro Morales, Igor Pak), J. Combin. Theory Ser. A , 154(2018), pp. 350--405.. Extended abstract at FPSAC 2016. 

The celebrated hook-length formula gives a product formula for the number of standard Young tableaux of a straight shape. In 2014, Naruse announced a more general formula for the number of standard Young tableaux of skew shapes as a positive sum over excited diagrams of products of hook-lengths. We give an algebraic and a combinatorial proof of Naruse's formula, by using factorial Schur functions and a generalization of the Hillman--Grassl correspondence, respectively. The main new results are two different q-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. We establish explicit bijections between these objects and families of integer arrays with certain nonzero entries, which also proves the second formula.

Dyck tilings, linear extensions, descents, and inversions ( with J.S. Kim, K.Meszaros, D.B. Wilson). J.  Comb. Theory, Series A,  122, Feb 2014, pp. 9-27. Extended abstract in Discrete Math and Theoretical Computer Science, FPSAC 2012 Proceedings. 

Dyck tilings were introduced by Kenyon and Wilson in their study of double-dimer pairings. They are certain kinds of tilings of skew Young diagrams with ribbon tiles shaped like Dyck paths. We give two bijections between "cover-inclusive" Dyck tilings and linear extensions of tree posets. The first bijection maps the statistic (area + tiles)/2 to inversions of the linear extension, and the second bijection maps the "discrepancy" between the upper and lower boundary of the tiling to descents of the linear extension.

Separable permutations and Greene's theorem; ( with A.Crites, G.Warrington). Ars Combin. 128(2016), pp.103--116.

We study the shape of separable (3142 and 2413-avoiding) permutations under RSK in light of Greene's theorem. We show that if the shape of a separable permutation $\sigma$ is $\lambda=(\lambda_1,...,\lambda_k)$, then $\sigma$ has $k$ disjoint increasing subsequences of lengths $\lambda_1,...,\lambda_k$. As a corollary, we prove that if $\sigma$ is a separable subsequence of a word $w$, then the shape of $\sigma$ is contained in the shape of $w$ as Young diagrams. These facts are also used to exhibit lower bounds on the length of words containing certain separable permutations as patterns.

Matrices with restricted entries and q-analogues of permutations (with J.Lewis, R.Liu, A.Morales, S.Sam, Y.Zhang), J. of Combinatorics(2011), no. 3, 355-396 Extended abstract at FPSAC 2011, DMTCS, proceedings, 2011, p.645-656 

We study the functions that count matrices of given rank over a finite field with specified positions equal to zero. We show that these matrices are $q$-analogues of permutations with certain restricted values. We obtain a simple closed formula for the number of invertible matrices with zero diagonal, a $q$-analogue of derangements, and a curious relationship between invertible skew-symmetric matrices and invertible symmetric matrices with zero diagonal. In addition, we provide recursions to enumerate matrices and symmetric matrices with zero diagonal by rank, and we frame some of our results in the context of Lie theory. Finally, we provide a brief exposition of polynomiality results for enumeration questions related to those mentioned, and give several open questions.

Factorization of banded permutations , Proceedings of the AMS 140 (11), 3805-3812.

We prove a conjecture of Gilbert Strang stating that a banded permutation of bandwidth $w$ can be represented as a product of at most $2w-1$ permutations of bandwidth 1.

Bijective enumeration of permutations starting with a longest increasing subsequence,  22nd International Conference on Formal Power Series and Algebraic Combinatorics Proceedings, Discrete Math. Theor. Comp. Sci. Proc. (2010), pp. 973--982.

We prove a formula for the number of permutations in $S_n$ such that their first $n-k$ entries are increasing and their longest increasing subsequence has length $n-k$. This formula first appeared as a consequence of character polynomial calculations in recent work of Adriano Garsia and Alain Goupil. We give two `elementary' bijective proofs of this result and of its $q$-analogue, one proof using the RSK correspondence and one only permutations.

PhD thesis

Combinatorial applications of symmetric function theory to certain classes of permutations and truncated tableaux; PhD dissertation, Harvard, April 2011. 

The dissertation includes 3 of the published papers (with some modifications) Tableaux and plane partitions of truncated shapes, Separable permutations and Greene's theorem and Bijective enumeration of permutations starting with a longest increasing subsequence. The Background chapter is a review of the theory of symmetric functions and is all one needs to know to understand these papers.