# Research Papers

I have papers on the following (overlapping) subjects:

## Computational Combinatorics

• (with Swee Hong Chan) Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy, preprint (2023), 35 pages.

Describing the equality conditions of the Alexandrov–Fenchel inequality has been a major open problem for decades. We prove that in the case of convex polytopes, this description is not in the polynomial hierarchy unless the polynomial hierarchy collapses to a finite level. This is the first hardness result for the problem, and is a complexity counterpart of the recent result by Shenfeld and van Handel (2020), which gave a geometric characterization of the equality conditions. The proof involves Stanley's order polytopes and employs poset theoretic technology.

• (with Swee Hong Chan) Computational complexity of counting coincidences, preprint (2023), 24 pages.

Can you decide if there is a coincidence in the numbers counting two different combinatorial objects? For example, can you decide if two regions in R3 have the same number of domino tilings? There are two versions of the problem, with 2×1×1 and 2×2×1 boxes. We prove that in both cases the coincidence problem is not in the polynomial hierarchy unless the polynomial hierarchy collapses to a finite level. While the conclusions are the same, the proofs are notably different and generalize in different directions.

We proceed to explore the coincidence problem for counting independent sets and matchings in graphs, matroid bases, order ideals and linear extensions in posets, permutation patterns, and the Kronecker coefficients. We also make a number of conjectures for counting other combinatorial objects such as plane triangulations, contingency tables, standard Young tableaux, reduced factorizations and the Littlewood–Richardson coefficients.

• What is a combinatorial interpretation?, preprint (2022), 58 pp.
to appear in Proc. Open Problems in Algebraic Combinatorics.

In this survey we discuss the notion of combinatorial interpretation in the context of Algebraic Combinatorics and related areas. We approach the subject from the Computational Complexity perspective. We review many examples, state a workable definition, discuss many open problems, and present recent results on the subject.

See also my talk at Open Problems in Algebraic Combinatorics Conference (Minneapolis, May 18, 2022), talk video and slides.

• (with Christian Ikenmeyer and Greta Panova) Positivity of the symmetric group characters is as hard as the polynomial time hierarchy, preprint (2022), 15 pp.; to appear at Int. Math. Res. Notices (IMRN).
the extended abstract is published in Proc. SODA 2023, 3573–3586;
selected to be a talk at FPSAC 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 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.

See video and slides1, slides2 of Greta's CDM 2023 talk.

• (with Christian Ikenmeyer) What is in #P and what is not?, preprint (2022), 82 pp.
the extended abstract appeared in Proc. 63rd FOCS (2022), 860–871.

For several classical nonnegative integer functions, we investigate if they are members of the counting complexity class #P or not. We prove #P membership in surprising cases, and in other cases we prove non-membership, relying on standard complexity assumptions or on oracle separations.

We initiate the study of the polynomial closure properties of #P on affine varieties, i.e., if all problem instances satisfy algebraic constraints. This is directly linked to classical combinatorial proofs of algebraic identities and inequalities. We completely characterize all polynomial closure properties of GapP and all relativizing polynomial closure properties of #P. We investigate #TFNP and obtain oracle separations that prove the strict inclusion of #P in all standard syntactic subclasses of #TFNP-1.

See this video (47:30-1:12:20) of Christian's talk at FOCS.
See also this talk by Christian (video and slides, Edinburgh, July 4, 2022).

• Combinatorial inequalities, Notices of the AMS, vol. 66 (2019), no. 7, 1109-1112.

Download .pdf file of the column. Here is the journal version (with my picture).

## Integer Points in Polytopes

• (with Philipp Hieronymi and Danny Nguyen) Presburger Arithmetic with algebraic scalar multiplications, Logical Methods in Computer Science, vol. 17 (2021), no. 3, Paper 4, 34 pp.

We study complexity of integer sentences in Sα = (R, <, +, Z, x ↦ αx), which is known to be decidable for quadratic α, and undecidable for non-quadratic irrationals. When α is quadratic and the sentence has r alternating quantifier blocks, we prove both lower and upper bounds as towers of height (r-3) and r, respectively. We also show that for α non-quadratic, already r=4 alternating quantifier blocks suffice for undecidability.

• (with Danny Nguyen) On the number of integer points in translated and expanded polyhedra, Discrete & Computational Geometry, vol. 65 (2021), 405–424.

We prove that the problem of minimizing the number of integer points in a parallel translations of a rational convex polytope in R6 is NP-hard. We apply this result to show that the problem of finding the largest integer t s.t. the expansion tP of a rational convex polytope PR6 has fewer than k integer points, is also NP-hard. We conclude that the Ehrhart quasi-polynomials of rational polytopes can have arbitrary fluctuations.

• (with Danny Nguyen) VC-dimension of short Presburger formulas, Combinatorica, vol. 39 (2019), 923–932.

We study VC-dimension of short formulas in Presburger Arithmetic, defined to have a bounded number of variables, quantifiers and atoms. We give both lower and upper bounds, which are tight up to a polynomial factor in the bit length of the formula.

Note: The conjecture at the end of §3.3 concerning the doubly exponential upper bound for the VC-dimension of general PA formulas was resolved by Dmitry Chistikov, Christoph Haase and Alessio Mansutti in this paper.

• (with Danny Nguyen) Short Presburger arithmetic is hard, SIAM Journal on Computing, vol. 51 (2022), no. 2, article 17, 30 pp. (STOC 2017 invited issue)
published online Nov. 5, 2019, 30 pages;
the extended abstract appeared in Proc. FOCS 2017, 37–48.

We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by "short'' we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integer coefficients involved in the linear inequalities. We prove that satisfiability of Short-PA sentences with m+2 alternating quantifiers is Σm-complete or Πm-complete, when the first quantifier is ∃ or ∀, respectively. Counting versions and restricted systems are also analyzed. Further application are given to hardness of two natural problems in Integer Optimization.

Download the Featured Math. Review of the FOCS paper, by Alexander Barvinok.

See the FOCS talk video by Danny Nguyen (Oct 2017, 20 min), and my MSRI talk video (Oct 2017, 1 hr).

• (with Danny Nguyen) Complexity of short generating functions, Forum Math. Sigma, vol. 6 (2018), paper E1, 37 pages.

We give complexity analysis of the class of short generating functions (GF). Assuming #P is not in FP/poly, we show that this class is not closed under taking many intersections, unions or projections of GFs, in the sense that these operations can increase the bit length of coefficients of GFs by a super-polynomial factor. We also prove that truncated theta functions are hard in this class.

• (with Danny Nguyen) The computational complexity of integer programming with alternations, Mathematics of Operations Research, vol. 45 (2020), no. 1, 191–204.
the extended abstract appeared in Proc. CCC 2017.

We prove that integer programming with three quantifier alternations is NP-complete, even for a fixed number of variables. This complements earlier results by Lenstra and Kannan, which together say that integer programming with at most two quantifier alternations can be done in polynomial time for a fixed number of variables. As a byproduct of the proof, we show that for two polytopes P,QR4, counting the projection of integer points in Q\P is #P-complete. This contrasts the 2003 result by Barvinok and Woods, which allows counting in polynomial time the projection of integer points in P and Q separately.

See slides of the CCC talk.

Note: Theorems 1.2 and 1.4 were later extended to short systems in the "Short Presburger arithmetic is hard" paper (see above).

• (with Danny Nguyen) Complexity of short Presburger arithmetic, preprint (2017), 17 pages;
the extended abstract appeared in Proc. STOC 2017.

We study complexity of short sentences in Presburger arithmetic (Short-PA). Here by "short'' we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integers involved in the inequalities. We prove that assuming Kannan's partition can be found in polynomial time, the satisfiability of Short-PA sentences can be decided in polynomial time. Furthermore, under the same assumption, we show that the numbers of satisfying assignments of short Presburger sentences can also be computed in polynomial time.

Note: This paper is superseded by our "Short Presburger arithmetic is hard" paper (see above). It will not be published in a journal.

• (with Danny Nguyen) Enumeration of integer points in projections of unbounded polyhedra, SIAM J. Discrete Math, vol. 32 (2018), no. 2, 986-1002.
The extended abstract appeared in Proc. IPCO 2017, Lecture Notes in Comput. Sci., vol. 10328, Springer, 2017, 417-429 (see link here).

We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections of semilinear subsets of the integer lattice. We extend the results to general formulas in Presburger Arithmetic. We also give an application to the k-Frobenius problem.

• On sampling integer points in polyhedra, in Foundations of computational mathematics (Hong Kong, 2000), World Scientific, River Edge, NJ, 2002, pages 319-324.

We investigate the problem of sampling integer points in rational polyhedra provided an oracle for counting these integer points. When the dimension is bounded, this assumption is justified in view of a recent algorithm due to Barvinok. We show that in full generality the exactly uniform sampling is possible, when the oracle is called polynomial number of times. Further, when Barvinok's algorithm is used, poly-log number of calls suffices.

• Four questions on Birkhoff polytope, Annals of Combinatorics, vol. 4 (2000), 83-90.

The questions are: what is the volume of Birkhoff polytope, how fast the simplex method works, how fast the vertex nearest neighbor random walk mixes, and what about mixing on other 0-1 polytopes?

Note: The asymptotics of the volume of Birkhoff polytope in Question 1.1 was resolved by Rodney Canfield and Brendan McKay in this paper.
A generalization of Theorem 1.7 to permutation polytopes is given by Robert Guralnick and David Perkinson in this paper.

## Geometric Combinatorics

• (with Alexey Glazyrin) Domes over curves, International Mathematics Research Notices, 2022, no. 18, 14067–14104;
published online June 2, 2021.

A closed PL-curve is called integral if it is comprised of unit intervals. Kenyon's problem asks whether for every integral curve γ in R3, there is a dome over γ, i.e. whether γ is a boundary of a polyhedral surface whose faces are equilateral triangles with unit edge lengths. First, we give an algebraic necessary condition when γ is a quadrilateral, thus giving a negative solution to Kenyon's problem in full generality. We then prove that domes exist over a dense set of integral curves. Finally, we give an explicit construction of domes over all regular n-gons.

See my Zoom talk video and slides at the Selected Topics in Mathematics seminar, University of Liverpool (Feb. 2021), or
Zoom talk video and slides at the Polytopics: Recent advances on polytopes Conference at Max Planck Institute (Apr. 7, 2021).
See a general audience version of this talk Polyhedral domes, Colloquium, Kings College London, UK, Zoom talk video and slides (May 4, 2021).

See also Alexey Glazyrin's Zoom talk video and his slides, at MIPT geometry seminar (Dec. 4, 2020).

Note: An alternative solution of Kenyon's problem was later found here.

• (with Alexey Garber) Concrete polytopes may not tile the space, Mathematika, vol. 66 (2020), 920–926.

Brandolini et al. conjectured in [BCRT] that all concrete lattice polytopes can multitile the space. We disprove this conjecture in a strong form, by constructing an infinite family of counterexamples in R3.

• (with Karim Adiprasito, Gaku Liu and Michael Temkin) Log smoothness and polystability over valuation rings, preprint (2018), 40 pages.

Let 𝒪 be a valuation ring of height one of residual characteristic exponent p and with algebraically closed field of fractions. Our main result provides a best possible resolution of the monoidal structure MX of a log variety X over 𝒪 with a vertical log structure: there exists a log modification Y → X, such that the monoidal structure of Y is polystable. In particular, if X is log smooth over 𝒪, then Y is polystable with a smooth generic fiber. As a corollary we deduce that any variety over 𝒪 possesses a polystable alteration of degree pn. The core of our proof is a subdivision result for polyhedral complexes satisfying certain rationality conditions.

• (with Stedman Wilson) Skyscraper polytopes and realizations of plane triangulations, Journal of Combinatorial Theory, Ser. B, vol. 127 (2017), 82-110.
(formerly "A quantitative Steinitz theorem for plane triangulations")

We give a new proof of Steinitz's classical theorem in the case of plane triangulations, which allows us to obtain a new general bound on the grid size of the simplicial polytope realizing a given triangulation, subexponential in a number of special cases. Formally, we prove that every plane triangulation G with n vertices can be embedded in R2 in such a way that it is the vertical projection of a convex polyhedral surface. We show that the vertices of this surface may be placed in a 4n3 x 8n5 x ζ(n) integer grid, where ζ(n) < (500 n8)τ(G) and τ(G) denotes the shedding diameter of G, a quantity defined in the paper.

• (with Assaf Oren and Rom Pinchasi) On the odd area of planar sets, Discrete & Computational Geometry, vol. 55 (2016), 715-724.

The main result in the paper is a construction of a simple (in fact, just a union of two squares) set T in the plane with the following property. For every ε> 0 there is a family F of an odd number of translates of T such that the area of those points in the plane that belong to an odd number of sets in F is smaller than ε.

Note: The odd area of a unit circle remains open. The odd area of rational polygons is bounded away from zero; this was proved by Rom Pinchasi and Yuri Rabonivich in this paper.

• (with Dan Vilenchik) Constructing uniquely realizable graphs, Discrete & Computational Geometry, vol. 50 (2013), 1051-1071.

In the Graph Realization Problem (GRP), one is given a graph G, a set of non-negative edge-weights, and an integer d. The goal is to find, if possible, a realization of G in the Euclidian space Rn, such that the distance between any two vertices is the assigned edge weight. The problem has many applications in mathematics and computer science, but is NP-hard when the dimension d is fixed. Characterizing tractable instances of GRP is a classical problem, first studied by Menger in 1931 in the case of a complete graph.

We construct two new infinite families of GRP instances whose solution can be approximated up to an arbitrary precision in polynomial time. Both constructions are based on the blow-up of fixed small graphs with large expanders. Our main tool is the Connelly's condition in Rigidity Theory, combined with an explicit construction and algebraic calculations of the rigidity (stress) matrix. As an application of our results, we give a deterministic construction of uniquely k-colorable vertex-transitive expanders.

• (with Eryk Kopczyński and Piotr Przytycki) Acute triangulations of polyhedra and Rn, Combinatorica, vol. 32 (2012), 85-110.

We study the problem of acute triangulations of convex polyhedra and the space Rn. Here the acute triangulation is a triangulation into simplices whose dihedral angles are acute. We prove that acute triangulations of the n-cube do not exist for n≥4. Further, we prove that acute triangulations of the space Rn do not exist for n≥5. In the opposite direction, we present a construction of an acute triangulation of the cube and the regular octahedron in R3. We also prove nonexistence of an acute triangulation of R4 if all dihedral angles are bounded away from π/2.

Download .pdf file of the paper, or .pdf of the French abstract.
Go to this page to see animations of acute triangulations from the paper.

The extended abstract of the paper has appeared in Proc. Symp. Computational Geometry (SCG'2010), ACM, New York, 2010, 307–313.
Download .pdf file of the extended abstract. Note that the proceedings version does not contain the Appendix.

• (with Rom Pinchasi) How to cut out a convex polyhedron, preprint (2011).

It is known that one can fold a convex polyhedron from a non-overlapping face unfolding, but the complexity of the algorithm in [Miller-Pak] remains an open problem. In this paper we show that every convex polyhedron P in Rd can be obtained in polynomial time, by starting with a cube which contains P and sequentially cutting out the extra parts of the surface.

Our main tool is of independent interest. We prove that given a convex polytope P in Rd and a facet F of P, then F is contained in the union of AG. Here the union is over all the facets G of P different from F, and AG is the set obtained from G by rotating towards F the hyperplane spanned by G about the intersection of it with the hyperplane spanned by F.

• (with Jean-Marc Schlenker) Profiles of inflated surfaces, J. Nonlinear Math. Phys., vol. 17 (2010), no. 2, 145–157.

We study the shape of inflated surfaces introduced in [Bleecker] and [Pak]. More precisely, we analyze profiles of surfaces obtained by inflating a convex polyhedron, or more generally an almost everywhere flat surface, with a symmetry plane. We show that such profiles are in a one-parameter family of curves which we describe explicitly as the solutions of a certain differential equation.

• Inflating polyhedral surfaces, preprint (2006), 37 pages.

We prove that all polyhedral surfaces in R3 have volume-increasing piecewise-linear isometric deformations. This resolves the conjecture of Bleecker who proved it for convex simplicial surfaces [Bleecker]. Further, we prove that all convex polyhedral surfaces in Rd have convex volume-increasing piecewise-linear isometric deformations. We also discuss the limits on the volume of such deformations, present a number of conjectures and special cases.

The pictures are better viewed in color, but should print fine on a monochromatic printer.

• A short proof of rigidity of convex polytopes, Siberian J. Mathematics, vol. 47 (2006), 859-864.

We present a much simplified proof of Dehn's theorem on the infinitesimal rigidity of convex polytopes. Our approach is based on the ideas of Trushkina [here] and Schramm [here].

Download .pdf file of the Russian translation, or go to the journal web site.
See also talk Caged eggs and the rigidity of convex polyhedra (Oded Schramm Memorial Conference, MSFT, Sep. 2009). Video and slides.

• The area of cyclic polygons: Recent progress on Robbins' Conjectures, mini survey, Advances Applied Math. vol. 34 (2005), 690-696 (special issue in memory of David Robbins).

In his works [R1] and [R2] David Robbins proposed several interrelated conjectures on the area of the polygons inscribed in a circle as an algebraic function of its sides. Most recently, these conjectures have been established in the course of several independent investigations. In this note we give an informal outline of these developments.

• (with Andre Henriques) Volume-preserving PL-maps between polyhedra, preprint (2004), 17 pages; a much simpler proof was later incorporated into Section 18 (Monge problem for polytopes) of my book.

We prove that for every two d-dimensional convex polytopes P, Q with vol(P)= vol(Q), there exists a continuous piecewise-linear (PL) volume-preserving map f: P -> Q. The result extends to general PL-manifolds. The proof is inexplicit and uses the corresponding fact in the smooth category, proved by Moser [M]. We conclude with various examples and combinatorial applications.

• (with Maksym Fedorchuk) Rigidity and polynomial invariants of convex polytopes, Duke Math. J., vol. 129 (2005), 371-404.

We present an algebraic approach to the classical problem of constructing a simplicial convex polytope given its planar triangulation and lengths of its edges. We introduce a ring of polynomial invariants of the polytope and show that they satisfy polynomial relations in terms of squares of edge lengths. We obtain sharp upper and lower bounds on the degree of these polynomial relations. In a special case of regular bipyramid we obtain explicit formulae for some of these relations. We conclude with a proof of Robbins Conjecture on the degree of generalized Heron polynomials.

• (with Ezra Miller) Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings, Discrete and Computational Geometry, vol. 39 (2008), no. 1-3 (Special Twentieth Anniversary issue), 339-388.

We initiate a systematic investigation of the metric combinatorics of convex polyhedra by proving the existence of polyhedral nonoverlapping unfoldings and analyzing the structure of the cut locus. The algorithmic aspect, which we include together with its complexity analysis, was for us a motivating feature of these results. We also show that our general methods extend to the abstract spaces we call 'convex polyhedral pseudomanifolds', whose sectional curvatures along low-dimensional faces are all positive. We also propose some directions for future research, including a series of precise conjectures on the number of combinatorial types of shortest paths, and on the geometry of unfolding boundaries of polyhedra.

The pictures are colored and better viewed in color.
They should print fine on a monochromatic printer.

Note: Conjectures 9.2-4 and 9.6 remain open.
The results of §7 were reproved by Florian Frick in his thesis (Ch. 4), with a similar but more streamlined and conceptual argument.
The continuous blooming conjecture 9.12 in R3 was proved by Erik Demaine, Martin Demaine, Vi Hart, John Iacono, Stefan Langerman and Joseph O’Rourke in this paper.

• On the number of faces of certain transportation polytopes, European J. Combinatorics, vol. 21 (2000), 689-694.

Define transportation polytope T(n,m) to be a polytope of nonnegative n x m matrices with row sums equal to m and column sums equal to n. We present an efficient algorithm for computing the numbers of the k-dimensional faces for the transportation polytope T(n,n+1). The construction relies on the new recurrence relation for which is of independent interest.

• (with Alex Postnikov) Transversal Matroids and Strata on Grassmannians, Funct. Anal. Appl., vol. 29 (1995) 140-143.

We discuss combinatorial and topological properties of strata on Grassmanians which correspond to transversal matroids. Applications to hypergeometric functions are also given.

Download .pdf file of the paper or .pdf file of the Russian original.

## Tilings in the Plane and in the Space

• (with Adam Sheffer and Martin Tassy) Fast domino tileability, Discrete & Computational Geometry, vol. 56 (2016), 377-394.

Domino tileability is a classical problem in Discrete Geometry, famously solved by Thurston for simply connected regions in nearly linear time in the area. In this paper, we improve upon Thurston's height function approach to a nearly linear time in the perimeter.

Note: The approach to tilings based on extending 1-Lipschitz functions from boundary to the interior, was generalized to general graphs in this paper by Nishant Chandgotia, Martin Tassy and myself. This answered the question in §5.5.

• (with Jed Yang) The complexity of generalized domino tilings, Electronic Jour. Combin., vol. 20, issue 4 (2013), P12, 23 pages.

Tiling planar regions with dominoes is a classical problem, where the decision and counting problems are polynomial. We establish a variety of hardness results (both NP- and #P-completeness), for different generalizations of dominoes in three and higher dimensions.

Link to the journal version: is here.

Note: Disconnectedness of the space of domino tilings in Prop. 8.1 was further extended via topological invariant in this paper by Juliana Freire, Caroline Klivans, Pedro Milet and Nicolau Saldanha. This both proves and gives a conceptual explanation why even large bricks can have disconnected space of domino tilings.

• (with Jed Yang) Tiling simply connected regions with rectangles, Journal of Combinatorial Theory, Ser. A, vol. 120 (2013), 1804–1816.

In 1995, Beauquier, Nivat, Rémila, and Robson showed that tiling of general regions with two rectangles is NP-complete, except for few trivial special cases. In a different direction, in 2005, Rémila showed that for simply connected regions and two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 106 rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.

Download .pdf file of the paper (Warning: it is color optimized, so if printed try to use a color printer).

Note: The above version is identical to the arXiv version. The journal version: .pdf file.
It is somewhat abridged at journal's request. Notably, it is missing proof of Lemma 3.2 replaced with a UTM argument.

Note: Jed Yang's thesis (2012) contains expanded definitive versions of both, with constants substantially improved.

• (with Michael Korn) Tilings of rectangles with T-tetrominoes, Theoretical Computer Science, vol. 319 (2004), 3-27 (special issue on tilings).

We prove that any two tilings of a rectangular region by T-tetrominoes are connected by moves involving only 2 and 4 tiles. We also show that the number of such tilings is an evaluation of the Tutte polynomial. The results are extended to more general class of regions.

Note: Despite claims in the literature, Conjecture 18 remains unresolved.

• Tile Invariants: New Horizons, Theoretical Computer Science, vol. 303 (2003), 303-331 (special issue on tilings).

Let T be a finite set of tiles. The group of invariants G(T), introduced by the author, is a group of linear relations between the number of copies of the tiles in tilings of the same region. We survey known results about G(T), the height function approach, the local move property, various applications and special cases.

• (with Cris Moore) Ribbon tile invariants from signed area, Journal of Combinatorial Theory, Ser. A, vol. 98 (2002), 1-16.

Ribbon tiles are polyominoes consisting of n squares laid out in a path, each step of which goes north or east. Tile invariants were first introduced in [Pak], where a full basis of invariants of ribbon tiles was conjectured. Here we present a complete proof of the conjecture, which works by associating ribbon tiles with a certain polygon in the complex plane, and deriving invariants from the signed area of this polygon.

• (with Roman Muchnik) On tilings by ribbon tetrominoes, Journal of Combinatorial Theory, Ser. A, vol. 88 (1999), 188-193.

We resolve a problem posed in our previous paper by extending the set of regions to all simply connected regions in the case n=4. Conway-Lagarias type technique is employed.

• Ribbon tile invariants, Trans. AMS., vol. 352 (2000), 5525-5561.

Consider a set of ribbon tiles which are polyominoes with n squares obtained by up and right rook moves. We describe all the linear relations for the number of times each such tile can appear in a tiling of any given row convex region. We also investigate the connection with signed tilings and give applications of tileability.

Compare reviews in Zbl. Math. and Math. Reviews. See also a .pdf file of an extended abstract (10 pages), which appeared in FPSAC'98 Conference Proceedings.

Note:
Conjecture 10.1 was proved by Cris Moore and IP in this paper.
A stronger Conjecture 10.2 was later proved by Scott Sheffield in this paper.
For earlier literature and further reference see here.

## Enumerative and Analytic Combinatorics

• Complexity problems in enumerative combinatorics, in Proc. ICM Rio de Janeiro, vol. 3, 2018, 3139–3166.

We give a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.

Important note: This is an expanded and corrected version which coincides with the arXiv version. Notably, Section 4 and a number of references are added. The published version also has typesetting issues, so please do not read it.

Here is the video of the talk. The paper is better, of course.
Section 4 is discussed in this talk. Zoom talk video and slides.

See my blog post announcing the paper with links to earlier ICM papers.

• (with Scott Garrabrant) Pattern avoidance is not P-recursive, preprint (2015), 18 pages.
A short version published as Permutation patterns are hard to count, in Proc. 27th SODA, ACM, New York, 2016, 923–936.

Let F ⊂ Sk be a finite set of permutations and let Cn(F) denote the number of permutations σ ∈ Sn avoiding the set of patterns F. The Noonan-Zeilberger conjecture states that the sequence {Cn(F)} is P-recursive. We disprove this conjecture. The proof uses Computability Theory and builds on our earlier work [GP1]. We also give two applications of our approach to complexity of computing {Cn(F)}.

Read also my blog post on the paper.

See video and slides of Prague talk based on the paper.

Note: Richard Stanley says this about our work in his recent interview to ECA:

"A topic within enumerative combinatorics that seems ripe for further investigation is developing a theory for showing that a given generating function (in one variable) does not have some desirable property, such as being D-finite or differentially algebraic. There are a number of results in this area, but nothing approaching a general theory. The most significant work in this direction (in my opinion) is the disproof of the Noonan-Zeilberger Conjecture by Scott Garrabrant and Igor Pak."

• (with Scott Garrabrant) Words in linear groups, random walks, automata and P-recursiveness, Journal of Combinatorial Algebra, vol. 1 (2017), 127-144.

Let S be a generating set of a finitely generated group G . Denote by an the number of words in S of length n that are equal to 1. We show that the cogrowth sequence {an} is not always P-recursive. This is done by developing new combinatorial tools and using known results in computability and probability on groups.

Note: This paper resolves a problem by Maxim Kontsevich stated by Richard Stanley here.

Watch my talk on the paper (BIRS, March 9, 2015).

• (with Scott Garrabrant) Counting with irrational tiles, preprint (2014), 29 pages.

We introduce and study the number of tilings of unit height rectangles with irrational tiles. We prove that the class of sequences of these numbers coincides with the class of diagonals of N-rational generating functions and a class of certain binomial multisums. We then give asymptotic applications and establish connections to hypergeometric functions and Catalan numbers.

Download the .pdf file of the paper (best printed on a color printer).

• (with Robin Pemantle) On the longest k-alternating subsequence, Electronic Jour. Combin., vol. 22, issue 1 (2015), P48, 7 pages.

A permutation is called k-alternating if it is alternating, and all jumps are at least k. We show that the longest k-alternating substring of a random permutation has length asymptotic to 2(n-k)/3.

Link to the journal version: is here.

Note: Armstrong's conjecture was later proved by Tommy Cai in this paper.

• (with Theodore Dokos) The expected shape of random doubly alternating Baxter permutations, Online Journal of Analytic Combinatorics, vol. 9 (2014), 12 pages.

Guibert and Linusson introduced in [GL] the family of doubly alternating Baxter permutations, i.e. Baxter permutations σ in Sn, such that σ and σ-1 are alternating. They proved that the number of such permutations in S2n and S2n+1 is the Catalan number Cn. In this paper we explore the expected limit shape of such permutations, following the approach by Miner and Pak [MP].

Download the .pdf file of the paper (best printed on a color printer).
Here is the journal version of the paper.
Warning: the file is 1.8Mb.

Note: The limit shape of Baxter permutations was recently studied by Jacopo Borga and Mickaël Maazoun in this paper.

• (with Sam Miner) The shape of random pattern-avoiding permutations, Advances in Applied Math., vol. 55 (2014), 86-130.

We initiate the study of limit shapes for random permutations avoiding a given pattern. Specifically, for patterns of length 3, we obtain delicate results on the asymptotics of distributions of positions of numbers in the permutations. We view the permutations as 0-1 matrices to describe the resulting asymptotics geometrically. We then apply our results to obtain a number of results on distributions of permutation statistics.

Download the .pdf file of the paper (best printed on a color printer).

Note: At the request of editors, the preprint version has been shortened for publication. The published article is missing some pictures, few corollaries and some proof details. Here is the .pdf file of the article.

Note: Conjectures in §9.5 and the Open Problem in §9.8 follow from a more detailed analysis by Christopher Hoffman, Douglas Rizzolo, Erik Slivken in this and that papers.

• (with Matjaž Konvalinka) Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Ser. A, vol. 123 (2014), 86-91.

In 1857, Cayley showed that certain sequences, now called Cayley compositions, are equinumerous with certain partitions into powers of 2. In this paper we give a simple bijective proof of this result and obtain several extensions. We then extend this bijection to an affine linear map between convex polyhedra to give and new proof of Braun's conjecture.

• (with Matjaž Konvalinka) Triangulations of Cayley and Tutte polytopes, Advances in Math., vol. 245 (2013), 1-33.

Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun's conjecture, which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to two one-variable deformations of Cayley polytopes (which we call t-Cayley and t-Gayley polytopes), and to the most general two-variable deformations, which we call Tutte polytopes. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph.

Our approach is based on an explicit triangulation of the Cayley and Tutte polytope. We prove that simplices in the triangulations correspond to labeled trees, and use properties of the Tutte polynomials to computes the volume of the polytopes. The heart of the proof is a direct bijection based on the neighbors-first search graph traversal algorithm.

• (with Amanda Redlich) Long cycles in abc-permutations, Functional Analysis & Other Mathematics, vol. 2 (2008), no. 1, 87-92.

An abc-permutation is a permutation σabc in Sn generated by exchanging an initial block of length a and a final block of length c of {1...n}, where n=a+b+c. In this note we compute the limit of the probability that a random abc-permutation is a long cycle. This resolves an open problem V. Arnold posed in 2002.

Note: The published version contained a crucial mistake in the proof of Lemma 2. The mistake was fixed in the erratum and the new proof of Lemma 2 is much shorter and simpler.

• (with Pavel Etingof) An algebraic extension of the MacMahon Master Theorem, Proc. A.M.S., vol. 136 (2008), 2279-2288.

We present a new algebraic extension of the classical MacMahon Master Theorem. The basis of our extension is the Koszul duality for non-quadratic algebras defined by Berger. Combinatorial implications are also discussed.

Note: As suggested in §6.4, the identities in the paper have combinatorial proofs by an explicit involution found by Anthony Mendes and Jeffrey Remmel in a series of papers which were published at about the same time. In fact, they discovered the identities independently and greatly generalized them, summarizing their work in this monograph.

• (with Matjaž Konvalinka) Non-commutative extensions of the MacMahon Master Theorem, Advances in Math., vol. 216 (2007), 29-61.

We present several non-commutative extensions of the MacMahon Master Theorem, further extending the results of Cartier-Foata and Garoufalidis-Lê-Zeilberger. The proofs are combinatorial and new even in the classical cases. We also give applications to the Foata-Zeilberger's β-extension and Krattenthaler-Schlosser's q-analogue.

See also a .pdf file of an extended abstract (11 pages), which will appear in the FPSAC'07 Conference Proceedings.

Note: The original version (v2) of [HL] preprint had only one, not multiple parameters, which were introduced in our paper. As we suggested in §13.2, the algebraic approach extends to the multiple parameters, which was done in the revised version of the same arXiv preprint (v3).

• (with Sergi Elizalde) Bijections for refined restricted permutations, Journal of Combinatorial Theory, Ser. A, vol. 105 (2004), 207-219.

We present a bijection between 321- and 132-avoiding permutations that preserves the number of fixed points and the number of excedances. This gives a simple combinatorial proof of recent results of Robertson, Saracino and Zeilberger [RSZ], and the first author [E]. We also show that our bijection preserves additional statistics, which extends the previous results.

• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees, Discrete Mathematics, vol. 204 (1999), 329-335 (special Henry W. Gould anniversary volume).

Transpositions of the form (1,i) are called star transpositions. We compute the diameter and the number of reduced decompositions for various permutations.

Note: The main result of the paper was generalized by John Irving and Amarpreet Rattan in this paper, thus resolving the open problem in Remark 1.2.

• (with A. Kuznetzov and A. Postnikov) Trees Associated with the Motzkin Numbers, Journal of Combinatorial Theory, Ser. A, vol. 76 (1996), 145-147.

We consider plane rooted trees on n+1 vertices without branching points on odd levels. The number of such trees in equal to the Motzkin number. We give a bijective proof of this statement.

• (with A. Postnikov and V. Retakh) Noncommutative Lagrange Theorem and Inversion Polynomials, FPSAC'95 Conference Proceedings (Paris, 1995).

We present a new version and a combinatorial proof of the noncommutative quasideterminants of Gelfand-Retakh. Various combinatorial applications are discussed.

• (with A. Kuznetzov and A. Postnikov) Increasing Trees and Alternating Permutations, Russian Math. Surveys, vol. 49 (1994), 79-110.

We consider several classes of increasing trees, which are equinumerable with alternating permutations (also called updown permutations). We also consider various statistics on these trees and relations with André polynomials and the Foata group, Entringer and Euler-Bernoulli numbers. Most proofs are bijective.

Download .pdf file of the paper, or .pdf file of the Russian original.

• Computation of the Tutte polynomial of complete graphs, preprint (1993).

Partly incorporated into "Triangulations of Cayley and Tutte polytopes".

## Asymptotic Algebraic Combinatorics

• (with Greta Panova) Durfee squares, symmetric partitions and bounds on Kronecker coefficients, Journal of Algebra, vol. 629 (2023), 358–380.

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.

• Skew shape asymptotics, a case-based introduction, Séminaire Lotharingien de Combinatoire, Issue 84, Article B84a (2021), 26 pp.

We discuss various tools in the emerging area of Asymptotic Algebraic Combinatorics, as they apply to one running example of thick ribbons. Connections to other areas, exercises and open problems are also included.

• (with Greta Panova) Breaking down the reduced Kronecker coefficients, Comptes Rendus Acad. Sci. Paris, Ser. I. Math., vol. 358, issue 4 (2020), 463–468.

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

Note: The conjecture in §4.5 (see also §4.6) was completely resolved by Christian Ikenmeyer and Greta Panova in this paper.

Note: In the published version, French title is different, reflecting the usual "lost in translation" effect. See also this MFO report (page 2), for the short story of how the first part of the paper came about.

• (with Greta Panova) Bounds on Kronecker coefficients via contingency tables, Linear Algebra and Its Applications, vol. 602 (2020), 157–178.

We present both upper and lower bounds for Kronecker coefficients g(λ,μ,ν) in terms of in term of the number of certain contingency tables. Various asymptotic applications and generalizations are also presented.

Erratum: The statement of Theorem 1.3 is too strong. The summation is over all λ⊢n, not over self-conjugate partitions λ=λ', λ⊢n.
Later, in our Durfee squares paper, we fix the mistake and obtain a much stronger bound. More precisely, we resolve Conj. 9.8 up to a constant factor in the exponent.

Note: An expanded version of the paper is posted on the arXiv under title "Upper bounds on Kronecker coefficients with few rows" (2020), 18 pages. It presents two more approaches: via Kostka numbers and via (multi-) Littlewood–Richardson coefficients. It is missing an orbit variation of the binary contingency tables upper bound and some examples that follow.

See also this and that talk by Greta Panova based in part on this paper.

• (with Alejandro Morales and Greta Panova) Asymptotics of principal evaluations of Schubert polynomials for layered permutations, Proc. AMS., vol. 147 (2019), 1377–1389.

Denote by u(n) the largest principal specialization of the Schubert polynomial over all σ in Sn. Stanley conjectured that there is a limit of (1/n2) log u(n) and asked for a limiting description of permutations σ achieving the maximum u(n). Merzon and Smirnov conjectured that this maximum is achieved on layered permutations. We resolve both Stanley's problems restricted to layered permutations.

• (with Greta Panova and Damir Yeliussizov) On the largest Kronecker and Littlewood–Richardson coefficients, J. Combin. Theory, Ser. A., vol. 165 (2019), 44–77.

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.

• (with Alejandro Morales and Martin Tassy) Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings, Combinatorics, Probability and Computing, vol. 31 (2022), 550–573.
Published online here 21 October, 2021.

We prove and generalize a conjecture in [MPP18] about the asymptotics of the number of standard Young tableaux of skew shape λ/μ which have stable limit shape under the 1/√ n  scaling. The proof is based on the variational principle on the partition function of certain weighted lozenge tilings.

See this talk by Alejandro Morales, and this followup talk.

• (with Alejandro Morales and Greta Panova) Asymptotics of the number of standard Young tableaux of skew shape, European J. Combin., vol. 70 (2018), 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.

See also slides of my BCC talk based in part on the paper.

Note: The generalization of Proposition 12.1 suggested in Remark 12.2 was obtained in this paper.
Conjecture in §13.7 was proved and generalized in this paper.

## Algebraic Combinatorics and Young tableaux

• (with Alejandro Morales and Greta Panova) Hook formulas for skew shapes IV. Increasing tableaux and factorial Grothendieck polynomials, Zapiski Nauchnykh Seminarov POMI, vol. 507 (2021), S.V. Kerov memorial issue, 59–98.
Reprinted in Journal of Math. Sciences, vol. 261 (2022), 630–657.

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 (see MPP-I, MPP-II and MPP-III below).

See video and slides of the talk based on the paper.
See also video and slides on Greta's CAE talk on the subject (May 2022).

• (with Zachary Hamaker, Alejandro Morales, Luis Serrano and Nathan Williams) Bijecting hidden symmetries for skew staircase shapes, Algebraic Combinatorics, vol. 6 (2023), no. 4, 1095-1118.

We present a bijection between the set of standard Young tableaux of staircase minus rectangle shape, and a set of marked shifted standard Young tableaux of a certain shifted shape. Numerically, this result is due to [DeWitt]. Combined with other known bijections this gives a bijective proof of the product formula for the number of standard Young tableaux of staircase minus rectangle shape. This resolves an open problem in [Morales, Pak and Panova], and allows for efficient random sampling. Other applications include a bijection for semistandard Young tableaux, and a bijective proof of Stembridge's symmetry of LR-coefficients of the staircase shape. We also extend these results to set-valued standard Young tableaux in the combinatorics of K-theory, leading to new proofs of results by [Lewis and Marberg] and [Abney-McPeek, An and Ng].

The journal version is available here.

Note: The 2006 email from John Stembridge to Vic Reiner can be found quoted here.

• (with Fëdor Petrov) Hidden symmetries of weighted lozenge tilings, Electronic Journal of Combinatorics, vol. 27, issue 3 (2020), #P3.44, 18 pages.

We study the weighted partition function for lozenge tilings, with weights given by multivariate rational functions originally defined in [MPP3] in the context of the factorial Schur functions. We prove that this partition function is symmetric for large families of regions. We employ both combinatorial and algebraic proofs.

• (with Alejandro Morales and Greta Panova) Hook formulas for skew shapes III. Multivariate and product formulas, Algebraic Combinatorics, vol. 2 (2019), 815-861.

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 [MPP1] and [MPP2]. 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.

Warning: the pictures are nicely colored, so the paper is best read when printed on a color printer. Welcome to the 21st century!
See also video of a talk by Greta Panova in part based on this paper (starting 50:13).

Note: The journal version has subpar typesetting and mislabeled references. Please refer to the above or the arXiv version.

The extended abstract of the paper was published in Proc. FPSAC 2018, in Séminaire Lotharingien de Combinatoire, 80B.84 (2018), 12 pages, available here.

Note:
Conjectures 5.17 and 9.6 were proved by Jang Soo Kim and Meesue Yoo in this paper.
Conjecture (**) in §6.1 was proved by Alejandro Morales, Igor Pak and Martin Tassy in this paper.
Theorem 3.10 which was key to the paper was given an elementary proof in this paper with Fëdor Petrov.
This result was also shown to follow from this paper by Daniel Bump, Peter McNamara and Maki Nakasuji (the connection is nontransparent).

• (with Alejandro Morales and Greta Panova) Hook formulas for skew shapes II. Combinatorial proofs and enumerative applications, SIAM J. Discrete Math., vol. 31 (2017), 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 [MPP1] 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.

Note:
Conjectures 9.3 and 9.6 were proved by Byung-Hak Hwang, Jang Soo Kim, Meesue Yoo and Sun-mi Yun in this paper.
Independently, Conjecture 9.6 was proved by Peter Guo, C.D. Zhao and Michael Zhong in this paper.

• (with Alejandro Morales and Greta Panova) Hook formulas for skew shapes I. q-analogues and bijections, Journal of Combinatorial Theory, Ser. A, vol. 154 (2018), 350-405.

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.

Warning: the pictures are colored, so the paper is best read when printed on a color printer.

Note: The original version of the paper has been expanded and split into two papers in a series: I and II. Download .pdf file of the original version (44 pages)
The shifted analogue proposed in §10.7 was obtained by Hiroshi Naruse and Soichi Okada in this paper.

Supplemental materials for this and other paper in the series:
1) Sage worksheet with most examples and conjectures in the paper,
2) an elementary but curious special case, see also a direct proof on Math.StackExchange, and WolframAlpha check of the key induction step.

See also this talk by Greta Panova, and that talk by Alejandro Morales.

• (with Greta Panova) Bounds on certain classes of Kronecker and q-binomial coefficients, J. Combin. Theory, Ser. A., vol. 147 (2017), 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 as polynomials in q to derive sharp bounds on the differences of their consecutive coefficients. We then derive effective asymptotic lower bounds for a wider class of Kronecker coefficients.

See also this talk by Greta Panova based in part on that paper.

Note: The asymptotically tight bounds in the middle range improving Thm 1.2 by a polynomial factor, were proved by Stephen Melczer, Greta Panova and Robin Pemantle in this paper.

• (with Greta Panova) On the complexity of computing Kronecker coefficients, Computational Complexity, vol. 26 (2017), 1-36.

We study the complexity of computing Kronecker coefficients g(α,μ,ν). We give explicit bounds in terms of the number of part 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 log N, but depend exponentially on . Moreover, similar bounds hold even when M = exp O(ℓ). By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(log N) 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 Sn are also considered.

Note: We mangled our attribution to Hepler's thesis. His hardness results for unary partitions implies those for binary partition, of course. Both our Theorem 7.1 and Hepler's results (see §4.1.6) are greatly extended in this paper (2022).

• (with Greta Panova) Strict unimodality of q-binomial coefficients, Comptes Rendus Acad. Sci. Paris, Ser. I. Math., vol. 351 (2013), no. 11-12, 415-418.

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 Sn representations. This extends classical unimodality result by J.J. Sylvester.

Warning: This version is a different from the published article, revised to fix a subtle mistake. It is the same as latest arXiv version.

Here is Sylvester's original article "Proof of the hitherto undemonstrated Fundamental Theorem of Invariants" (Philosophical Magazine, 1878).
Here is Cayley's original article "A Second Memoir upon Quantics" (Philosophical Transactions of the Royal Society of London, 1856) with the unimodality conjecture.

• (with Greta Panova) Unimodality via Kronecker products, Journal of Algebraic Combinatorics, vol. 40 (2014), 1103-1120.

We present new proofs and generalizations of unimodality of the q-binomial (Gaussian) coefficients as polynomials in q. We use an algebraic approach by interpreting the differences between numbers of certain partitions as Kronecker coefficients of representations of Sn. Other applications of this approach include strict unimodality of the diagonal q-binomial coefficients and unimodality of certain partition statistics.

• (with Greta Panova and Ernesto Vallejo) Kronecker products, characters, partitions, and the tensor square conjectures, Advances in Math., vol. 288 (2016), 702-731.

We study the remarkable Saxl conjecture which states that tensor squares of certain irreducible representations of the symmetric groups Sn 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 Sn.

Note: Further progress on the Saxl conjecture is made here, there and there .

• (with Ionuţ Ciocan-Fontanine and Matjaž Konvalinka) Quantum cohomology of the Hilbert scheme and the weighted hook walk on Young diagrams, Journal of Algebra, vol. 349 (2012), 268–283.

Following the work of Okounkov-Pandharipande [OP1], [OP2] and Diaconescu [D], we study the equivariant quantum cohomology of the Hilbert scheme and the relative Donaldson-Thomas theory. Using the ADHM construction and a recent work [CDKM], we continue the study the Gromov-Witten invariant of the abelian/nonabelian correspondence, and establish a connection between the J-function of the Hilbert scheme and a certain combinatorial identity in two variables. This identity is then generalized to a multivariate identity, which simultaneously generalizes the branching rule for the dimension of irreducible representations of the symmetric group in the staircase shape. We then establish this identity by a weighted generalization of the Greene-Nijenhuis-Wilf hook walk, which is of independent interest.

• (with Ionuţ Ciocan-Fontanine and Matjaž Konvalinka) The weighted hook length formula, J. Combin. Theory, Ser. A., vol. 118 (2011), 1703-1717.

Based on the ideas in our previous paper [CKP], we introduce the weighted analogue of the branching rule for the classical hook length formula, and give two proofs of this result. The first proof is completely bijective, and in a special case gives a new short combinatorial proof of the hook length formula. Our second proof is probabilistic, generalizing the (usual) hook walk proof of Green-Nijenhuis-Wilf, as well as the q-walk of Kerov. Further applications are also presented.

An extended abstract of this paper appeared in Proc. FPSAC 2010 (San Francisco, CA).

• (with Ernesto Vallejo) Reductions of Young tableau bijections, SIAM J. Discrete Math., vol. 24 (2010), 113-145.

We introduce notions of linear reduction and linear equivalence of bijections for the purposes of study bijections between Young tableaux. Originating in Theoretical Computer Science, these notions allow us to give a unified view of a number of classical bijections, and establish formal connections between them. Along the way we establish a number unexpected connections between classical Young tableaux bijections and make several intriguing conjectures.

Note: Different parts of Conjecture 1 were established by Vladimir Danilov and Gleb Koshevoy in this paper and Olga Azenhas in this paper (later incorporated here). Conjecture 3 was proved by André Henriques and Joel Kamnitzer in this paper (Thm. 7.9). The question in was resolved in §6.7 was resolved by Olga Azenhas, Alessandro Conflitti and Ricardo Mamede here.

• Periodic permutations and the Robinson-Schensted correspondence, preprint (2003), 13 pages.

We introduce a group of periodic permutations, a new version of the infinite symmetric group. We then generalize and study the Robinson-Schensted correspondence for such permutations.

• (with Ernesto Vallejo) Combinatorics and geometry of Littlewood-Richardson cones, Europ. J. Combinatorics, vol. 26 (2005), 995-1008.

We present several direct bijections between different combinatorial interpretations of the Littlewood–Richardson coefficients. The bijections are defined by explicit linear maps which have other applications.

• Hook Length Formula and Geometric Combinatorics, Séminaire Lotharingien de Combinatoire, vol. 46 (2001), article B46f, 13 pages.

We present a transparent proof of the classical hook length formula. The formula is reduced to an equality between the number of integer point in certain polytopes. The latter is established by an explicit continuous volume-preserving piecewise linear map.

• (with J-C Novelli, A.V. Stoyanovsky) A direct bijective proof of the hook-length formula, Discrete Mathematics and Theoretical Computer Science, vol. 1 (1997), 53-67.

We give a simple bijective proof of the hook-length formula.

You can also check the Third Edition of Don Knuth's The Art of Computer Programming (vol. 3, 1998), for a 2-page overview of the algorithm. Yet another 2-page overview is in Bruce Sagan's "Group Representations and Symmetric Functions", MSRI Lecture Notes, 1997 (available here) and the new edition of his monograph The Symmetric Group (which calls the bijection "beautiful", rightly or not).

If you want to play with the bijection, there is a Maple package for the algorithm written by Vince Vatter (to run it, you will need Doron Zeilberger's RSK package).

Note: The shifted analogue of the bijection is now known, and due to Ilse Fischer (in our paper we announced this possibility, but never wrote a paper since we could not figure out all the technical details). The increasing tree analogue by Bényi Beáta is much simpler and is proved in this paper.

Here is what Christian Krattenthaler writes in the Math. Reviews, 99h:05123:
"This is probably the most important recent contribution to bijective combinatorics."

Note: Curtis Greene gave the general audience explanation of the hook-length formula and its proof ideas: Part 1 and Part 2 of the Numberphile video.

This paper is an extended version of the note Short Bijective Proof of the Hook-length Formula, Funct. Anal. Appl., vol. 26, 1992, 216-218 (with A.V. Stoyanovsky.)

Download .pdf file of the note or .pdf file of the Russian original.

• (with Alex Postnikov) Oscillating Tableaux, (Sp x Sp)-modules, and Robinson-Schensted-Knuth correspondence, Proc. FPSAC'96 Conf., Minneapolis, MN.

We present a new approach to the RSK correspondence via oscillating tableaux. Generalization of RSK, continuous analog, and closed connection with (Sp x Sq)-modules are discussed.

• (with Alex Postnikov) Enumeration of trees and one amazing Representation of Sn, Proc. FPSAC'96 Conf., Minneapolis, MN.

We present several remarkable properties of the one representation of Sn, obtained by an action on parking functions. Of particular importance are multiplicities of the irreducible representations corresponding to hook shapes which correspond to certain k-trees.

• (with Alex Postnikov) Resolutions for Sn-modules Corresponding to Skew Hooks, and Combinatorial Applications, Funct. Anal. Appl., vol. 28 (1994), 132-134.

We construct a new resolution for a special type of Sn-modules. The resolution arises from inversion polynomial and generalizes a known combinatorial identity. In the limiting case we obtain new and classical partition identities.

Download .pdf file of the paper or .pdf file of the Russian original.

• (with Alexandre A. Kirillov) Covariants of the Symmetric Group and its analogues in Weil algebras, Funct. Anal. Appl., vol. 24 (1990), 172-176.

A classical hook-content formula appears as a Poincare series for the multiplicities of the irreducible Sn-module in symmetric algebra. We obtain a super-analog of this formula by taking Weil algebra instead of the symmetric algebra.

Download .pdf file of the paper or .pdf file of the Russian original.

Note: A combinatorial argument in the proof of the Lemma 3 is misleadingly simple and is a sketch at best. Algebraic proofs and generalizations were obtained in this paper by Thibon (1992), this paper by Molchanov (1992), and this paper by Koike (1994).

## Integer Partitions

• (with Stephen DeSalvo) Limit shapes via bijections, Combinatorics, Probability and Computing, vol. 28 (2019), no. 2, 187-240.

We compute the limit shape for several classes of restricted integer partitions, where the restrictions are placed on the part sizes rather than the multiplicities. Our approach utilizes certain classes of bijections which map limit shapes continuously in the plane. We start with bijections outlined in [Pak], and extend them to include limit shapes with different scaling functions.

See also slides of the talk (Saint Petersburg Combinatorics Seminar, March 17, 2021).

• (with Stephen DeSalvo) Log-concavity of the partition function, Ramanujan Journal, vol. 38 (2015), 61-73.

We prove that the partition function p(n) is log-concave for all n>25. We then extend the results to resolve two related conjectures by Chen and one by Sun. The proofs are based Lehmer's estimates on the remainders of the Hardy-Ramanujan and the Rademacher series for p(n).

Note: Conjecture 4.3 was proved by William Y.C. Chen, Larry X.W. Wang and Gary Y.B. Xie in this paper. Their bounds were further sharpened in this paper.
Sun's Conjecture discussed in §7.7 was proved by William Y.C. Chen and Ken Y. Zheng in this paper, by using the approach we suggested.

Acknowledgement of priority: After the paper was published, we learned that the central result of the paper has appeared earlier in the following interesting article. The proofs are different, but of the same flavor, although our version is more detailed and has other applications.
Jean-Louis Nicolas, Sur les entiers N pour lesquels il y a beaucoup de groupes abéliens d'ordre N (in French), Annales de l’institut Fourier, tome 28, no. 4 (1978), p. 1-16.

• (with Matjaž Konvalinka) Geometry and complexity of O'Hara's algorithm, Adv. Applied Math., vol. 42 (2009), no. 2, 157-175.

In this paper we analyze O'Hara's partition bijection. We present three type of results. First, we show that O'Hara's bijection can be viewed geometrically as a certain scissor congruence type result. Second, we obtain a number of new complexity bounds, proving that O'Hara's bijection is efficient in several special cases and mildly exponential in general. Finally, we prove that for identities with finite support, the map of the O'Hara's bijection can be computed in polynomial time, i.e. much more efficiently than by O'Hara's construction.

• (with Cilanne Boulet) A combinatorial proof of the Rogers-Ramanujan identities, Journal of Combinatorial Theory, Ser. A, vol. 113 (2006), 1019-1030.

We give a combinatorial proof of the Rogers-Ramanujan identities by using two symmetries of a new generalization of Dyson's rank. These symmetries are later established by direct bijections.

Note that the pictures are colored, so the paper is best read when printed on a color printer.

• The nature of partition bijections II. Asymptotic stability, preprint (2004), 32 pages, 19 pictures.

We introduce a notion of asymptotic stability for bijections between sets of partitions and a class of geometric bijections. We then show that a number of classical partition bijections are geometric and that geometric bijections under certain conditions are asymptotically stable.

Note that the pictures are colored, so the paper is best read when printed on a color printer.

• The nature of partition bijections I. Involutions, Advances Applied Math. vol. 33 (2004), 263-289.

We analyze involutions which prove several partition identities and describe them in a uniform fashion as projections of "natural" partition involutions along certain bijections. The involutions include those due to Franklin, Sylvester, Andrews, as well as few others. A new involution is constructed for an identity of Ramanujan, and analyzed in the same fashion.

• (with Christine Bessenrodt) Partition congruences by involutions, Europ. J. Combinatorics, vol. 25 (2004), 1139-1149, special issue in honor of Alain Lascoux.

We present a general construction of involutions on integer partitions which enable us to prove a number of modulo 2 partition congruences.

• Partition Bijections, a Survey, Ramanujan Journal, vol. 12 (2006), 5-75.

We present an extensive survey of bijective proofs of classical partitions identities. While most bijections are known, they are often presented in a different, sometimes unrecognizable way. Various extensions and generalizations are added in the form of exercises.

Errata: The following list was kindly compiled by Darij Grinberg. My apologies for all of these. Thanks, Darij!

Note: In the MathSciNet review of the article, George Andrews writes:

"This paper undertakes a monumental task: to present a reasonably coherent account of partition bijections. [...] This is a truly important contribution. The author's presentation is lucid, often clarifying or improving the original work and providing new insights."

Note: Several open problems in the article have been resolved:
2.6.3 by Byungchan Kim here.
2.7.6 by Ae Ja Yee here.
4.4.2 by Eduardo Stabel here. Another proof is by Bruce Berndt, Byungchan Kim and Ae Ja Yee here. Also, Jeremy Lovejoy suggests here that it follows from this paper.
5.2.7 by Christine Bessenrodt and IP here, and later by William Chen and Eric Liu here.
5.2.8 by IP here.
7.2.5 is one of the large family of identities proved bijectively by Sun Kim here,
8.2.5 is disproved by Matjaž Konvalinka and IP here.
8.4.5 is unresolved, but this lower bound was established for O'Hara's Algorithm (ibid.)
9.4.3 is unresolved, but see §5 in Sun Kim's
thesis.

• Partition Identities and Geometric Bijections, Proc. A.M.S., vol. 132 (2004), no. 12, 3457-3462.

We present a geometric framework for a class of partition identities. We show that there exists a unique bijection proving these identities, and satisfies certain linearity conditions. In particular, we show that Corteel's bijection enumerating partitions with nonnegative k-th differences can be obtained by our approach. Other examples and generalizations are presented.

• (with Alex Postnikov) A Generalization of Sylvester's Identity, Discrete Math., vol. 178 (1998), 277-281.

We present a new generalization of Euler's and Sylvester's identities for partitions. The proof is based on an explicit bijection.

## Order Theory

• (with Swee Hong Chan) Linear extensions of finite posets, preprint (2023), 55 pages.

We give a broad survey of inequalities for the number of linear extensions of finite posets. We review many examples, discuss open problems, and present recent results on the subject. We emphasize the bounds, the equality conditions of the inequalities, and the computational complexity aspects of the results.

• (with Swee Hong Chan and Greta Panova) On the cross-product conjecture for the number of linear extensions, preprint (2023), 24 pages.

We prove a weak version of the cross-product conjecture: F(k+1,) F(k,+1) ≥ (½+ε) 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.

• (with Swee Hong Chan) Multivariate correlation inequalities for P-partitions, Pacific Jour. Math., vol. 323 (2023), 223–252.

Motivated by the Lam–Pylyavskyy inequalities for Schur functions, we give a far reaching multivariate generalization of Fishburn's correlation inequality for the number of linear extensions of posets. We then give a multivariate generalization of the Daykin–Daykin–Paterson inequality proving log-concavity of the order polynomial of a poset. We also prove a multivariate P-partition version of the cross-product inequality by Brightwell–Felsner–Trotter. The proofs are based on a multivariate generalization of the Ahlswede–Daykin inequality.

See the journal version here.

• (with Swee Hong Chan) Correlation inequalities for linear extensions, preprint (2022), 23 pages.

We employ the combinatorial atlas technology to prove new correlation inequalities for the number of linear extensions of finite posets. These include the approximate independence of probabilities and expectations of values of random linear extensions, closely related to Stanley's inequality. We also give applications to the numbers of standard Young tableaux and to Euler numbers.

• (with Swee Hong Chan and Greta Panova) Effective poset inequalities, SIAM J. Discrete Math., vol. 37 (2023), 1842–1880.

We prove a number of new inequalities for the numbers of linear extensions and order polynomials of finite posets. First, we generalize the Björner–Wachs inequality to inequalities on order polynomials and their q-analogues via direct injections and FKG inequalities. We then establish several new inequalities on order polynomials, and prove the asymptotic version of Graham's conjecture. Second, we generalize actions of Coxeter groups on restricted linear extensions, leading to vanishing and uniqueness conditions for the generalized Stanley inequality. Third, we generalize the Sidorenko inequality to posets with small chain intersections and give complexity theoretic applications.

Acknowledgement of priority (Nov 8, 2022): After the paper was first posted here and on the arXiv, we discovered (largely by accident) that Graham's conjecture from 1983 (Conjecture 4.19 in our paper) was already established in Theorem 4 of D.E. Daykin, J.W. Daykin and M.S. Paterson, On log concavity for order-preserving maps of partial orders, Discrete Math., vol. 50 (1984), 221-226. The paper was updated in the revision. Note: The proof by [DDP84] is given by a direct injection, proving that this inequality is in #P. On the other hand, our proof (of the asymptotic version) is based on the FKG inequality, exactly as Graham asked. Note also that our Theorem 4.20 can be made stronger by taking account of the error term in Theorem 4.8. In summary: it's good to have multiple proofs.

Acknowledgement of priority (May 28, 2023): After the paper was accepted, we discovered that the vanishing conditions for the generalized Stanley inequality were given in Theorem 8.2 of D.E. Daykin and J.W. Daykin, Order preserving maps and linear extensions of a finite poset, SIAM J. Algebraic Discrete Methods, vol. 6 (1985), 738–748. While the authors did not include the full proof, the details can be found in J.W. Daykin's thesis (1984), §4.2.

Acknowledgement of priority (Aug 6, 2023): The log-concavity of the order polynomial (Theorem 1.3) is was proved by F. Brenti in his thesis and republished in the Memoirs AMS (Theorem 7.6.5 in both). This proof is via direct injection. Note: Our proof is via the FKG inequality and proves a stronger result (Theorem 4.8). See also Ferroni and Higashitani survey, §6.1, for this result in the context of the Ehrhart polynomials of order polytopes.

Note: Log-concavity of the order polynomial (Theorem 1.3) was generalized to the q-analogue and multivariate analogue in this paper, using the q and multivariate analogue of the AD inequality.

• (with Swee Hong Chan) Introduction to the combinatorial atlas, Expositiones Mathematicae, vol. 40 (2022), 1014–1048.

We give elementary self-contained proofs of the strong Mason conjecture recently proved by Anari et. al [ALOV] and Brändén–Huh [BH], and of the classical Alexandrov–Fenchel inequality. Both proofs use the combinatorial atilas technology recently introduced by the authors [CP]. We also give a formal relationship between combinatorial atlases and Lorentzian polynomials.

• (with Swee Hong Chan) Log-concave poset inequalities, preprint (2021), 71 pp.

We study combinatorial inequalities for various classes of set systems: matroids, polymatroids, poset antimatroids, and interval greedoids. We prove log-concavity inequalities for counting certain weighted feasible words, which generalize and extend several previous results establishing Mason conjectures for the numbers of independent sets of matroids. Notably, we prove matching equality conditions for both earlier inequalities and our extensions.

In contrast with much of the previous work, our proofs are combinatorial and employ nothing but linear algebra. We use the language formulation of greedoids which allows a linear algebraic setup, which in turn can be analyzed recursively. The underlying non-commutative nature of matrices associated with greedoids allows us to proceed beyond polymatroids and prove the equality conditions. As further application of our tools, we rederive both Stanley's inequality on the number of certain linear extensions, and its equality conditions, which we then also extend to the weighted case.

Download here the FPSAC 2022 extended abstract, which appeared in Sém. Lothar. Combin., 86B.9 (2022), 12 pp.

See video and slides of Swee Hong's UCLA in-person talk on the subject.

Alternatively, watch my CJCS talk (Nov 4, 2021), see video and slides,
or my Vinberg Lecture (May 4, 2022), see video and slides.

Note: Mason's conjectures are stated in his 1972 paper available here.
Stanley's inequality is proved in his 1981 paper available here.
Kung's 1995 article discussing Rota's point of view on Mason's inequalities is available here, and his letter is here.

• (with Swee Hong Chan and Greta Panova) Extensions of the Kahn–Saks inequality for posets of width two, Combinatorial Theory, vol. 3 (2023), no. 1, Paper No. 8, 34 pp.

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 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.

• (with Swee Hong Chan and Greta Panova) The cross-product conjecture for width two posets, Trans. AMS., vol. 375 (2022), 5923-5961.
published online here (June 10, 2022).

The cross-product conjecture (CPC) in [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, and the equality part of the CPC for posets of width two.

See video and sldes of my UC Davis talk on the subject.
See also Zoom video (Passcode: 9j6W7.66) of the Berkeley talk by Greta Panova.

• (with Swee Hong Chan and Greta Panova) Sorting probability of Catalan posets, Advances in Applied Mathematics, vol. 129 (2021), article 102221, 13 pp.
Published online here (May 10, 2021).

We show that the sorting probability of the Catalan poset Pn satisfies δ(Pn) = O(n–5/4).

• (with Swee Hong Chan and Greta Panova) Sorting probability for large Young diagrams, Discrete Analysis, Paper 2021:24, 57 pp.

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.

Read the journal introduction to the paper.

See video of Greta's Rutgers talk on the paper.
See also video and slides of Swee Hong's talk on the paper.

• (with Samuel Dittmer) Counting linear extensions of restricted posets, preprint (2018), 33 pages.

The classical 1991 result by Brightwell and Winkler [BW] states that the number of linear extensions of a poset is #P-complete. We extend this result to posets with certain restrictions. First, we prove that the number of linear extension for posets of height two is #P-complete. Furthermore, we prove that this holds for incidence posets of graphs. Finally, we prove that the number of linear extensions for posets of dimension two is #P-complete.

Important: This paper was split into two parts.
[height-two part]: Electron. J. Comb., vol. 27 (2020), No. 4, Research Paper P4.48, 13 pp.; see the journal version here.

## Graph Theory

• (with Nikita Gladkov) Positive dependence for colored percolation, preprint, 7 pp.

For uniform random 4-colorings of graph edges with colors a,b,c,d, every two colors form a ½–percolation, and every two overlapping pairs of colors form independent ½–percolations. We show joint positive dependence for pairs of colors ab, ac and ac, and joint negative dependence for pairs of colors ab, ac and bc. The proof is based on a generalization of the Harris–Kleitman inequalities. We apply the results to crossing probabilities for the colored bond and site percolation, and to colored critical percolation that we also define.

• (with Nishant Chandgotia and Martin Tassy) Kirszbraun-type theorems for graphs, Journal of Combinatorial Theory, Ser. B, vol. 137 (2019), 10-24.

The classical Kirszbraun theorem says that all 1-Lipschitz functions f: ARn, ARn, with the Euclidean metric have a 1-Lipschitz extension to Rn. For metric spaces X and Y, we say that Y is X-Kirszbraun if all 1-Lipschitz functions f: A→Y, AX, have a 1-Lipschitz extension to X. We analyze the case when X and Y are graphs with the usual path metric. We prove that Zd-Kirszbraun graphs are exactly graphs that satisfy a certain Helly property. We also consider complexity aspects of these properties.

• (with Sergei Chmutov) The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial of ribbon graphs, Moscow Mathematical Journal, vol. 7 (2007), no. 3, 409-418, 573 (special volume dedicated to A. Khovanskii).

We show that the Kauffman bracket [L] of a checkerboard colorable virtual link L is an evaluation of the Bollobás-Riordan polynomial RG of a ribbon graph G = GL associated with L. This result generalizes the celebrated relation between the Kauffman bracket and the Tutte polynomial of planar graphs.

Note: This was the first paper relating BR-polynomial and link invariants. Many generalizations and variations were introduced in subsequent years, resolving our open problems. E.g., Sergei Chmutov works with signed graphs here.

• (with Mike Korn) Combinatorial evaluations of the Tutte polynomial, preprint (2003), 24 pages.

We give a number of new combinatorial interpretations of values of the Tutte polynomial of planar graphs, in terms of two different graph colorings, claw coverings, and, for particular graphs on a square grid, in terms of Wang tilings and T-tetromino tilings. These results are extended to surfaces of higher genus and give interpretations of the Bollobás-Riordan polynomial. Most proofs are bijective.

• (with Alexander Kelmans and Alex Postnikov) Tree and forest volumes of graphs, DIMACS Technical Report, No. 2000-03 (January 2000), 33 pages.

We present a number of results enumerating spanning trees and spanning forests in multipartite graphs and more general graphs with part structure. This is an advanced extension of [Pak-Postnikov] and [Kelmans].

• (with Alex Postnikov) Enumeration of spanning trees in some graphs, Russian Math. Surveys, vol. 45 (1990), 220-221.

We give a new formula for the number of spanning trees in graphs with partition structure (e.g. multipartite graphs).

Download .pdf file of the note or .pdf file of the Russian original.

## Contingency Tables

• (with Hanbaek Lyu) On the number of contingency tables and the independence heuristic, Bull. London Math. Soc., vol. 54 (2022), 242–255.

We obtain sharp asymptotic estimates on the number of n x n contingency tables with two linear margins Cn and BCn. The results imply a second order phase transition on the number of such contingency tables, with a critical value at Bc:=1 + (1+1/C)1/2. As a consequence, for B>Bc, we prove that the classical independence heuristic leads to a large undercounting.

Alternatively, see Han's (much nicer) talk slides.

• (with Petter Brändén and Jonathan Leake) Lower bounds for contingency tables via Lorentzian polynomials, Israel Journal of Math., vol. 253 (2023), 43–90.
published online October 20, 2022, see here.

We present a new lower bound on the number of contingency tables, improving upon and extending previous lower bounds by Barvinok [Bar09, Bar16] and Gurvits [Gur15]. As an application, we obtain new lower bounds on the volumes of flow and transportation polytopes. Our proofs are based on recent results on Lorentzian polynomials.

• (with Sam Dittmer and Hanbaek Lyu) Phase transition in random contingency tables with non-uniform margins, Trans. AMS, vol. 373 (2020), 8313–8338.

For parameters n,δ,B, and C, let X=(Xkℓ) be the random uniform contingency table whose first ⌊nδ⌋ rows and columns have margin ⌊BCn⌋ and the last n rows and columns have margin ⌊Cn⌋. For every 0<δ<1, we establish a sharp phase transition of the limiting distribution of each entries of X at the critical value Bc=1+ (1+1/C)1/2. In particular, for 1/2<δ<1, we show that the distribution of each entry converges to a geometric distribution in total variation distance, whose mean depends sensitively on whether B < Bc or B > Bc. Our main result shows that E[X11] is uniformly bounded for B < Bc, but has sharp asymptotic C(B-Bc)n1-δ for B > Bc. We also establish a strong law of large numbers for the row sums in top right and top left blocks.

Note: This and the arXiv version have an appendix absent in both the published and the first arXiv versions.

## Random Walks

• (with Swee Hong Chan and Greta Panova) Log-concavity in planar random walks, Combinatorica, vol. 42 (2022), suppl. 1, 1011–1026.
published online September 21, 2022.

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

See video and slides of the Banff talk on the subject.

Note: The MathSciNet review for the article ends with: "The proof techniques used in this article are riveting."

• (with Igor Gorodezky) Generalized loop-erased random walks and approximate reachability, Random Structures & Algorithms, vol. 44 (2014), 201–223.

In this paper we extend the loop-erased random walk (LERW) to the directed hypergraph setting. We then generalize Wilson's algorithm for uniform sampling of spanning trees to directed hypergraphs. In several special cases, this algorithm perfectly samples spanning hypertrees in expected polynomial time.

Our main application is to the reachability problem, also known as the directed all-terminal network reliability problem. This classical problem is known to be #P-complete, hence is most likely intractable. We show that in the case of bi-directed graphs, a conjectured polynomial bound for the expected running time of the generalized Wilson's algorithm implies a FPRAS for approximating reachability.

Note: Conjecture 7.1 is proved by Heng Guo and Mark Jerrum in this paper.

• (with Sergiy Sidenko) Convergence of Kac's Random Walk, preprint (2007), 12 pages.

We study a long standing open problem on the mixing time of Kac's random walk on SO(n,R) by random rotations. We obtain an upper bound mix = O(n2.5 log n) for the weak convergence which is close to the trivial lower bound Ω(n2). This improves the upper bound O(n4 log n) by Diaconis and Saloff-Coste. The proof is a variation on the coupling technique we develop to bound the mixing time for compact Markov chains, which is of independent interest.

Note: A sharp upper bound was obtained in this paper by Roberto Oliveira.

• Mixing time and long paths in graphs, in Proc. SODA'02 (San Francisco, CA), 321-328.

We prove that regular graphs with large degree and small mixing time contain long paths and other graphs. We apply the results to size Ramsey numbers, self-avoiding walks in graphs, and present efficient algorithm for finding long paths in graphs as above.

Note: Conjecture 1 was partially proved by Jair Donadelli, Penny Haxell and Yoshiharu Kohayakawa in this paper.
After some more work in this direction, it was completely resolved by Nemanja Draganić, Michael Krivelevich and Rajko Nenadov in this paper.
Better bounds on Birthday Paradox for Markov chains are given here.

• (with A. Żuk) On Kazhdan Constants and Mixing of Random Walks, International Mathematical Research Notes, 2002, No. 36, 1891-1905.

Let G be a group with Kazhdan's property (T), and let S be a transitive generating set (there exists a subgroup H of Aut(G) which acts transitively on S.) In this paper we relate two definitions of the Kazhdan constant and the eigenvalue gap in this case. Applications to various random walks on groups, and the product replacement random algorithm, are also presented.

Note: Sharper bounds on Kazhdan constants and mixing times of matrix random walks, were later obtained by Martin Kassabov in this paper.

• (with Alex Astashkevich) Random walks on nilpotent groups, preprint (2001), 14 pages.

We obtain sharp bounds on mixing time of random walks on nilpotent groups, with Hall bases as generating sets.

• (with Nathan Lulov) Rapidly mixing random walks and bounds on characters of the symmetric group, Journal of Algebraic Combinatorics, vol. 16 (2002), 151-163.

We investigate mixing of random walks on Sn and An generated by permutations of a given cycle structure. In our approach we follow methods developed by Diaconis, by using characters of the symmetric group and combinatorics of Young tableaux. We conclude with conjectures and open problems.

Note: Conjecture 4.1 and a variation on Conjecture 4.3 was proved by Michael Larsen and Aner Shalev in this paper.

• (with Don Coppersmith) Random walk on upper triangular matrices mixes rapidly, Probability Theory and Related Fields, vol. 117 (2000), 407-417.

We present an upper bound O(n2) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process.

Note: Our bounds apply when the size of the field q> Cn2. When q fixed, a similar upper bound was obtained by Yuval Peres and Allan Sly in this paper. When q is in the intermediate range there is still a gap between the upper and lower bounds.

• (with Feng Chen, László Lovász) Lifting Markov Chains to Speed up Mixing, Proc. STOC'99, 275-281.

There are several examples where the mixing time of a Markov chain can be reduced substantially, often to about its square root, by ``lifting'', i.e., by splitting each state into several states. In several examples of random walks on groups, the lifted chain not only mixes better, but is easier to analyze.

We characterize the best mixing time achievable through lifting in terms of multicommodity flows. We show that the reduction to square root is best possible. If the lifted chain is time-reversible, then the gain is smaller, at most a factor of log (1/p), where p is the smallest stationary probability of any state. We give an example showing that a gain of a factor of log (1/p) log log (1/p) is possible.

• Using stopping times to bound mixing times, in Proc. SODA'99, 953-954.

We present a strong uniform time approach which to prove bounds on mixing time of random walk on groups. Various examples are given. Speeding up the walks is also discussed.

• Two random walks on upper triangular matrices, Journal of Theoretical Probability, vol. 13 (2000), 1083-1100.

We study two random walks on a group of upper triangular matrices. In each case, we give upper bound on the mixing time by using a stopping time technique.

• Random walks on finite groups with few random generators, Electronic Jour. Probability, vol. 4 (1999), 1-11.

Let G be a finite group. Consider random walks on G generated by a randomly chosen set of generators of size k. We show that when k=O(log|G|) the mixing time mix=O(log|G|) with high probability.

A stronger version of this result was presented at the European Symposium on Algorithms (ESA'99) and was published in
Random Cayley graphs with O(log|G|) generators are expanders, Lecture Notes in Computer Science, vol. 1643, Springer, 1999, 521-526; link here.

• (with Van H. Vu) On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes, Discrete Applied Math., vol. 110 (2001), 251-272.

Consider a random walk on a vector space with steps defined by a given set of vectors. We show that in some cases the mixing time can be defined in purely combinatorial terms. We also investigate cutoff phenomenon for these walks.

An extended abstract of the paper has appeared in Proc. FPSAC'99 Conference, 417-428. Download .pdf file of the extended abstract.

Note: The open problem in §13.5 was completely resolved by Michael Krivelevich, Benjamin Sudakov and Van Vu in this paper.

• Random Walks on Groups: Strong Uniform Time Approach, Ph.D. Thesis, Harvard University, 1997, 120 pages.

We show that one can successfully employ stopping times to get sharp bounds on mixing times for a wide range of examples of walks on permutation and linear groups. The first half of the thesis dedicated to a general theory of stopping times.

Note: For the great progress on conjectures 2.7.2 and 2.7.9, see this survey by Harald Helfgott.

## Combinatorics and Probability on Finite Groups

• (with Greta Panova and Damir Yeliussizov) Bounds on the largest Kronecker and induced multiplicities of finite groups, Communications in Algebra, vol. 47 (2019), no. 8, 3264-3279.

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.

• (with Andrew Soffer) On Higman's k(Un(Fq)) conjecture, preprint (2015).

A classical conjecture by Graham Higman states that the number of conjugacy classes of Un(Fq), the group of upper triangular n×n matrices over Fq, is polynomial in q, for all n. In this paper we present both positive and negative evidence, verifying the conjecture for n≤16, and suggesting that it probably fails for n≥59. The tools are both theoretical and computational. We introduce a new framework for testing Higman's conjecture, which involves recurrence relations for the number of conjugacy classed of pattern groups. These relations are proved by the orbit method for finite nilpotent groups. Other applications are also discussed.

• (with Rados Radoičić) Hamiltonian paths in Cayley graphs, Discrete Math., vol. 309 (2009), 5501-5508 ("Hamiltonicity Problem for Vertex-Transitive Graphs" special issue); includes a literature review and refs to 60 papers.

The classical Lovász conjecture says that every connected Cayley graph is Hamiltonian. We present a short survey of various results in that direction and make some additional observations. In particular, we prove that every finite group G has a generating set of size at most log2 |G|, such that the corresponding Cayley graph contains a Hamiltonian cycle. We also present an explicit construction of 3-regular Hamiltonian expanders.

Note: Lovász's conjecture remains open with progress unlikely. Conjecture 1 remains open, but the Krivelevich-Sudakov (log |G|)5 bound on the number of generators was reduced to (log |G|)3 in this paper by Demetres Christofides and Klas Markström.

• (with Christopher Malon) Percolation on finite Cayley graphs, Combinatorics, Probability and Computing, vol. 15 (2006), 571-588.
Extended abstract of the earlier version of the paper has appeared in Proc. RANDOM'02.

In this paper, we study percolation on finite Cayley graphs. A conjecture of Benjamini says that the critical percolation pc of such a graph can be bounded away from one, for any Cayley graph satisfying a certain diameter condition. We prove Benjamini's conjecture for some special classes of groups. We also establish a reduction theorem, which allows us to build Cayley graphs for large groups without increasing pc.

Warning: Please do not use/refer to the RANDOM extended abstract as the the results and proofs in the final version significantly differ.

Note: Benjamini's conjecture is largely resolved by Tom Hutchcroft and Matthew Tointon in this paper. I was wrong to disbelieve it.

• (with Robert Guralnick) On a question of B.H. Neumann, Proc. A.M.S., vol. 131 (2003), 2021-2025.

The automorphism group of a free group Aut(Fk) acts on the set of generating k-tuples (g1,...,gk) of a group G. Higman showed that when k=2, the union of conjugacy classes of commutators [g1,g2] and [g1,g2]-1 is an orbit invariant. We give a negative answer to a question of B.H. Neumann, as to whether there is a generalization of Higman's result for k > 2.

Note: The conjecture in Remark 1.4 was resolved by Shelly Garion and Aner Shalev in this paper. A quantified version suggested in the same remark was obtained in this preprint.

• On probability of generating a finite group, preprint, 1999; later largely included into "What do we know..." survey article.

Let G be a finite group, and let p(G,k) be the probability that k random group elements generate G. Denote by v(G) the smallest k such that p(G,k)>1/e. In this paper we analyze the quantity v(G) for different classes of groups. We prove that v(G)< r(G)+1 when G is nilpotent, and r(G) is the minimal number of generators of G. When G is solvable we show that v(G) < 3.25 r(G) + 107. We also show that v(G) < C log log |G|, where G is a direct product of simple nonabelian groups and C is a universal constant. Applications to the "product replacement algorithm" are also discussed.

Note: Conjecture 1.6 was proved by Alexander Lubotzky in this paper.

## Growth and Probability on Infinite Groups

• (with David Soukup) Algebraic and arithmetic properties of the cogrowth sequence of nilpotent groups, preprint (2022), 20 pp.

We prove that congruences of the cogrowth sequence in a unitriangular group UT(m, Z) are undecidable. This is in contrast with abelian groups, where the congruences of the cogrowth sequence are decidable. As an application, we conclude that there is no algorithm to present the cogrowth series as the diagonal of a rational function.

Note: The matrix size we need for the proof m≈1086 is about 10,000 times the number of atoms in the observable universe.

• (with Anton Malyshev) Lifts, derandomization, and diameters of Schreier graphs of Mealy automata, Combinatorica, vol. 37 (2017), 733-765.

It is known that random 2-lifts of graphs give rise to expander graphs. We present a new conjectured derandomization of this construction based on certain Mealy automata. We verify that these graphs have polylogarithmic diameter, and present a class of automata for which the same is true. However, we also show that some automata in this class do not give rise to expander graphs.

From a kind Math. Review by Jeffrey Shallit: "The techniques involve an ingenious combination of algebraic, combinatorial, and automata-theoretic methods."

Note: Conjecture 1.2, 1.3 and Problem 11.4 remain wide open as our bounds have not been improved. However, in this paper Michael B. Cohen completed the approach of [MSS] to obtain explicit (i.e. poly-time) constructions of Ramanujan (multi-) graphs via 2-lifts, see §11.10 of the paper.

• (with Anton Malyshev) Growth in product replacement graphs, Journal of Group Theory, vol. 18 (2015), 209-234.

We prove the exponential growth of product replacement graphs for a large class of groups. Much of our effort is dedicated to the study of product replacement graphs of Grigorchuk groups, where the problem is most difficult.

• (with Martin Kassabov) Groups of Oscillating Intermediate Growth, Ann. Math., vol. 177 (2013), 1113-1145.

We construct an uncountable family of finitely generated groups of intermediate growth, with growth functions of new type. These functions can have large oscillations between lower and upper bounds, both of which come from a wide class of functions. In particular, we can have growth oscillating between exp(nα) and any prescribed function, growing as rapidly as desired. Our construction is built on top of any of the Grigorchuk groups of intermediate growth, and is a variation on the limit of permutational wreath product.

• (with Rostislav Grigorchuk) Groups of Intermediate Growth: an Introduction, L’Enseignement Mathématique, vol. 54 (2008), no. 3-4, 251-272.

We present an accessible introduction to basic results on groups of intermediate growth. The idea is to separate the (straightforward) analytic calculations and group theoretic arguments. We neither survey the field nor do we obtain the best known bounds for the growth. Instead, we concentrate on making the exposition as elementary and self-contained as possible.

Note: Conjecture 12.1 was resolved by Anna Erschler and Tianyi Zheng (see comment below). Earlier, a lot of progress has been made constructing other groups of intermediate growth, see Rostislav Grigorchuk's survey.

• (with Tatiana Smirnova-Nagnibeda) Uniqueness of percolation on nonamenable Cayley graphs, Comptes Rendus Acad. Sci. Paris, Ser. I Math., vol. 330 (2000), no. 6, 495-500.

For every nonamenable group, a finite system of generators is constructed such that the Bernoulli bond percolation on the corresponding Cayley graph exhibits the double phase transition phenomenon, i.e., nonempty nonuniqueness phase.

• (with Roman Muchnik) On growth of Grigorchuk groups, International Journal of Algebra and Computation, vol. 11 (2001), 1-17.

We present an analytic technique for estimating the growth for groups of intermediate growth. We apply our technique to Grigorchuk groups, which are the only known examples of such groups. Our estimates generalize and improve various bounds by Grigorchuk, Bartholdi and others.

Note: Recent paper by Anna Erschler and Tianyi Zheng proved a lower bound matching our upper bound, thus resolving the problem.

• (with Roman Muchnik) Percolation on Grigorchuk groups, Comm. Algebra, vol. 29 (2001), 661-671.

Let pc(G) be the critical probability of the site percolation on the Cayley graph of group G. Benjamini and Schramm conjectured that pc<1, given the group is infinite and not a finite extension of Z. The conjecture was proved earlier for groups of polynomial and exponential growth and remains open for groups of intermediate growth. In this note we prove the conjecture for a special class of Grigorchuk groups, which contains all known examples of groups of intermediate growth.

Note: The Benjamini-Schramm Conjecture was completely resolved by Hugo Duminil-Copin, Subhajit Goswami, Aran Raoufi, Franco Severo, and Ariel Yadin in this paper.

## The Product Replacement Algorithm

• (with Alex Gamburd) Expansion of product replacement graphs, Combinatorica, vol. 26 (2006), 411-429.

We establish a connection between the expansion coefficient of the product replacement graph of a group G, and the minimal expansion coefficient of a Cayley graph of G. This gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders.

The extended abstract of the paper has appeared in the Proc. SODA'2002. Download .pdf file of the extended abstract. Note that the proceedings version does not contain the Appendix.

Note: The assumption used in Corollary 2 has been (mostly) established by Emmanuel Breuillard and Alex Gamburd in this paper.

• The product replacement algorithm is polynomial, Proc. FOCS'2000, 476-485.

The main result of this paper is a polynomial upper bound for the cost of the algorithm, provided k is large enough. This is the first such result, improving (sub)-exponential bounds by Diaconis and Saloff-Coste, etc.

• (with Alex Lubotzky) The product replacement algorithm and Kazhdan's property (T), Journal of AMS, vol. 14 (2001), 347-363.

The ``product replacement algorithm'' is a commonly used heuristic to generate random group elements in a finite group G, by running a random walk on generating k-tuples of G. While experiments showed outstanding performance, the theoretical explanation remained mysterious. In this paper we propose a new approach to study of the algorithm, by using Kazhdan's property (T) from representation theory of Lie groups.

Note: Open Problem 3.2 has been completely resolved. First, Marek Kaluba, Piotr Nowak and Narutaka Ozawa proved here that Aut(F5) has Kazhdan's property (T). Then, Marek Kaluba, Dawid Kielak and Piotr Nowak proved the same for all Aut(Fk), k≥6 in this paper. Open Problem 3.7 remains unresolved for k≥3.

• (with Gene Cooperman) The product replacement graph on generating triples of permutations, preprint, 2000.

We prove that the product replacement graph on generating 3-tuples of An is connected for n < 12. We employ an efficient heuristic based on the ``large connected component'' concept and use of symmetry to prune the search. The heuristic works for any group. Our tests were confined to An due to the interest in Wiegold's Conjecture, usually stated in terms of T-systems. Our results confirm Wiegold's Conjecture in some special cases and are related to the recent conjecture of Diaconis and Graham. The work was motivated by the study of the product replacement algorithm.

• What do we know about the product replacement algorithm?, Groups and Computation III (W. Kantor, A. Seress, eds.), de Gruyter, Berlin, 2001, 301-347.

We give an extensive review of the theoretical results related to the product replacement algorithm. Both positive and negative results are described. The review is based on a large amount of work done by the author, including joint results with Babai, Bratus, Cooperman, Lubotzky and Zuk (see on this web page).

Note: Much progress has been made:
Open Problem 1.3.5 was resolved by Eleonora Crestani and Andrea Lucchini in this paper,
Conjecture 1.5.3 was proved by Alexander Lubotzky in this paper,
Question 2.3.4 was resolved by Robert Guralnick and IP in this paper,
Conjecture 2.5.9 follows from the proof of Theorem 2.5.10 and Theorem 10 in Martin Liebeck's survey (the theorem is the result in this paper),
Remark 3.2.5 claims a result which never materialized, unfortunately,
Open Problem 3.5.2 has been resolved by Marek Kaluba et al., see the link and the comment above.
Remark 3.5.3 suggest expanders of An. Before Open Problem 3.5.2 has been resolved, an alternative construction was given by Martin Kassabov here.

• (with László Babai) Strong bias of group generators: an obstacle to the ''product replacement algorithm'', Journal of Algorithms, vol. 50 (2004), 215-231 (special SODA'2000 issue). An extended abstract of this paper has appeared in Proc. SODA'00, 627-635.

Let G be a finite group. Efficient generation of nearly uniformly distributed random elements in G, starting from a given set of generators of G, is a central problem in computational group theory. In this paper we demonstrate a weakness in the popular ''product replacement algorithm,'' widely used for this purpose. Roughly, we show that components of the uniform generating k-tuples have a bias in the distribution, detectable by a short straight-line program.

• On the graph of generating sets of a simple group, preprint, 1999; later largely incorporated into "What do we know..." survey.

We prove that the product replacement graph on generating k-tuples of a simple group contains a large connected component. This is related to the recent conjecture of Diaconis and Graham. As an application, we also prove that the output of the product replacement algorithm in this case does not have a strong bias.

• (with Sergey Bratus) On sampling generating sets of finite groups and product replacement algorithm, in ISSAC'99 Conference Proceedings, 91-96.

This is an extended abstract of the two separate papers on the generating k-subsets of a finite group. We elaborate on the number of such subsets and present an efficient and very economic algorithm in case of nilpotent groups. We also prove rapid mixing of the product replacement algorithm in case when group is abelian.

## Other Group Algorithms

• Testing commutativity of a group and the power of randomization, LMS Journal of Computation and Mathematics, vol. 15 (2012), 38-43.

Let G be a group generated by k elements, with group operations (multiplication, inversion, comparison with identity) performed by a black box. We prove that one can test whether G is abelian at a cost of O(k) group operations. On the other hand, we show that deterministic approach requires Ω(k2) group operations.

This paper first appeared as a Yale preprint in 2000. It was revised and updated in 2011 prior to submission.
See here for a journal version.

• (with Sergey Bratus) On sampling generating sets of finite groups, preprint, 1999; later largely incorporated into the ISSAC article.

Let G be a finite group. For a given k, what is the probability that a group is generated by k random group element? How small can be this probability and how one can uniformly sample these generating k-tuples of elements? In this paper we answer these questions for nilpotent and solvable groups. Applications to product replacement algorithms and random random walks are discussed.

• (with Sergey Bratus) Fast constructive recognition of a black box group isomorphic to Sn using Goldbach conjecture, Journal of Symbolic Computation, vol. 29 (2000), 33-57.

We present a Las Vegas algorithm for verification whether a given group defined as a black box group (we can multiply elements, take inverses, and compare them with identity) is isomorphic to a given symmetric group. Surprisingly, the algorithm relies on the Goldbach conjecture and its various extensions. In the appendix to the article we use analytic number theory and probabilistic approach to support the conjectures.

Note: Ternary Goldbach conjecture was proved in this paper by Harald Helfgott.

• When and how n choose k, AMS DIMACS series, vol. 43 (1998), 191-238.

We present several combinatorial and probabilistic algorithms for generating random k-subsets of n-sets, k-subspaces of a n-dimensional space over the finite field, random nonsingular matrices, etc.

Check out a review by M. Fulmeck in Math. Reviews.

## Popular mathematical writings

• Book review of E. Brown and R.K. Guy, The Unity of Combinatorics, AMS/MAA, 2020, 353 pp.
This review appeared in the Notices of the AMS, vol. 69 (Jan 2022), 108-111.

• Toufik Mansour, Interview with Igor Pak, Enumerative Combinatorics and Applications, vol. 1 (2021), Interview #S3I11, 11 pp.

See errata in my answers in this blog post.

• (with Fëdor Petrov and Viacheslav Sokolov) Hook inequalities, Math. Intelligencer, vol. 42 (2020), no. 2, 1–8.

We give an elementary proof of the recent hook inequality given in [MPP]: ∏u∈λ h(u) ≤ ∏u∈λ h(u), where h(u) is the usual hook in Young diagram λ, and h(i,j) := i+j-1. We then obtain a large variety of similar inequalities and their high-dimensional generalizations.

See also video of the talk by F. Petrov in part based on the paper.

• (with Alejandro Morales and Greta Panova) Why is π < 2ϕ?, Amer. Math. Monthly, vol. 125 (2018), no. 8, 715-723.

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.

Download .pdf file of the paper. Here is a short blog post on the paper.
Download .pdf file of the published version of the paper (different title, other minor changes, not all for the better).
Warning: The picture on the front page looks best when printed in color.

Note: Sidorenko's inequality was proved via an explicit surjection in this paper by Christian Gaetz and Yibo Gao. An explicit injection was later found in this paper by Christian Gaetz and Yibo Gao, and independently in this paper by Swee Hong Chan, Igor Pak and Greta Panova.

• History of Catalan numbers, an appendix to Richard Stanley, Catalan Numbers, Cambridge Univ. Press, 2015, 177-189.

We give a brief history of Catalan numbers, from their first discovery in the 18th century to modern times.

From Tina Garrett's review of the book:
[..] the appendices contain a must-read history of the Catalan numbers by Igor Pak. In particular, Pak’s description of the early years of Catalan research, from Euler’s communication with Segner to the 19th century work of several French mathematicians, takes the reader on a journey of discovery.
Igor Pak’s contribution,
History of Catalan Numbers is a delightful look at the emergence of this fascinating sequence in the historical literature and will be of interest to those who think deeply about how mathematical discovery emerges.

See my Catalan Numbers website with historical documents and other links.
See also my blog posts on which this paper was based: one and two.

• (with Rom Pinchasi) Collapsing walls theorem, Amer. Math. Monthly, vol. 119 (2012), 156–160.

Let P be a pyramid with the base a convex polygon Q. We show that when all other faces of P are collapsed (rotated around the edges onto the plane spanned by Q), they cover the whole Q.

Notes:
1. Another (much nicer) proof was given by Arseniy Akopyan in this paper.
2. This problem then found its way into the Finals of the Russian Math. Olympiad in 2012, where apparently nobody solved it. Still, it was awarded a Prize for the Best Problem (as voted by the students). See this site for problems and solutions (2005-present), this link for my problem 11.4, and this link for two solutions, both of which are simpler and better than ours.
3. In a final (somewhat bizarre) twist of fate, the ingenuous solution by Ilya Bogdanov (the first of the two solutions above), became a cartoon, published on the back cover by the Kvantik magazine for pre-teens with math interests (July 2019). The Kvantik solution-by-picture for the problem is available here.

• Inflating the cube without stretching, Amer. Math. Monthly, vol. 115 (2008), no. 5, 443-445.

We give a simple proof of the following result: There exists a non-convex polyhedron whose surface is isometric to the surface of a cube of smaller volume.

• On Fine's partition theorems, Dyson, Andrews, and missed opportunities, Math. Intelligencer, vol. 25 (2003), 10-16.

We present combinatorial proofs of several Fine's partition theorems, along with some historical account.

Download here the journal version of the paper (note the bio sketch at the end).

A preliminary version of this paper was translated and published in Matematicheskoe Prosveschenie, vol. 7 (2003), 136-149 (in Russian). This is an annual publication of MCCME.

Note: The involutive proof of Fine's identity suggested in the Final Remarks is resolved by Christine Bessenrodt and IP in this paper.
A different proof was later given by William Y.C. Chen and Eric H. Liu in this paper.

## Professional development

• How to tell a good mathematical story, Notices of the AMS, vol. 68 (2021), 925-928.

The article tackles an old problem "What should one write in the paper?” By that I mean what to include, what not, what to emphasize, in what order, etc. To resolve these questions one starts by figuring out how to tell a good story about your results.

the published version with my picture.

• How to write a clear math paper: Some 21st century tips, Journal of Humanistic Mathematics, vol. 8 (2018), 301-328.

In this article we explain the importance of clarity and give other tips for mathematical writing.