I have papers on the following (overlapping) subjects:
Click here to return to Igor Pak Home Page.
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.
An important application of our results is a deterministic construction of uniquely k-colorable graphs with arbitrarily large girth. Constructing such graphs is also a classical problem; a non-constructive proof of existence was given by Bollobás and Sauer in 1976. We present an explicit, asymptotically optimal (logarithmic girth) construction of vertex transitive uniquely k-colorable graphs, based on Cayley expanders. Other applications are also discussed.
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.
A special case of the technical part is given in this note:
(with Rom Pinchasi)
The collapsing walls theorem, to appear in Amer. Math. Monthly,
2009, 5 pp.
Download .pdf file of the full paper, and .pdf file of the short note.
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 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 .ps file or .pdf file of the paper.
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 .ps file or
.pdf file of the paper.
Download .ps file or
.pdf file of the Russian
translation, or go to the
journal
web site.
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 .dvi file, .ps file or .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 .ps file (664 K) or .pdf file (205 K) of 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 .ps file (674 K) or .pdf file (264 K) of the paper.
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 .ps file (1.1 M) or
.pdf file (430 K) of the paper.
The pictures are colored and better viewed in color.
They should print fine on a monochromatic printer.
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 .dvi file, .ps file or .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 .dvi file, .ps file, or .pdf file.
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 .dvi file, .ps file, or .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.
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).
In [BNRR], it was shown that tiling of general regions with two rectangles is NP-complete, except for few trivial special cases. In a different direction, Rémila [Rem2] 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 (note: it is color optimized, so if printed try to use a color printer)
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 .ps file or .pdf file of the paper.
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 .ps file or .pdf file of the paper.
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 .ps file or .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 .dvi file, .ps file, or .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 .dvi file or .pdf file of the paper.
Compare reviews in Zbl. Math. and Math. Reviews. See also a .ps file of an extended abstract (10 pages), which appeared in FPSAC'98 Conference Proceedings.
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).
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. As an application, we give a slight improvement to Gilbert's asymptotic bound for the number of connected labeled graphs.
Download the .dvi file, .ps file, or .pdf file of 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.
The published version contained a 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 .dvi file,
.ps file or
.pdf file.
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 .dvi file, .ps file or .pdf file.
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 .ps file or
.pdf file.
See also a .pdf file of an
extended abstract (11 pages), which will appear in the
FPSAC'07
Conference Proceedings.
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 .ps file or .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 .ps file or .pdf file.
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 .dvi file, .ps file or .pdf file.
We present a new version and a combinatorial proof of the noncommutative quasideterminants of Gelfand-Retakh. Various combinatorial applications are discussed.
Download .dvi file, .ps file or .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.
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.
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 .ps file or .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 .ps file or .pdf file of the paper.
An extended abstract of this paper appeared in Proc. FPSAC 2010 (San Francisco, CA).
Download .ps file or .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 .ps file (1M), or .pdf file (350K).
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 .ps file or .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 .dvi file, .ps file or .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 .ps file or .pdf file. Click here for a journal version.
We give a simple bijective proof of the hook-length formula.
Download .ps file or .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).
Finally, to answer a common question: yes, 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).
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 (Sp x Sq)-modules are discussed.
Download .dvi file or .ps file of the extended abstract.
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 .dvi file or .ps 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.
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 .ps file or .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 .ps file or
.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 .ps file or .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 .ps file or .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.
In the MathSciNet review,
George Andrews writes:
"This paper undertakes a monumental task: to present a reasonably coherent
account of partition bijections. [...]
This is a truly important contribution.
The author's presentation is lucid, often clarifying or improving the
original work and providing new insights."
Download .pdf
file of the paper and .pdf file
of the MathSciNet review.
Warning: The paper file is 660K. Printing on a monochromatic
printer may distort some colored pictures.
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 .dvi file, .ps file or .pdf file.
We present combinatorial proofs of several Fine's partition theorems, along with some historical account.
Download .ps file or .pdf file.
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.
We present a new generalization of Euler's and Sylvester's identities for partitions. The proof is based on an explicit bijection.
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 .ps file or .pdf file (both in color).
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.
We present two versions of the paper which differ only in the pictures. The first, colored version is for viewing on a monitor and printing on a colored printer. The second, monochromatic version, is optimized for printing on a monochromatic printer.
Download .ps file or
.pdf file of the colored version.
Download .ps file or
.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 .ps 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.
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.
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.
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 .dvi file, .ps
file, or .pdf file of the paper.
Download .dvi file, .ps
file or .pdf file of the extended
abstract.
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 .dvi file, .ps file or .pdf file.
We obtain sharp bounds on mixing time of random walks on nilpotent groups, with Hall bases as generating sets.
Download .dvi file, .ps file or .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 .dvi file, .ps file, or .pdf file.
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 .dvi file, .ps file or .pdf file.
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 .dvi file, .ps file, or .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 .dvi file, .ps file, or .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 .dvi file, .ps file, or .pdf file.
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 Lecture Notes in Computer Science (J. Nesetril, Ed.), vol. 1643, Springer, 1999.
Download .dvi file or .ps 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 .dvi file or .ps file.
An extended abstract of the paper has appeared in Proc. FPSAC'99 Conference, 417-428. Download .dvi file or .ps file of the extended abstract.
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.
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 .dvi file, .ps file, or .pdf file of the paper.
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 .dvi file,
.ps file, or
.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.
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 .dvi file, .ps file, or .pdf file of the paper.
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.
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 .dvi file, or .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 .ps file, or .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 .ps file, or .pdf file of the paper.
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 .dvi file, .ps file, or .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 .dvi file, .ps file, or .pdf file.
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.
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 .dvi file, .ps file, or .pdf file of the paper.
The extended abstract of the paper has appeared in the Proc. SODA'2002. Download .dvi file, .ps file or .pdf file of the extended abstract. Note that the proceedings version does not contain the Appendix.
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 .dvi file, .ps file or .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 .dvi file, .ps file, or .pdf file.
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 .dvi file or .ps file.
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 .dvi file,
.ps file, or
.pdf file of the paper.
See also .dvi file, .ps file,
or .pdf file of the MathSciNet review.
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 .dvi file,
.ps file,
or .pdf file of the full paper.
Download .dvi file, .ps
file, or .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 .dvi file or .ps 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 .dvi file, .ps file or .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 .dvi file, .ps file
or .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 .dvi file or .ps 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 .dvi file (a picture is missing in the Appendix), .ps file, or .pdf file
We present several combinatorial and probabilistic algorithms for generating random k-subsets of n-sets, k-subspaces of a n-dimensional space over the finite field, random nonsingular matrices, etc.
Check out a review by M. Fulmeck in Math. Reviews, or another review by A. Hulpke in Zbl. Math..
Click here to return to Igor Pak Home Page.
Last updated 3/23/2013.