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