I have papers on the following (overlapping) subjects:
Click here to return to Igor Pak Home Page.
The Stanley–Yan (SY) inequality gives the ultra-log-concavity for the numbers of bases of a matroid which have given sizes of intersections with k fixed disjoint sets. The inequality was proved by Stanley (1981) for regular matroids, and by Yan (2023) in full generality. In the original paper, Stanley asked for equality conditions of the SY inequality, and proved total equality conditions for regular matroids in the case k=0.
In this paper, we completely resolve Stanley's problem. First, we obtain an explicit description of the equality cases of the SY inequality for k=0, extending Stanley's results to general matroids and removing "total equality'' assumption. Second, for k≥1, we prove that the equality cases of the SY inequality cannot be described in a sense that they are not in the polynomial hierarchy unless the polynomial hierarchy collapses to a finite level.
Download .pdf file of the paper.
See video
and slides of Swee Hong's talk
about the paper, IAS (October, 2024).
The extended abstract is published in Proc. 56th STOC (2024), 875–883.
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.
Download .pdf file of the paper.
Journal version is available here.
The extended abstract in STOC'24
is available here.
See my MFO talk about the paper (video only, Jan. 23, 2024).
See Swee Hong's talk at IPAM, and his slides.
See my talk at
Stanley's conference,
(video and slides, June 4, 2024).
See also Swee Hong's pre-recorded STOC talk video,
and slides (June 26, 2024).
Additionally, read my blog post about the paper, and Gil Kalai's blog post about this and related work.
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.
Download .pdf file of the paper.
See journal version here (published online August 8, 2024).
See also my blog post and
slides of my GSCC'24 talk.
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.
Download .pdf file of the paper.
See this and other papers at the conference proceedings website:
Open Problems in Algebraic Combinatorics.
Download .pdf of the final version (updated, many typos fixed, but style and formatting issues).
See also my talk at Open Problems in Algebraic Combinatorics Conference
(Minneapolis, May 18, 2022), talk video and
slides.
See also this tweet review the talk.
Notes: Combinatorial interpretations are characterized by #P
complexity class.
Conjecture 5.5 and a weaker Conjecture 5.6 we disproved by Gladkov, IP and Zimin in
this paper.
While Conjecture 6.3 remains open, a version
of it was proved by Chan and IP in this paper.
Open Problem 7.9 was resolved in the negative by Soskin and IP (in preparation).
While Conjecture 10.1
remains open, this and
that papers (joint with Robichaux)
provide some negative evidence.
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.
Download .pdf file of the paper.
See video and slides1, slides2 of
Greta's CDM 2023 talk.
See also video and
slides of Greta's
talk at FPSAC 2023.
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.
Download .pdf file of the full paper.
See also FOCS extended abstract
(local copy).
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).
Download .pdf file of the column.
Here is the journal version (with my picture).
Download .pdf file of the expanded version of the column (notes and references are added).
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.
See also the journal version.
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 P⊂R6 has fewer than k integer points, is also NP-hard. We conclude that the Ehrhart quasi-polynomials of rational polytopes can have arbitrary fluctuations.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
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 .pdf file of the paper.
Download the Featured Math. Review of the FOCS paper,
by Alexander Barvinok.
See also this blog post
by Gil Kalai.
See the FOCS talk video by Danny Nguyen (Oct 2017, 20 min), and my MSRI talk video (Oct 2017, 1 hr).
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.
Download .pdf file of the paper.
Download published version from journal's website (no registration or subscription required).
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,Q⊂R4, 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.
Download .pdf file of the paper.
Download the extended abstract here.
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).
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.
Download .pdf file of the paper.
Download the extended abstract here.
Note: This paper is superseded by our "Short Presburger arithmetic is hard" paper (see above). It will not be published in a journal.
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.
Download .pdf file of the paper.
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.
Download .pdf file.
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?
Download .pdf file.
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.
We address two longstanding open problems, one originating in PL topology, another in birational geometry. First, we prove the weighted version of Oda's strong factorization conjecture (1978), and prove that every two toric varieties that are related by a common iterated blowup (at rationally smooth points). Second, we prove that any two PL homeomorphic polyhedra have a common stellar subdivisions, as conjectured by Alexander in 1930.
Download .pdf file of the paper.
See Karim's talk about the paper
at 2nd ICBS (July 2024).
Read also Karim's blog post and
my blog post on the paper.
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.
Download .pdf file of the paper.
See also an extended abstract in this
MFO 2020-30 report.
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.
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.
Download .pdf file of the paper.
See also this talk by Alexey (slides only).
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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 ε.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
Download .pdf file.
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.
Download .pdf file (676 K) of the paper.
The pictures are better viewed in color, but should print fine
on a monochromatic printer.
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 paper.
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.
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.
Download .pdf file of the paper.
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.
Download .pdf file iof the paper.
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.
Download .pdf file (264 K) of the paper.
Download Referativny Zhurnal review (in Russian),
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.
Download
.pdf file of the paper.
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.
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.
Download .pdf file.
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.
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.
Download .pdf file of the paper (best printed in color).
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.
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.
Download .pdf file of the paper (best printed in color).
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.
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).
See also my blog post inspired by this paper.
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.
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.
Download .pdf file of the paper.
Note: Despite claims in the literature, Conjecture 18 remains unresolved.
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.
Download .pdf file of the paper.
Download Referativny Zhurnal review (in Russian),
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
We give a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.
Download the .pdf file of the paper (31 pages).
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.
See also this
blog post by Gil Kalai.
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)}.
Download the .pdf file of the paper.
Read also my blog post on the paper.
See video
and slides of Prague talk based on the paper.
See also video
by my Banff blackboard talk.
Note: Richard Stanley says this about our work in his recent interview to ECA:
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.
Download the .pdf file of the paper.
Watch my talk
on the paper (BIRS, March 9, 2015).
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).
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.
Download the .pdf file of the paper.
Link to the journal version: is here.
Note: Armstrong's conjecture was later proved by Tommy Cai in this paper.
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.
Note: The limit shape of Baxter permutations was recently studied by Jacopo Borga and Mickaël Maazoun in this paper.
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).
See also slides of my MFO talk based on the paper.
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.
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.
Download the .pdf file of the paper.
Download Cayley's original paper (1857).
See also my blog post on the paper.
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.
Download the .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the erratum.
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.
Download .pdf file.
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.
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.
Download
.pdf file of the paper.
See also a .pdf file of an
extended abstract (11 pages), which will appear in the
FPSAC'07
Conference Proceedings.
See also
slides of my UCLA talk based on the paper.
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).
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.
Download .pdf file.
Transpositions of the form (1,i) are called star transpositions. We compute the diameter and the number of reduced decompositions for various permutations.
Download .pdf file.
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.
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.
Download .pdf file.
We present a new version and a combinatorial proof of the noncommutative quasideterminants of Gelfand-Retakh. Various combinatorial applications are discussed.
Download .pdf file.
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.
Partly incorporated into "Triangulations of Cayley and Tutte polytopes".
Download .pdf file of the preprint.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
See also journal website for the paper.
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.
Download .pdf file of the paper.
See also Zoom talk video
and slides.
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.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the expanded version of the paper.
See also this and that
talk by Greta Panova based in part on this paper.
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.
Download .pdf file of the paper.
See also this talk by Alejandro Morales.
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.
Download .pdf file of the paper.
See also this talk
by Damir Yeliussizov based on the paper.
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.
Download .pdf file of the paper.
See this talk
by Alejandro Morales, and this followup talk.
See also this talk by Martin Tassy based on the paper.
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.
Download .pdf file of the paper.
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.
We give a signed puzzle rule to compute Schubert coefficients. The rule is based on a careful analysis of Knutson's recurrence [Knu03]. We use the rule to prove polynomiality of the sums of Schubert coefficients with bounded number of inversions.
Download .pdf file of the paper.
The Schubert vanishing problem is a central decision problem in algebraic combinatorics and Schubert calculus, with applications to representation theory and enumerative algebraic geometry. The problem has been studied for over 50 years in different settings, with much progress given in the last two decades.
We prove that the Schubert vanishing problem is in AM assuming the Generalized Riemann Hypothesis GRH. This complements our earlier result (2024), that the problem is in coAM assuming the GRH. In particular, this implies that the Schubert vanishing problem is unlikely to be coNP-hard, as we previously conjectured.
The proof is of independent interest as we formalize and expand the notion of a lifted formulation partly inspired by algebraic computations of Schubert problems, and extended formulations of linear programs. We use the result by Mahajan and Vinay (1997) to show that the determinant has a lifted formulation of polynomial size. We combine this with Purbhoo's algebraic criterion (2006) to derive the result.
Download .pdf file of the paper.
Schubert coefficients are structure constants describing multiplication of Schubert polynomials. Deciding positivity of Schubert coefficients is a major open problem in Algebraic Combinatorics. We prove a positive rule for this problem based on two standard assumptions: Generalized Riemann hypothesis (GRH) and Miltersen–Vinodchandran's Assumption (MVA).
Download .pdf file of the paper.
See my blog post on the paper.
See also video of
Colleen's talk
at the Fields Institute on the paper.
Note: Miltersen–Vinodchandran's article is available here. The assumption (MVA) is stated in Theorem 1.5.
Schubert coefficients are nonnegative integers c(u,v,w) that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. It is a major open problem whether they have a combinatorial interpretation, i.e, whether c(u,v,w) are in #P. We study the closely related vanishing problem of Schubert coefficients: {c(u,v,w) =? 0}. Until this work it was open whether this problem is in the polynomial hierarchy PH. We prove that the vanishing problem is in coAM assuming the GRH. In particular, the vanishing problem is in Σ2.
Our approach is based on constructions lifted formulations, which give polynomial systems of equations for the problem. The result follows from a reduction to Parametric Hilbert's Nullstellensatz, recently studied in [A+24]. We apply our construction to show that the vanishing problem is in NPC and PR in the Blum–Shub–Smale (BSS) model of computation over complex and real numbers respectively. Similarly, we prove that computing Schubert coefficients is in #PC, a counting version of the BSS model. We extend our results to all classical types. Type D is resolved in the appendix (joint with David Speyer).
Download .pdf file of the paper.
See also Colleen's talk at IPAM.
Note: For the definition and short list of properties of complexity class AM, see this Wikipedia article and this section of Complexity Zoo.
We prove the existence of signed combinatorial interpretations for a several large families of structure constants. These families include standard bases of symmetric and quasisymmetric polynomials, as well as various bases in Schubert theory.
Download .pdf file of the paper.
Note: Signed combinatorial interpretations are characterized by GapP complexity class.
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).
Download .pdf file of the paper.
Download the paper also from the journal website.
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).
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].
Download .pdf file of the paper.
The journal version is available here.
Note: The 2006 email from John Stembridge to Vic Reiner can be found quoted here.
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.
Download .pdf file of the paper.
See also the journal version of the paper.
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.
Download .pdf file of the paper.
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).
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
See also this talk and that talk by Greta Panova.
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).
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
Note: Further progress on the Saxl conjecture is made here, there and there .
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
An extended abstract of this paper appeared in Proc. FPSAC 2010 (San Francisco, CA).
Download .pdf file
of the extended abstract.
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.
Download .pdf file (350K).
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.
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.
Download .pdf file.
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.
Download .pdf file.
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.
Download .pdf file. Click here for a journal version.
We give a simple bijective proof of the hook-length formula.
Download .pdf file of the paper.
Click
here for a journal version. See also
here for a nice web version of the idea.
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."
Download .pdf file of the full review.
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.
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.
Download .pdf file of the extended abstract.
See also .pdf file of the full version (22 pp., unpublished).
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.
Download .pdf file of the extended abstract.
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.
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).
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.
Download .pdf file of the paper.
See also slides of the talk
(Saint Petersburg Combinatorics Seminar, March 17, 2021).
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).
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
Note that the pictures are colored, so the paper is best read
when printed on a color printer.
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.
Download .pdf file (500K) of the paper.
Note that the pictures are colored, so the paper is best read
when printed on a color printer.
i 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.
Download .pdf file of the paper.
We present a general construction of involutions on integer partitions which enable us to prove a number of modulo 2 partition congruences.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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:
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.
6.1.6 by Sun Kim here (see also §3 in his thesis).
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.
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.
Download .pdf file of the paper.
Download Referativny Zhurnal review (in Russian),
We present a new generalization of Euler's and Sylvester's identities for partitions. The proof is based on an explicit bijection.
Download .pdf file of the paper.
We introduce several new constructions of finite posets with the number of linear extensions given by generalized continued fractions. We apply our results to the problem of the minimum number of elements needed for a poset with a given number of linear extensions.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
See also the journal version (Open Access).
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.
Download .pdf file of the paper.
See the journal version here.
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.
Download .pdf file of the paper.
See my talk at IPAM
on the paper.
Note: Conjecture 1.5 was resolved in this paper by Leake, Lindberg and Oveis Gharan. It's false for the (3+1) poset and holds for the (3+1)-free posets (cf. this paper).
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.
Download .pdf file of the paper.
See also Greta's Zoom talk at ICECA (abstract, video).
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.
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.
Download .pdf file of the paper.
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 .pdf file of the paper.
See also journal version (open access).
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.
See also his Cornell Combinatorics Seminar talk with emphasis
on matroids.
Alternatively, watch
my CJCS talk (Nov 4, 2021), see
video and
slides,
or my Vinberg Lecture (May 4, 2022), see
video and
slides.
For a more in-depth explanation, watch "Combinatorial atlas and their applications" lecture series at the IPAC online seminar:
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.
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.
Download .pdf file of the paper.
Download published version,
See also this talk
by Greta Panova (Banff, Canada, Nov 2021).
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.
Download .pdf file of the paper.
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.
We show that the sorting probability of the Catalan poset Pn satisfies δ(Pn) = O(n–5/4).
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
Note: The paper is motivated by the 1/3-2/3 conjecture. Special cases of the conjecture were resolved by Linial for width-two posets and by Olson-Sagan for Young diagrams. See also this Putnam problem (A3, 2024), and both solutions of the problem (the first solution is based on our paper).
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.
Download .pdf file.
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.
We prove the exponential growth of the cardinality of the set of numbers of spanning trees in simple (and planar) graphs on n vertices, answering a question of Sedláček from 1969. The proof uses a connection with continued fractions, "thin orbits", and Zaremba's conjecture.
Download the .pdf file of the paper.
Here is Alex's tweet on the paper.
See my talk on the paper, video and slides. See also Alex's talk on the paper (video and slides).
Note: Our estimates on the Hausdorff dimension of the Hančl–Turek fractal was improved to 20 significant digits by Mark Pollicott in this paper.
We give an explicit counterexample to the bunkbed conjecture introduced by Kasteleyn in 1985. The counterexample is given by a planar graph on 7222 vertices, and is built on the recent work of Hollom (2024).
Download .pdf file.
Supplementary materials and computer calculations are available here,
see also code on GitHub.
See my blog post on the paper and some backstory in
this blog post.
See Nikita's talk on the paper in the context of his thesis.
See also this series of tweets by Tim Gowers, UCLA press release, this YouTube video by Trefor Bazett or that YouTube video (in German) by Johann Beurich.
Finally, see this article in Quanta Magazine, this article in IFLScience, that in Pour la Science (in French), that in Frankfurter Allgemeine Zeitung (in German), that article in TASS and that article in Security Lab (both in Russian) about our work. There is also this TV news segment (starting at 13:20, in Czech), with completely unfounded geopolitical conclusions.
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.
Download .pdf file of the paper.
Download .pdf file of the accepted version
(heavily edited in PRE style).
See here
for the journal version.
The classical Kirszbraun theorem says that all 1-Lipschitz functions f: A→Rn, A⊂Rn, 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, A⊂X, 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.
Download .pdf file of the paper.
See also .pdf file of the detailed MathSciNet review.
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.
Download .pdf file.
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.
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.
Download .pdf file of the colored version.
Download .pdf file of the monochromatic version.
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].
Download .pdf file.
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.
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.
Download .pdf file of the paper.
See also my Zoom talk video
and slides.
Alternatively, see Han's (much nicer) talk slides.
We present a niew 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.
Download .pdf file of the paper.
See also Jonathan's talk at IPAM (April, 2024).
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.
Download .pdf file of the paper.
Note: This and the arXiv version have an appendix absent in both the published and the first arXiv versions.
We prove log-concavity of exit probabilities of lattice random walks in certain planar regions.
Download .pdf file of the paper.
See video and
slides
of the Banff talk on the subject.
See also S.H. Chan's online poster at
Lattice Paths 2021 Conference.
Note: The MathSciNet review for the article ends with: "The proof techniques used in this article are riveting."
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.
Download .pdf file of the paper.
Note: Conjecture 7.1 is proved by Heng Guo and Mark Jerrum in this paper.
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.
Download .pdf file of the paper.
Note: A sharp upper bound was obtained in this paper by Roberto Oliveira.
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.
Download .pdf file of the paper.
Download .pdf file of the extended
abstract.
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.
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.
Download .pdf file.
Note: Sharper bounds on Kazhdan constants and mixing times of matrix random walks, were later obtained by Martin Kassabov in this paper.
We obtain sharp bounds on mixing time of random walks on nilpotent groups, with Hall bases as generating sets.
Download .pdf file.
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.
Download .pdf file.
Note: Conjecture 4.1 and a variation on Conjecture 4.3 was proved by Michael Larsen and Aner Shalev in this paper.
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.
Download .pdf file.
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.
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.
Download .pdf file
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.
Download .pdf file.
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.
Download .pdf file.
Download Referativny Zhurnal review (in Russian),
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.
Download .pdf file.
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.
Download .pdf file.
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.
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.
Download .pdf file.
Note: For the great progress on conjectures 2.7.2 and 2.7.9, see this survey by Harald Helfgott.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
Note: Lovász's conjecture remains open with progress unlikely. Conjecture 1 was resolved in this paper by Draganić, Montgomery, Correia, Pokrovskiy and Sudakov.
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
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.
Download or .pdf file.
Note: Conjecture 1.6 was proved by Alexander Lubotzky in this paper.
We construct a new large family of finitely generated groups with continuum many values of the following monotone parameters: spectral radius, critical percolation, and asymptotic entropy. We also present several open problems on other monotone parameters.
Download the
.pdf file of the paper.
Read also my blog post on the paper.
Note: See Martin's talk at MSRI on the earlier version of the paper back in December 2016, both video and slides.
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.
Download the .pdf file of the paper.
Note: The matrix size we need for the proof m≈1086 is about 10,000 times the number of atoms in the observable universe.
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.
Download the .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
Download .pdf file.
Note: Recent paper by Anna Erschler and Tianyi Zheng proved a lower bound matching our upper bound, thus resolving the problem.
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.
Download .pdf file.
Note: The Benjamini-Schramm Conjecture was completely resolved by Hugo Duminil-Copin, Subhajit Goswami, Aran Raoufi, Franco Severo, and Ariel Yadin in this paper.
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.
Download .pdf file of the paper.
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 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.
Download .pdf file of the extended abstract.
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.
Download .pdf file.
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.
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.
Download .pdf file of the paper.
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).
Download .pdf file of the paper.
See also .pdf file of the MathSciNet review.
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.
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.
Download .pdf file of the full paper.
Download .pdf file of the extended abstract.
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.
Download .pdf file.
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.
Download .pdf file.
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.
Download .pdf file of the paper.
See here
for a journal version.
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.
Download .pdf file.
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.
Download .pdf file. Read also my blog post about this article.
Note: Ternary Goldbach conjecture was proved in this paper by Harald Helfgott.
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.
Download .pdf file of the paper.
We consider a probabilistic version of the depth-first search on mazes with two exits, and show that this algorithm has equal probability of finding either exit. The proof is combinatorial and uses an explicit involution.
Download .pdf file of the paper.
Download .pdf file of the review.
Download here the published version.
See also this short blog post I wrote on the review.
Note: click here to see links to much of the content of the book.
Download the interview from the journal website.
See errata in my answers in this blog post.
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.
Download .pdf file of the paper.
See also video of the talk by F. Petrov in part based on the paper.
We give a combinatorial proof of the inequality in the title in terms of Fibonacci numbers and Euler numbers. The result is motivated by Sidorenko's theorem on the number of linear extensions of the poset and its complement. We conclude with some open problems.
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.
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.
Download .pdf file of the paper.
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.
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.
Download .pdf file of the paper.
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.
Warning: Most links above are in Russian. If you can't read them, your loss!
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.
Download .pdf file of the paper.
We present combinatorial proofs of several Fine's partition theorems, along with some historical account.
Download .pdf file of the paper.
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.
Download the .pdf file
of the Russian translation here
or here.
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.
The article discusses the editorial and publishing process in physics journal using PRE and to lesser extent other APS journals. Many of the PRE practices and innovations could be of interest to the broad mathematical community. We conclude with some suggestions.
Download .pdf file of the paper, or
my lengthy polemical blog post expounding on the subject.
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.
Download .pdf file of the article, 6 pp., or
the published version with my picture.
In this article we explain the importance of clarity and give other tips for mathematical writing.
Download .pdf file of the article, or the
journal version.
See also MSRI video of a talk based on the article,
and this blog entry.
Note: The article was included on the list of "Notable Writings" in
The Best
Writing on Mathematics (M. Pitici, Ed.), Princeton Univ. Press, 2019.
See also this tweet review
by Steven Strogatz.
Note: I no longer agree with "abbreviate authors' first names" advice. For this, I am thankful to Yufei Zhao for his blog post on the subject and the followup conversation.
The workshop final report is available here (from Banff website).
The workshop summary is available here (from AIM website).
Click here to return to Igor Pak Home Page.
Last updated: April 27, 2025.
