The Library
Combinatorial generation via permutation languages. II. Lattice congruences
Tools
Tools
Tools
Hoang, Hung P. and Mutze, Torsten (2021) Combinatorial generation via permutation languages. II. Lattice congruences. Israel Journal of Mathematics, 244 . pp. 359-417. doi:10.1007/s11856-021-2186-1 ISSN 0021-2172.
|
PDF
WRAP-Combinatorial-generation-via-permutation-languages-II-Lattice-congruences-Mutze-2020.pdf - Accepted Version - Requires a PDF viewer. Download (2003Kb) | Preview |
Official URL: https://doi.org/10.1007/s11856-021-2186-1
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.
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Congruence lattices , Symmetry groups , Computer science -- Mathematics, Polytopes , Permutations | |||||||||
| Journal or Publication Title: | Israel Journal of Mathematics | |||||||||
| Publisher: | Springer | |||||||||
| ISSN: | 0021-2172 | |||||||||
| Official Date: | September 2021 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 244 | |||||||||
| Page Range: | pp. 359-417 | |||||||||
| DOI: | 10.1007/s11856-021-2186-1 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Reuse Statement (publisher, data, author rights): | This is a post-peer-review, pre-copyedit version of an article published in Israel Journal of Mathematics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11856-021-2186-1 | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Date of first compliant deposit: | 7 October 2020 | |||||||||
| Date of first compliant Open Access: | 21 August 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Related URLs: | ||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
