Combinatorial generation via permutation languages. II. Lattice congruences

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Combinatorial generation via permutation languages. II. Lattice congruences

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Combinatorial generation via permutation languages. II. Lattice congruences

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-08554S" target="_blank" >GA19-08554S: Struktury a algoritmy ve velmi symetrických grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Israel Journal of Mathematics

ISSN

0021-2172

e-ISSN

—

Svazek periodika

244

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

IL - Stát Izrael

Počet stran výsledku

59

Strana od-do

359-417

Kód UT WoS článku

000687017400008

EID výsledku v databázi Scopus

2-s2.0-85113188157