Combinatorial generation via permutation languages. II. Lattice congruences
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10435481" target="_blank" >RIV/00216208:11320/21:10435481 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Dc3ilISx04" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Dc3ilISx04</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s11856-021-2186-1" target="_blank" >10.1007/s11856-021-2186-1</a>
Alternative languages
Result language
angličtina
Original language name
Combinatorial generation via permutation languages. II. Lattice congruences
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-08554S" target="_blank" >GA19-08554S: Structures and algorithms in highly symmetric graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Israel Journal of Mathematics
ISSN
0021-2172
e-ISSN
—
Volume of the periodical
244
Issue of the periodical within the volume
1
Country of publishing house
IL - THE STATE OF ISRAEL
Number of pages
59
Pages from-to
359-417
UT code for WoS article
000687017400008
EID of the result in the Scopus database
2-s2.0-85113188157