My research interests are in the area of algebraic and enumerative combinatorics and
its applications to statistical mechanics,
representation theory, algebra and biology.

Papers are available below, as well as a list of Selected Talks with some slides and other writings.

Geometric Complexity Theory and Matrix Powering (with Fulvio Gesmundo, Christian Ikenmeyer)

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.

Asymptotics of the number of standard Young tableaux of skew shape, with A. Morales, I. Pak.

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.

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.

No occurrence obstructions in geometric complexity theory with Peter Burgisser, Christian Ikenmeyer (2016), submitted. 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.

Hook formulas for skew shapes I. q-analogues and bijections. with Alejandro Morales, Igor Pak. submitted. 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.

Rectangular Kronecker coefficients and plethysms in geometric complexity theory,
with Christian Ikenmeyer,submitted, 2015. 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.

Lozenge tilings with free boundaries,
*Letters in Mathematical Physics*, to appear (2015).
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 Comb Theory Series A*.

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.

Pfaffian formulas for spanning tree probabilities, with D.B.Wilson, *Combinatorics Probability and Computing*.

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.

Strict unimodality
of q-binomial coefficients; with Igor Pak. * C. R. Acad. Sci.
Paris*, Ser. I (2013), 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. *Journal of Algebraic Combinatorics*(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. *Computational Complexity*, to appear.

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.

The thermodynamic patterns of eukaryotic genes suggest a mechanism for
intronexon recognition
; (M. Nedelcheva-Veleva, M. Sarov, I. Yanakiev,
E. Mihailovska, M. Ivanov, G. Panova,
Stoyno S. Stoynov(PI) ), *Nature
Communications*,doi:10.1038/ncomms3101.

Kronecker products, characters, partitions, and the tensor square
conjectures; with Igor Pak and Ernesto Vallejo. *Advances in Mathematics*.

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.

Asymptotics of symmetric
polynomials with applications to statistical
mechanics and representation theory; with V. Gorin. *Annals of Probability*, to appear.

updated version as of Apr 2014.
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.

Schur times Schubert via the
Fomin-Kirillov algebra; with K. Meszaros, A. Postnikov. *Electronic
J. Combinatorics,* Vol
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.

Dyck tilings, linear
extensions, descents, and inversions; joint with J.S. Kim,
K.Meszaros, D.B. Wilson. *Journal of Combinatorial Theory, Series A*,
Vol. 122, Feb 2014, p. 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.

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

My dissertation includes 3 of the papers below (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.

Tableaux and plane partitions
of truncated shapes; *Advances in Applied Mathematics*, 49,
Issues 35,(2012),p.196-217

Extended
abstract at FPSAC 2011, * 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.

Matrices with restricted
entries and q-analogues of
permutations; joint 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.

Separable
permutations and Greene's theorem;
joint with A.Crites, G.Warrington. *Ars Combinatoria*, to appear.

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.

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,
*Discrete Mathematics and Theoretical Computer Science Proceedings(2010)*

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*, April 2012, Volume 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.

Why is π < 2 φ ? (with A. Morales, I. Pak)

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.

Lie Algebras, Representation theory and
GL_n

Minor thesis towards Ph.D. requirements,
advisor Joseph Harris.

AIM workshop: Combinatorics and Complexity of Kronecker coefficients, co-organizer, Palo Alto, CA. November 3-7, 2014.

University of Pennsylvania Mathematics Colloquium, December 4 2013.

Georgia Tech, Atlanta, GA, November 19 2013.

UC Berkeley Combinatorics Seminar, Berkeley, CA, October 14 2013.

University of Washington Combinatorics Seminar, Seattle, September 2013.

Mathematical Congress of the Americas, Special Session on Algebraic and Enumerative Combinatorics, Guanajauto, Mexico, August 2013.

Formal Power Series and Algebraic Combinatorics, Paris, France, June 2013:

The slides on Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory.

Random tilings workshop, SUNY Stony Brook, February 2013.

UCLA Probability Seminar, January 2013.

UCLA Combinatorics Seminar, December 2012.

FPSAC, Nagoya, Japan, August 2012. poster presentation on Dyck tilings, linear extensions, inversions and descents.

Workshop on convex polytopes, RIMS Kyoto, Japan, July 2012.

MSRI Evans Lecture Series, UC Berkeley, February 2012.

Counting tricks with symmetric functions,

UCLA Combinatorics Seminar, December 2011.

Formal Power Series and Algebraic Combinatorics, Reykjavik, June 2011. (best student paper award)

Microsoft Research Theory Group, Redmond WA, May 2011.

AMS Eastern Regional Meeting, College of the Holy Cross, April 2011.

MIT Combinatorics Seminar, November 2010.

Permutation Patterns 2010, slides on Separable permutations, Robinson-Schensted and shortest containing supersequence.

Formal Power Series and Algebraic Combinatorics, San Francisco 2010.

Joint Math Meeting 2010, Special Session on Permutations, January 2010.