# Research Papers

I have papers on the following (overlapping) subjects:

## Integer Points in Polytopes

• (with Philipp Hieronymi and Danny Nguyen) Presburger Arithmetic with algebraic scalar multiplications, preprint (2018), 33 pages.

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.

Download .pdf file of the paper. Note: This version is substantially revised over the first version in the arXiv.

• (with Danny Nguyen) On the number of integer points in translated and expanded polyhedra, Discrete & Computational Geometry, published online Feb. 7, 2020, 20 pages.

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.

• (with Danny Nguyen) Short Presburger arithmetic is hard, SIAM Journal on Computing, STOC 2017 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.

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 simplex method works, how fast 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, preprint (2020), 20 pages.

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.

• (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 ε.

• (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 and Schramm.

Download .pdf file of the Russian translation, or go to the journal web site.

• 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 Ch. 4 of his thesis with a similar but more streamlined and conceptual argument. In R3, the continuous blooming conjecture 9.12 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], "Ribbon tile invariants" (see below), 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 the "Ribbon tile invariants" 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. A.M.S., 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.

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

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

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

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 page for the paper.
Warning: the file is 1.8Mb.

• (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 β-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 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.

• (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

• Skew shape asymptotics, a case-based introduction, preprint (2020), 19 pages.

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. Mathematique, 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: 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.

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.

• (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, preprint (2018), 21 pages.

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.

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

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

## Algebraic Combinatorics and Young tableaux

• (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,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!

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.

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.

• (with Greta Panova) Strict unimodality of q-binomial coefficients, Comptes Rendus Acad. Sci. Paris, Ser. I. Mathematique, 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).

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

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.

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

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

In the MathSciNet review, 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."

Download .pdf file of the paper and .pdf file of the MathSciNet review.
Warning: Printing on a monochromatic printer may distort some colored pictures.

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; Jeremy Lovejoy suggests here that it also follows from this paper,
5.2.7 by Christine Bessenrodt and IP 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 and Greta Panova) Sorting probability of Catalan posets, preprint (2020), 10 pages.

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, preprint (2020), 38 pages.

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.

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

## Graph Theory

• (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 satisfies 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, preprint (2020), 10 pages.

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.

• (with Petter Brändén and Jonathan Leake) Lower bounds for contingency tables via Lorentzian polynomials, preprint (2020), 28 pages.

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, preprint (2019), 24 pages; to appear in Trans. AMS;
Published online here.

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.

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

## Random Walks

• (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 proved by Jair Donadelli, Penny Haxell and Yoshiharu Kohayakawa 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 remains open. We continue 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 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.

## 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, or another review by A. Hulpke in Zbl. Math..

## Popular mathematical writings

• Combinatorial inequalities, the first "Short Stories" column, 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).

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

• (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.
Warning: The picture on the front page looks best when printed in color.

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

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

## Professional development

• How to Write a Clear Math Paper: Some 21st Century Tips, Journal of Humanistic Mathematics, vol. 8 (2018), 301-328.

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