List of papers classified by topics. 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 and on my Google Scholar profile.
List of papers classified by topics. 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 and on my Google Scholar profile.
Polynomial time classical versus quantum algorithms for representation theoretic multiplicities, 2025
Littlewood-Richardson, Kronecker and plethysm coefficients are fundamental multiplicities of interest in Representation Theory and Algebraic Combinatorics. Determining a combinatorial interpretation for the Kronecker and plethysm coefficients is a major open problem, and prompts the consideration of their computational complexity. Recently it was shown that they behave relatively well with respect to quantum computation, and for some large families there are polynomial time quantum algorithms [Larocca,Havlicek, arXiv:2407.17649] (also [BCGHZ,arXiv:2302.11454]). In this paper we show that for many of those cases the Kronecker and plethysm coefficients can also be computed in polynomial time via classical algorithms, thereby refuting some of the conjectures in [LH24]. This vastly limits the cases in which the desired super-polynomial quantum speedup could be achieved.
Computational Complexity in Algebraic Combinatorics, Current Developments in Mathematics 2023 conference, Vol 2024(1), Int. Press Boston.
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), Forum of Mathematics, Pi (2024).
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.
Grothendieck Shenanigans: Permutons from pipe dreams via integrable probability (with A. H. Morales, L. Petrov, D. Yeliussizov), submitted (2024). IPAM hhighlight featuring this paper.
We study random permutations arising from reduced pipe dreams. Our main model is motivated by Grothendieck polynomials with parameter β=1 arising in K-theory of the flag variety. The probability weight of a permutation is proportional to the principal specialization (setting all variables to 1) of the corresponding Grothendieck polynomial. By mapping this random permutation to a version of TASEP (Totally Asymmetric Simple Exclusion Process), we describe the limiting permuton and fluctuations around it as the order n of the permutation grows to infinity. The fluctuations are of order n13 and have the Tracy-Widom GUE distribution, which places this algebraic (K-theoretic) model into the Kardar-Parisi-Zhang universality class. We also investigate non-reduced pipe dreams and make progress on a recent open problem on the asymptotic number of inversions of the resulting permutation. Inspired by Stanley's question for the maximal value of principal specializations of Schubert polynomials, we resolve the analogous question for β=1 Grothendieck polynomials, and provide bounds for general β.
White paper: "Geometry , Statistical Mechanics and Integrabitliy" (with 33 coauthors) for the IPAM Long Program in Spring 2024.
Durfee squares, symmetric partitions and bounds on Kronecker coefficients (with I. Pak), Journal of Algebra (2023).
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.
Hook-length Formulas for Skew Shapes via Contour Integrals and Vertex Models (with L. Petrov), submitted (2024).
The number of standard Young tableaux of a skew shape λ/μ can be computed as a sum over excited diagrams inside λ. Excited diagrams are in bijection with certain lozenge tilings, with flagged semistandard tableaux and also nonintersecting lattice paths inside λ. We give two new proofs of a multivariate generalization of this formula, which allow us to extend the setup beyond standard Young tableaux and the underlying Schur symmetric polynomials. The first proof uses multiple contour integrals. The second one interprets excited diagrams as configurations of a six-vertex model at a free fermion point, and derives the formula for the number of standard Young tableaux of a skew shape from the Yang-Baxter equation.
Grothendieck Shenanigans: Permutons from pipe dreams via integrable probability (with A. H. Morales, L. Petrov, D. Yeliussizov), submitted (2024). IPAM hhighlight featuring this paper.
We study random permutations arising from reduced pipe dreams. Our main model is motivated by Grothendieck polynomials with parameter β=1 arising in K-theory of the flag variety. The probability weight of a permutation is proportional to the principal specialization (setting all variables to 1) of the corresponding Grothendieck polynomial. By mapping this random permutation to a version of TASEP (Totally Asymmetric Simple Exclusion Process), we describe the limiting permuton and fluctuations around it as the order n of the permutation grows to infinity. The fluctuations are of order n13 and have the Tracy-Widom GUE distribution, which places this algebraic (K-theoretic) model into the Kardar-Parisi-Zhang universality class. We also investigate non-reduced pipe dreams and make progress on a recent open problem on the asymptotic number of inversions of the resulting permutation. Inspired by Stanley's question for the maximal value of principal specializations of Schubert polynomials, we resolve the analogous question for β=1 Grothendieck polynomials, and provide bounds for general β.
White paper: "Geometry , Statistical Mechanics and Integrabitliy" (with 33 coauthors) for the IPAM Long Program in Spring 2024.
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.
On the cross-product conjecture for the number of linear extensions (with S. H. Chan, I. Pak)
We prove a weak version of the cross--product conjecture:
F(k+1,ℓ)F(k,ℓ+1)≥(1/2+ε)F(k,ℓ)F(k+1,ℓ+1) , where F(k,ℓ) is the number of linear extensions for which the values at fixed elements x,y,z are k and ℓ apart, respectively, and where ε>0 depends on the poset. We also prove the converse inequality and disprove the {generalized cross--product conjecture}. The proofs use geometric inequalities for mixed volumes and combinatorics of words.
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.
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.
Hook-length Formulas for Skew Shapes via Contour Integrals and Vertex Models (with L. Petrov), submitted (2024).
The number of standard Young tableaux of a skew shape λ/μ can be computed as a sum over excited diagrams inside λ. Excited diagrams are in bijection with certain lozenge tilings, with flagged semistandard tableaux and also nonintersecting lattice paths inside λ. We give two new proofs of a multivariate generalization of this formula, which allow us to extend the setup beyond standard Young tableaux and the underlying Schur symmetric polynomials. The first proof uses multiple contour integrals. The second one interprets excited diagrams as configurations of a six-vertex model at a free fermion point, and derives the formula for the number of standard Young tableaux of a skew shape from the Yang-Baxter equation.
Minimal skew semistandard tableaux and the Hillman--Grassl correspondence (with A. H. Morales, G.Y. Park), Adv. Appl. Mathematics (2024).
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.
Hook-length Formulas for Skew Shapes via Contour Integrals and Vertex Models (with L. Petrov), submitted (2024).
The number of standard Young tableaux of a skew shape λ/μ can be computed as a sum over excited diagrams inside λ. Excited diagrams are in bijection with certain lozenge tilings, with flagged semistandard tableaux and also nonintersecting lattice paths inside λ. We give two new proofs of a multivariate generalization of this formula, which allow us to extend the setup beyond standard Young tableaux and the underlying Schur symmetric polynomials. The first proof uses multiple contour integrals. The second one interprets excited diagrams as configurations of a six-vertex model at a free fermion point, and derives the formula for the number of standard Young tableaux of a skew shape from the Yang-Baxter equation.
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.
Preservation of log-concavity on gamma polynomials (with L. Ferroni, Lorenzo Venturello)
Each symmetric polynomial h(x) = h0 + h1*x + ... + hn*x^n, where hi = h{n-i} for all i, can be written as a linear combination in the basis {x^i(1+x)^{n-2i}}. The polynomial \gamma_h(x) = \gamma_0 + \gamma_1 *x+ ... + \gamma_[n/2]* x^[n/2], commonly referred to as the \gamma-polynomial of h(x), records the coefficients of the aforementioned linear combination. Two decades ago, Brändén and Gal independently showed that if \gamma_h(x) has nonpositive real roots only, then so does h(x). More recently, Brändén , Ferroni, and Jochemko proved using Lorentzian polynomials that if \gamma_h(x) is ultra log-concave, then so is h(x), and they raised the question of whether a similar statement can be proved for the usual notion of log-concavity. The purpose of this article is to show that the answer to the question of Br\"anden, Ferroni, and Jochemko is affirmative. One of the crucial ingredients of the proof is an inequality involving binomial numbers that we establish via a path-counting argument.
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.
Diffusion of activated ATM explains γH2AX and MDC1 spread beyond the DNA damage site, Georgi Danovski, Greta Panova, Bradley Keister, Georgi Georgiev, Aleksandar Atemin, Sonya Uzunova, Rumen Stamatov, Petar-Bogomil Kanev, Radoslav Aleksandrov, Krastan B Blagoev, Stoyno Stoynov , iScience (2024).
During DNA repair, ATM-induced H2AX histone phosphorylation and MDC1 recruitment spread megabases beyond the damage site. The mechanism underlying this spread remains unclear. To elucidate this step of the DNA damage response, we measured ATM and MDC1 recruitment kinetics at micro-irradiation-induced complex DNA lesions. While MDC1 spreads beyond the damage-induced focus of ATM accumulation, cohesin loader NIPBL and cohesin subunit RAD21 accumulate later than MDC1. Such delayed recruitment suggests that, in complex DNA lesions, loop extrusion cannot alone explain γH2AX and MDC1 spread. To determine if diffusion of activated ATM could account for the observed behavior, we measured the exchange rate and diffusion constants of ATM and MDC1 within damaged and unperturbed chromatin. Based on these measurements, we introduced a quantitative model that describes the dynamic behavior of ATM and subsequent MDC1 spread at complex DNA lesions. Altogether, we propose activated ATM diffusion as an underlying mechanism of MDC1 spread.
Coordination of Repair of Complex DNA Lesions. R. Aleksandrov, A. Dotchev, I. Poser, D. Krastev, G. Georgiev, G. Panova, Y. Babukov, G. Danovski, T. Dyankova, L. Hubatsch, A. Ivanova, A. Atemin, M. Nedelcheva-Veleva, S. Hasse, M. Sarov, F. Buchholz, A. Hyman, S. Grill, and Stoyno S. Stoynov, Molecular Cell 69 (2018),
Press release and overview at Innovations Report.
A single mutagen can generate multiple different types of DNA lesions. How different repair pathways cooperate in complex DNA lesions, however, remains largely unclear. Here we measured, clustered, and modeled the kinetics of recruitment and dissociation of 70 DNA repair proteins to laser-induced DNA damage sites in HeLa cells. The precise timescale of protein recruitment reveals that error-prone translesion polymerases are considerably delayed compared to error-free polymerases. We show that this is ensured by the delayed recruitment of RAD18 to double-strand break sites. The time benefit of error-free polymerases disappears when PARP inhibition significantly delays PCNA recruitment. Moreover, removal of PCNA from complex DNA damage sites correlates with RPA loading during 5′-DNA end resection. Our systematic study of the dynamics of DNA repair proteins in complex DNA lesions reveals the multifaceted coordination between the repair pathways and provides a kinetics-based resource to study genomic instability and anticancer drug impact.
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.
The essential cis- and trans-acting elements required for RNA splicing have been defined, however, the detailed molecular mechanisms underlying intron–exon recognition are still unclear. Here we demonstrate that the ratio between stability of mRNA/DNA and DNA/DNA duplexes near 3′-spice sites is a characteristic feature that can contribute to intron–exon differentiation. Remarkably, throughout all transcripts, the most unstable mRNA/DNA duplexes, compared with the corresponding DNA/DNA duplexes, are situated upstream of the 3′-splice sites and include the polypyrimidine tracts. This characteristic instability is less pronounced in weak alternative splice sites and disease-associated cryptic 3′-splice sites. Our results suggest that this thermodynamic pattern can prevent the re-annealing of mRNA to the DNA template behind the RNA polymerase to ensure access of the splicing machinery to the polypyrimidine tract and the branch point. In support of this mechanism, we demonstrate that RNA/DNA duplex formation at this region prevents pre-spliceosome A complex assembly.
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.