Abstract
This paper deals with lattice congruences of the weak order on the symmetric group, and initiates the investigation of the cover graphs of the corresponding lattice quotients. These graphs also arise as the skeleta of the so-called quotientopes, a family of polytopes recently introduced by Pilaud and Santos [Bull. Lond. Math. Soc., 51:406–420, 2019], which generalize permutahedra, associahedra, hypercubes and several other polytopes. We prove that all of these graphs have a Hamilton path, which can be computed by a simple greedy algorithm. This is an application of our framework for exhaustively generating various classes of combinatorial objects by encoding them as permutations. We also characterize which of these graphs are vertex-transitive or regular via their arc diagrams, give corresponding precise and asymptotic counting results, and we determine their minimum and maximum degrees.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. E. L. Aldred, S. Bau, D. A. Holton and B. D. McKay, Nonhamiltonian 3-connected cubic planar graphs, SIAM Journal on Discrete Mathematics 13 (2000), 25–32.
D. W. Barnette, Conjecture 5, in Recent Progress in Combinatorics. Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, Academic Press, New York-London, 1969, p. 343.
G. Chatel and V. Pilaud, Cambrian Hopf algebras, Advances in Mathematics 311 (2017), 598–633.
J. Cardinal, V. Sacristán and R. I. Silveira, A note on flips in diagonal rectangulations, Discrete Mathematics & Theoretical Computer Science 20 (2018), Article no. 14.
L. Demonet, O. Iyama, N. Reading, I. Reiten and H. Thomas, Lattice theory of torsion classes, Transactions of the American Mathematical Society, to appear, https://arxiv.org/abs/1711.01785.
S. Giraudo, Algebraic and combinatorial structures on pairs of twin binary trees, Journal of Algebra 360 (2012), 115–157.
F. Gray, Pulse code communication, U.S. Patent no. 2,632,058, 1953.
B. Grünbaum, Polytopes, graphs, and complexes, Bulletin of the American Mathematical Society 76 (1970), 1131–1201.
E. Hartung, H. P. Hoang, T. Mütze and A. Williams, Combinatorial generation via permutation languages. I. Fundamentals, Transactions of the American Mathematical Society, to appear, https://arxiv.org/abs/1906.06069.
E. Hartung, H. P. Hoang, T. Muütze and A. Williams, Combinatorial generation via permutation languages, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, Philadelphia, PA, 2020, pp. 1214–1225.
C. Hohlweg and C. E. M. C. Lange, Realizations of the associahedron and cyclohedron, Discrete & Computational Geometry 37 (2007), 517–543.
F. Hurtado and M. Noy, Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry 13 (1999), 179–188.
W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
S. Johnson, Generation of permutations by adjacent transposition, Mathematics of Computation 17 (1963), 282–285.
J.-L. Loday, Realization of the Stasheff polytope, Archiv der Mathematik 83 (2004), 267–278.
L. Lovász, The factorization of graphs, in Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf. Calgary, Alberta, 1969), Gordon and Breach, New York, 1970, pp. 243–246.
C. Lange and V. Pilaud, Associahedra via spines, Combinatorica 38 (2018), 443–486.
S. Law and N. Reading, The Hopf algebra of diagonal rectangulations, Journal of Combinatorial Theory. Series A 119 (2012), 788–824.
J. M. Lucas, The rotation graph of binary trees is Hamiltonian, Journal of Algorithms 8 (1987), 503–535.
J. M. Lucas, D. R. van Baronaigien, and F. Ruskey, On rotations and the generation of binary trees, Journal of Algorithms 15 (1993), 343–366.
OEIS Foundation, The on-line encyclopedia of integer sequences, http://oeis.org.
V. Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, Journal of Combinatorial Theory. Series A 155 (2018), 418–457.
V. Pilaud and V. Pons, Permutrees, Algebraic Combinatorics 1 (2018), 173–224.
V. Pilaud and F. Santos, The brick polytope of a sorting network, European Journal of Combinatorics 33 (2012), 632–662.
V. Pilaud and F. Santos, Quotientopes, Bulletin of the London Mathematical Society 51 (2019), 406–420.
N. Reading, Lattice and order properties of the poset of regions in a hyperplane arrangement, Algebra Universalis 50 (2003), 179–205.
N. Reading, Cambrian lattices, Advances in Mathematics 205 (2006), 313–353.
N. Reading, From the Tamari lattice to Cambrian lattices and beyond, in Associahedra, Tamari Lattices and Related Structures, Progress in Mathematical Physics, Vol. 299, Birkhäuser/Springer, Basel, 2012, pp. 293–322.
N. Reading, Noncrossing arc diagrams and canonical join representations, SIAM Journal on Discrete Mathematics 29 (2015), 736–750.
N. Reading, Finite Coxeter groups and the weak order, in Lattice Theory: Special Topics and Applications. Vol. 2, Birkhäuser/Springer, Cham, 2016, pp. 489–561.
N. Reading, Lattice theory of the poset of regions, in Lattice Theory: Special Topics and Applications. Vol. 2, Birkhäuser/Springer, Cham, 2016, pp. 399–487.
A. Seidenberg, A simple proof of a theorem of Erdős and Szekeres, Journal of the London Mathematical Society 34 (1959), 352.
J. M. Steele, Variations on the monotone subsequence theme of Erdős and Szekeres, in Discrete Probability and Algorithms (Minneapolis, MN, 1993), IMA Volumes in Mathematics and its Applications, Vol. 72, Springer, New York, 1995, pp. 111–131.
D. Tamari, The algebra of bracketings and their enumeration, Nieuw Archief voor Wiskunde 10 (1962), 131–146.
H. F. Trotter, Algorithm 115: Perm, Communications of the ACM 5 (1962), 434–435.
Acknowledgments
We thank Jean Cardinal, Vincent Pilaud, and Nathan Reading for several stimulating discussions about lattice congruences of the weak order on Sn. Figures 4 and 7 in this paper were obtained by modifying and augmenting Figures 6 and 9 from [PS19], and the original source code for those figures was provided to us by Vincent Pilaud. We also thank the anonymous reviewer who provided many thoughtful remarks that helped improving this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this paper appeared in the Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020) [HHMW20].
Torsten Mütze was supported by Czech Science Foundation grant GA 19-08554S, and by German Science Foundation grant 413902284.
Rights and permissions
About this article
Cite this article
Hoang, H.P., Mütze, T. Combinatorial generation via permutation languages. II. Lattice congruences. Isr. J. Math. 244, 359–417 (2021). https://doi.org/10.1007/s11856-021-2186-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-021-2186-1