Menu:

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.


Papers

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.



Popular math, expository papers


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.




Selected Talks



MIT Combinatorics Seminar, MIT, Cambridge, MA, Nov 2016.
Foundations of Computer Science (FOCS) conference, New Brunswick, NJ. Oct 2016.
AMS Fall Eastern Sectional Meeting , Bowdoin College, Brunswick, ME. Sept 2016.
Kronecker Coefficients Conference 2016 , City University London, United Kingdom. Sept 2016.
Formal Power Series and Algebraic Combinatorics conference, Vancouver, Canada. Jul 2016.
University of Pennsylvania CAGE seminar, Philadelphia, PA. Jun 2016.
Six-vertex model, dimers, shapes and all that workshop, Simons Center for Geometry and Physics, Stony Brook, NY. Mar 2016.
UCLA Combinatorics Seminar, Los Angeles, CA. Mar 2016.
Triangle Lectures in Combinatorics, Greensboro, NC, (plenary speaker). Feb 2016.
Texas A&M Universi:ty Probability / Algebra and Combinatorics Seminar , College Station, TX, Nov. 24 2015.
AMS Fall Eastern Sectional Meeting, Special Session on Probability, Combinatorics and Statistical Mechanics, Rutgers University, New Brunswick, NJ, Nov. 14, 2015.
Haverford Mathematics Colloquium, Haverford, PA, Nov. 2, 2015.
University of Rochester Probability Seminar, Rochester, NY, OctoOct. 9, 2015
Temple University Mathematics Colloquium, Philadelphia, PA, October 5, 2015.
Formal Power Series and Algebraic Combinatorics, Daejeon, Korea. July 7, 2015.
AMS-EMS-SPM joint meeting, Special Session on Algebraic Combinatorics and Representation Theory, Porto, Portugal. June 13, 2015.
Lattice Models: Exact Results and Combinatorics workshop, Galileo Galilei Institute for Theoretical Physics, Florence, Italy. May 20, 2015.
Limit Shapes workshop, ICERM, Providence, RI. April 17, 2015.
University of Virginia Algebra Seminar, UVA, Charlottesville, VA. March 20, 2015.
Columbia/Courant Probability Seminar: Random Tilings, New York, NY. February 27, 2015.
Princeton University Combinatorics Seminar, Princeton, NJ. February 25, 2015.
Joint AMS/MAA meeting, Special Session on Probability and Applications, San Antonio, TX. January 10, 2015.
Symbolic and Computational Methods for Tensors and Representation Theory, Simons Institute, Berkeley, CA. November 19, 2014. video and slides.
IMA workshop on Geometric and Enumerative Combinatorics, Minneapolis, MN. November 12, 2014. videos
AIM workshop: Combinatorics and Complexity of Kronecker coefficients, co-organizer, Palo Alto, CA. November 3-7, 2014.
AMS Meeting, Special Session on Combinatorial Representation Theory, Halifax, Canada. October 18, 2014.
Geometric Complexity Theory workshop, Simons Institute, Berkeley, CA. September 19, 2014. slides and video.
Formal Power Series and Algebraic Combinatorics, Chicago, IL, June 30, 2014.
Stanley 70th birthday conference, MIT, Cambridge, MA, June 24, 2014.
SIAM Discrete Mathematics, Combinatorics and Statistical Mechanics SS, Minneapolis, MN, June 16, 2014.
UC Davis Mathematics Colloquium, Davis, CA, January 24, 2014.
Caltech Mathematics Colloquium, Pasadena, CA, January 22, 2014.
IST Austria, Klosterneuburg, Austria, Colloquium, January 8 2014.
ETH Zurich Fakultaet fuer Mathematik, Special Lecture, Zurich, Switzerland, January 6 2014.
Washington University in St. Louis, Mathematics Colloquium, December 9 2013.
University of Pennsylvania Mathematics Colloquium, December 4 2013.
Georgia Tech, Atlanta, GA, November 19 2013.
Vanderbilt Mathematics Colloquium, Nashville, TN, November 11 2013.
UC Berkeley Combinatorics Seminar, Berkeley, CA, October 14 2013.
UCSD Combinatorics Seminar, San Diego, CA, October 1 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 Postdoc Seminar, Berkeley, CA, March 2012.
UC Berkeley Combinatorics Seminar, Berkeley, CA, March 2012.
MSRI Evans Lecture Series, UC Berkeley, February 2012.
Counting tricks with symmetric functions,
UCLA Combinatorics Seminar, December 2011. Dyck tilings, linear extensions and descents
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.
University of Pennsilvania Combinatorics Seminar, January 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.