Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.14327 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912661901410304 |
|---|---|
| author | Brenner, Sofia Cardinal, Jean McConville, Thomas Merino, Arturo Mütze, Torsten |
| author_facet | Brenner, Sofia Cardinal, Jean McConville, Thomas Merino, Arturo Mütze, Torsten |
| contents | 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. [...] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14327 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Combinatorial generation via permutation languages. VII. Supersolvable hyperplane arrangements Brenner, Sofia Cardinal, Jean McConville, Thomas Merino, Arturo Mütze, Torsten Combinatorics 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. [...] |
| title | Combinatorial generation via permutation languages. VII. Supersolvable hyperplane arrangements |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.14327 |