Traversing regions of supersolvable hyperplane arrangements and their lattice quotients
Sofia Brenner, Jean Cardinal, Thomas McConville, Arturo Merino, Torsten Mütze
Abstract
For an arrangement of hyperplanes in through the origin, a region is a connected subset of . The graph of regions has a vertex for every region, and an edge between any two vertices whose corresponding regions are separated by a single hyperplane from . We aim to compute a Hamiltonian path or cycle in the graph , i.e., a path or cycle that visits every vertex (=region) exactly once. Our first main result is that if is a supersolvable arrangement, then the graph of regions has a Hamiltonian cycle. More generally, we consider quotients of lattice congruences of the poset of regions , obtained by orienting the graph away from a particular base region . Our second main result is that if is supersolvable and is a canonical base region, then for any lattice congruence on , the cover graph of the quotient lattice has a Hamiltonian path.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Related papers
- Zigzagging through acyclic orientations of chordal graphs and hypergraphsJean Cardinal, Hung Phuc Hoang, Arturo Merino, Torsten MützeSODA 2023 · 3 citations
- Listing faces of polytopesNastaran Behrooznia, Sofia Brenner, Arturo Merino, Torsten Mütze et al.SODA 2026 · 3 citations
- Combinatorial generation via permutation languagesElizabeth J. Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron WilliamsSODA 2020 · 22 citations
- Facet-HamiltonicityHugo A. Akitaya, Jean Cardinal, Stefan Felsner, Linda Kleist et al.SODA 2025
- Traversing combinatorial 0/1-polytopes via optimizationArturo Merino, Torsten MützeFOCS 2023 · 2 citations
