I have papers on the following (overlapping) subjects:
Click here to return to Igor Pak Home Page.
We study complexity of integer sentences in S_{α} = (R, <, +, Z, x ↦ αx), which is known to be decidable for quadratic α, and undecidable for non-quadratic irrationals. When α is quadratic and the sentence has r alternating quantifier blocks, we prove both lower and upper bounds as towers of height (r-3) and r, respectively. We also show that for α non-quadratic, already r=4 alternating quantifier blocks suffice for undecidability.
Download .pdf file of the paper. Note: This version is substantially revised over the first version in the arXiv.
We prove that the problem of minimizing the number of integer points in a parallel translations of a rational convex polytope in R^{6} 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⊂R^{6} 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.
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⊂R^{4}, 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 simplex method works, how fast 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.
A closed PL-curve is called integral if it is comprised of unit intervals. Kenyon's problem asks whether for every integral curve γ in R^{3}, 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 Zoom talk video and
slides.
See also an extended abstract in this
MFO 2020-30 report.
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 R^{3}.
Download .pdf file of the paper.
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 M_{X} 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 p^{n}. 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 R^{2} 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 4n^{3} x 8n^{5} x ζ(n) integer grid, where ζ(n) < (500 n^{8})^{τ(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.
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 R^{n}, 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 R^{n}. 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 R^{n} 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 R^{3}. We also prove nonexistence of an acute triangulation of R^{4} 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 R^{d} 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 R^{d} and a facet F of P, then F is contained in the union of A_{G}. Here the union is over all the facets G of P different from F, and A_{G} 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 R^{3} 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 R^{d} 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 and Schramm.
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 Ch. 4 of his thesis with a similar but more streamlined and conceptual argument. In R^{3}, the continuous blooming conjecture 9.12 was proved by Erik Demaine, Martin Demaine, Vi Hart, John Iacono, Stefan Langerman and Joseph O’Rourke in this paper.
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 10^{6} 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], "Ribbon tile invariants" (see below), where a full basis of invariants of ribbon tiles was conjectured. Here we present a complete proof of the conjecture, which works by associating ribbon tiles with a certain polygon in the complex plane, and deriving invariants from the signed area of this polygon.
Download .pdf file of the paper.
We resolve a problem posed in the "Ribbon tile invariants" paper by extending the set of regions to all simply connected regions in the case n=4. Conway-Lagarias type technique is employed.
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.
See also this
blog post by Gil Kalai.
Let F ⊂ S_{k} be a finite set of permutations and let C_{n}(F) denote the number of permutations σ ∈ S_{n} avoiding the set of patterns F. The Noonan-Zeilberger conjecture states that the sequence {C_{n}(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 {C_{n}(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 a_{n} the number of words in S of length n that are equal to 1. We show that the cogrowth sequence {a_{n}} is not always P-recursive. This is done by developing new combinatorial tools and using known results in computability and probability on groups.
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 S_{n}, such that σ and σ^{-1} are alternating. They proved that the number of such permutations in S_{2n} and S_{2n+1} is the Catalan number C_{n}. In this paper we explore the expected limit shape of such permutations, following the approach by Miner and Pak [MP].
Download the .pdf file of the paper (best printed on a color printer).
Here is the journal page for the paper.
Warning: the file is 1.8Mb.
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 S_{n} 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 β-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 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.
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 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.
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: 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.
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 video of a talk by Greta Panova in part based
on this paper.
Denote by u(n) the largest principal specialization of the Schubert polynomial over all σ in S_{n}. Stanley conjectured that there is a limit of (1/n^{2}) 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.
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 this 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 generalized and proved in this paper.
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,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.
Warning: the pictures are nicely colored, so the paper is best read
when printed on a color printer. Welcome to the 21st century!
See also video of a talk by Greta Panova
in part based on this paper (starting 50:13).
Note: The journal version has subpar typesetting and mislabeled references. Please refer to the above or the arXiv version.
The extended abstract of the paper was published in Proc. FPSAC 2018, in Séminaire Lotharingien de Combinatoire, 80B.84 (2018), 12 pages, available here.
Note: Conjectures 5.17 and 9.6 were proved by Jang Soo Kim and Meesue Yoo in this paper. Conjecture (**) in §6.1 was proved by Alejandro Morales, Igor Pak and Martin Tassy in this paper. Theorem 3.10 which was key to the paper was given an elementary proof in this paper with Fëdor Petrov. This result was also shown to follow from this paper by Daniel Bump, Peter McNamara and Maki Nakasuji (the connection is nontransparent).
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 S_{n}, 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.
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 S_{n} are also considered.
Download .pdf file of the paper.
See also this talk and that talk by Greta Panova.
We prove strict unimodality of the q-binomial (Gaussian) coefficients as polynomials in q. The proof is based on the combinatorics of certain Young tableaux and the semigroup property of Kronecker coefficients of S_{n} representations. 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 S_{n}. 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 S_{n} contain all irreducibles as their constituents. Our main result is that they contain representations corresponding to hooks and two row Young diagrams. For that, we develop a new sufficient condition for the positivity of Kronecker coefficients in terms of characters, and use combinatorics of rim hook tableaux combined with known results on unimodality of certain partition functions. We also present connections and speculations on random characters of S_{n}.
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).
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.
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 (S_{p} x S_{q})-modules are discussed.
Download .pdf file of the extended abstract.
We present several remarkable properties of the one representation of S_{n}, 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 S_{n}-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 S_{n}-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.
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.
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.
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.
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.
Warning: Printing on a monochromatic
printer may distort some colored pictures.
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; Jeremy Lovejoy suggests here that it also follows from this paper,
5.2.7 by Christine Bessenrodt and IP here,
5.2.8 by IP here,
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 show that the sorting probability of the Catalan poset P_{n} satisfies δ(P_{n})= 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.
See also video and
slides
of Swee Hong's talk on the 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.
The classical Kirszbraun theorem says that all 1-Lipschitz functions f: A→R^{n}, A⊂R^{n}, with the Euclidean metric have a 1-Lipschitz extension to R^{n}. 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 Z^{d}-Kirszbraun graphs are exactly graphs that satisfies a certain Helly property. We also consider complexity aspects of these properties.
Download .pdf file.
We show that the Kauffman bracket [L] of a checkerboard colorable virtual link L is an evaluation of the Bollobás-Riordan polynomial R_{G} of a ribbon graph G = G_{L} 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 B_{c}:=1 + (1+1/C)^{1/2}. As a consequence, for B>B_{c}, we prove that the classical independence heuristic leads to a large undercounting.
Download .pdf file of the paper.
See also Zoom talk video
and slides.
We present a new lower bound on the number of contingency tables, improving upon and extending previous lower bounds by Barvinok [Bar09, Bar16] and Gurvits [Gur15]. As an application, we obtain new lower bounds on the volumes of flow and transportation polytopes. Our proofs are based on recent results on Lorentzian polynomials.
Download .pdf file of the paper.
For parameters n,δ,B, and C, let X=(X_{kℓ}) 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 B_{c}=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 < B_{c} or B > B_{c}. Our main result shows that E[X_{11}] is uniformly bounded for B < B_{c}, but has sharp asymptotic C(B-B_{c})n^{1-δ} for B > B_{c}. 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.
This and the arXiv version have an appendix absent in both the published and the first arXiv versions.
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(n^{2.5} log n) for the weak convergence which is close to the trivial lower bound Ω(n^{2}). This improves the upper bound O(n^{4} 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 proved by Jair Donadelli, Penny Haxell and Yoshiharu Kohayakawa 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 S_{n} and A_{n} 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(n^{2}) 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> Cn^{2}. 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 U_{n}(F_{q}), the group of upper triangular n×n matrices over F_{q}, 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 log_{2} |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 remains open, but the Krivelevich-Sudakov (log |G|)^{5} bound on the number of generators was reduced to (log |G|)^{3} in this paper by Demetres Christofides and Klas Markström.
In this paper, we study percolation on finite Cayley graphs. A conjecture of Benjamini says that the critical percolation p_{c} 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 p_{c}.
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 remains open. We continue to disbelieve it.
The automorphism group of a free group Aut(F_{k}) acts on the set of generating k-tuples (g_{1},...,g_{k}) of a group G. Higman showed that when k=2, the union of conjugacy classes of commutators [g_{1},g_{2}] and [g_{1},g_{2}]^{-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) + 10^{7}. 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.
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 p_{c}(G) be the critical probability of the site percolation on the Cayley graph of group G. Benjamini and Schramm conjectured that p_{c}<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(F_{5}) has Kazhdan's property (T). Then, Marek Kaluba, Dawid Kielak and Piotr Nowak proved the same for all Aut(F_{k}), 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 A_{n} 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 A_{n} 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 A_{n}. 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 Ω(k^{2}) 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.
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 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.
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.
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.
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.
In this note we explain the importance of clarity and give other tips for mathematical writing.
Download .pdf file of the paper.
See also the journal version.
See also MSRI video of a talk based on the article, and this blog entry.
Click here to return to Igor Pak Home Page.
Last updated Jan 10, 2020.