Lune

SODA2026Top-tier venue

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 H\mathcal{H} of hyperplanes in Rn\mathbb{R}^n through the origin, a region is a connected subset of Rn∖H\mathbb{R}^n \setminus \mathcal{H}. The graph of regions G(H)G(\mathcal{H}) has a vertex for every region, and an edge between any two vertices whose corresponding regions are separated by a single hyperplane from H\mathcal{H}. We aim to compute a Hamiltonian path or cycle in the graph G(H)G(\mathcal{H}), i.e., a path or cycle that visits every vertex (=region) exactly once. Our first main result is that if H\mathcal{H} is a supersolvable arrangement, then the graph of regions G(H)G(\mathcal{H}) has a Hamiltonian cycle. More generally, we consider quotients of lattice congruences of the poset of regions P(H,R0)\mathsf{P}(\mathcal{H}, R_0), obtained by orienting the graph G(H)G(\mathcal{H}) away from a particular base region R0R_0. Our second main result is that if H\mathcal{H} is supersolvable and R0R_0 is a canonical base region, then for any lattice congruence ≡\equiv on P(H,R0)=:L\mathsf{P}(\mathcal{H}, R_0) =: L, the cover graph of the quotient lattice L/≡L/{\equiv} has a Hamiltonian path.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Zigzagging through acyclic orientations of chordal graphs and hypergraphsJean Cardinal, Hung Phuc Hoang, Arturo Merino, Torsten MützeSODA 2023 · 3 citations
  2. Listing faces of polytopesNastaran Behrooznia, Sofia Brenner, Arturo Merino, Torsten Mütze et al.SODA 2026 · 3 citations
  3. Combinatorial generation via permutation languagesElizabeth J. Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron WilliamsSODA 2020 · 22 citations
  4. Facet-HamiltonicityHugo A. Akitaya, Jean Cardinal, Stefan Felsner, Linda Kleist et al.SODA 2025
  5. Traversing combinatorial 0/1-polytopes via optimizationArturo Merino, Torsten MützeFOCS 2023 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines