Hamiltonian Cycles in Simplicial and Supersolvable Hyperplane Arrangements

Veronika Körber, Tobias Schnieders, Jan Stricker, Jasmin Walizadeh · 2025

Read Hamiltonian Cycles in Simplicial and Supersolvable Hyperplane Arrangements by Veronika Körber, Tobias Schnieders, Jan Stricker, Jasmin Walizadeh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14538.txt.

Introduction

Veronika Körber, Tobias Schnieders, Jan Stricker, and Jasmin Walizadeh study cycles in graphs built from hyperplane arrangements in a 2025 paper. An arrangement is a set of flat walls that cut space into regions, and its graph links regions that share a wall. A Hamiltonian cycle visits every region exactly once before returning, like a Gray code.

The authors confirm such cycles for all three-dimensional simplicial arrangements in a standard catalogue. They extend older results to show cycles exist for all restrictions of reflection arrangements, including Weyl groupoids. They also prove cycles for the broader class of supersolvable arrangements and related structures. Their proof builds the cycle step by step from the structure of the arrangement.

Catalog record

CREATORVeronika Körber, Tobias Schnieders, Jan Stricker, Jasmin Walizadeh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-14538

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hamiltonian Cycles in Simplicial and Supersolvable Hyperplane Arrangements Veronika Körber, Tobias Schnieders, Jan Stricker, Jasmin Walizadeh Abstract . Motivated by the Gray code interpretation of Hamiltonian cycles in Cayley graphs, we investigate the existence of Hamiltonian cycles in tope graphs of hyperplane arrangements, with a focus on simplicial, reflection, and supersolvable arrangements. We confirm Hamiltonicity for all 3-dimensional simplicial arrangements listed in the Grünbaum–Cuntz catalogue. Extending earlier results by Conway, Sloane, and Wilks, we prove that all restrictions of finite reflection arrangements, including all Weyl groupoids and crystallographic arrangements, admit Hamiltonian cycles. Finally, we further establish that all supersolvable hyperplane arrangements and supersolvable oriented matroids have Hamiltonian cycles, offering a constructive proof based on their inductive structure. 2020 Mathematics Subject Classification Primary 52C35 \cdot Secondary 05C45 \cdot 51F15 \cdot 52C40 1. Introduction There are many algorithms that construct all subsets or all permutations of a finite set successively. Such an algorithm is called Gray code, if we can get from one object to the next one by a minimal change. Nijenhuis and Wilf explain such a Gray code for the subsets of a finite set by adding or removing only one element in each step [ NW14 ] . Such Gray codes for permutations were given by Johnson [ Joh63 ] and Trotter [ Tro62 ] in the 1960s. We can interpret these Gray codes as Hamiltonian cycles in Cayley graphs of permutation groups generated by simple transpositions. It is widely conjectured that all finite Cayley graphs have a Hamiltonian cycle. Conway, Sloane, and Wilks found Hamiltonian cycles in the Cayley graphs of all finite reflection groups [ CSW89 ] . Also we recently found that Takato Inoue and Hiroyuki Yamane proved, that the Cayley graphs of finite weyl groupoids admit a Hamiltonian cycle [ Yam21 , IY23 ] . Reflection groups are special groups that can be described by hyperplane arrangements, where the group elements correspond to reflections along the hyperplanes. The graph of regions or tope graph is precisely the Cayley graph for a certain set of generators. For each hyperplane arrangement, we can interpret the region graph as a tope graph, which is a subgraph of the cube graph. Therefore, for reflection groups, a Hamiltonian cycle on the Cayley graph is the same as a Hamiltonian cycle on the tope graph. In general, tope graphs of hyperplane arrangements do not have a Hamiltonian cycle. We consider the reflection arrangements and their restrictions, which are simplicial arrangements. These arrangements include the finite connected Weyl groupoids and crystallographic arrangements in dimension 3 and above. We further consider the Grünbaum–Cuntz Catalogue of all known simplicial arrangements in dimension 3 [ CEL22 ] and show that all their tope graphs have a Hamiltonian cycle. We extend Conway, Sloane, and Wilks proof to all restrictions of reflection arrangements. These arrangements are also of particular interest, since it is conjectured that all inscribable zonotopes come from these arrangements [ MS22 ] . At last, many of the arrangements in the Grünbaum–Cuntz catalogue are supersolvable arrangements. This leads to a construction for Hamiltonian cycles for all supersolvable arrangements and oriented matroids. While writing this paper, we learned that Sofia Brenner, Jean Cardinal, Thomas McConville, Arturo Merino, and Torsten Mütze [ Bre+25 ] simultaneously and independently also found these results for supersolvable hyperplane arrangements. Acknowledgement. This paper grew out of a project within a Dive into Research , which grants research experience to undergraduates. We thank Professors Michael Cuntz, Lukas Kühne, and Raman Sanyal, who organised the Dive into Research. Jan Stricker was supported by the SPP 2458 Combinatorial Synergies , funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 539866293. We are also thankful for the funding for the Dive into Research from the DFG priority programme SPP 2458 Combinatorial Synergies . At last, we want to give special thanks to Professor Raman Sanyal, who posed the starting question and helped a lot with proofreading and insightful discussions. 2. Preliminaries Let us start by defining the objects we are working with and some of their basic properties. For a given positive integer m , the set [m] denotes the set \{1,2,\ldots,m\} . Definition 2.1 . A hyperplane H\subseteq\mathbb{R}^{n} is a codimension-1 affine subspace, which we can describe as \displaystyle H\coloneq\{x\in\mathbb{R}^{n}\penalty\ \mid\penalty\ \alpha_{1}x_{1}+\alpha_{2}x_{2}+\cdots+\alpha_{n}x_{n}=b\} for some \alpha\in\mathbb{R}^{n}\setminus\{0\} and some b\in\mathbb{R} . The vector \alpha is called a normal of H . We denote a hyperplane defined by \alpha and b=0 as H_{\alpha} . The choice of a normal vector gives the hyperplane an orientation. Notation 2.2 . We denote the closed/open half spaces of a hyperplane H_{\alpha} by \displaystyle H_{\alpha}^{\geq} \displaystyle\coloneq\{x\in\mathbb{R}^{n}\mid\alpha^{t}x\geq 0\}, \displaystyle H_{\alpha}^{\leq} \displaystyle\coloneq\{x\in\mathbb{R}^{n}\mid\alpha^{t}x\leq 0\}, \displaystyle H_{\alpha}^{>} \displaystyle\coloneq\{x\in\mathbb{R}^{n}\mid\alpha^{t}x>0\}, \displaystyle H_{\alpha}^{<} \displaystyle\coloneq\{x\in\mathbb{R}^{n}\mid\alpha^{t}x<0\}. Definition 2.3 . A hyperplane arrangement {\mathcal{A}} is a finite non-empty set of hyperplanes. If all hyperplanes in {\mathcal{A}} contain the origin, we call {\mathcal{A}} a central hyperplane arrangement. Definition 2.4 . The intersection lattice of a central hyperplane arrangement {\mathcal{A}}=\left\{\,H_{1},\ldots,H_{m}\,\right\} in \mathbb{R}^{n} is the set {\mathcal{L}}({\mathcal{A}})=\left\{\,\bigcup_{i\in I}H_{i}\mid I\subset[m]\,\right\}, partially ordered by reverse inclusion. This is a geometric lattice. The rank of an element X\in{\mathcal{L}}({\mathcal{A}}) is its codimension in \mathbb{R}^{n} . The rank of a hyperplane arrangement {\mathcal{A}} is the codimension of \bigcap_{H\in{\mathcal{A}}}H . If the rank equals the dimension of the ambient space, we call {\mathcal{A}} essential . For an essential hyperplane arrangement, the atoms of the lattice are the hyperplanes, the coatoms are the rank- (n-1) elements. Definition 2.5 . The complement of the arrangement in the ambient space \mathbb{R}^{n}\setminus\bigcup_{H\in{\mathcal{A}}}H is disconnected. The closures of the connected components are called regions . We denote the set of regions with {\mathcal{R}}({\mathcal{A}}) . The intersection of two regions with affine codimension 1 is a wall of both regions. Each wall is inside a hyperplane of the arrangement. A region is called simplicial if the normal vectors of the hyperplanes from all walls are linearly independent. If all regions of {\mathcal{A}} are simplicial, we call {\mathcal{A}} a simplicial hyperplane arrangement. Definition 2.6 . Let {\mathcal{A}} be a hyperplane arrangement. By the deletion of a hyperplane H , we obtain the hyperplane arrangement {\mathcal{A}}\setminus\left\{\,H\,\right\} in \mathbb{R}^{n} . We call an arrangement that results by multiple deletions from {\mathcal{A}} , a subarrangement of {\mathcal{A}} . The restriction to a hyperplane H gives us a hyperplane arrangement {\mathcal{A}}^{H}=\left\{\,H^{\prime}\cap X\mid H\neq H^{\prime}\in{\mathcal{A}}\,\right\}. Since for subarrangements, regions only get bigger, we can define a surjective map on the regions of the arrangement. Definition (and Lemma) 2.7 . Let {\mathcal{A}}^{\prime} be a subarrangement of {\mathcal{A}} . We define a map \displaystyle\pi:\penalty\ {\mathcal{R}}({\mathcal{A}}) \displaystyle\rightarrow{\mathcal{R}}({\mathcal{A}}^{\prime}) \displaystyle R \displaystyle\mapsto R^{\prime}\text{, where }R^{\prime}\in{\mathcal{R}}({\mathcal{A}}^{\prime}):R\subseteq R^{\prime}. This map is well-defined and surjective. Definition 2.8 . For a central hyperplane arrangement {\mathcal{A}}=\{H_{1},\ldots,H_{m}\} with a chosen order and orientation of the hyperplanes, we assume that the positive and negative sides of each hyperplane are fixed. A tope s_{R} for a region R is a map s_{R}:[m]\rightarrow\{-,+\} , where s_{R}(k)=+ if R\subseteq H_{k}^{\geq} and s_{R}(k)=- if R\subseteq H_{k}^{\leq} . We often identify s_{R} with the vector (s_{R}(1),s_{R}(2),\ldots,s_{R}(m))\in\left\{\,-,+\,\right\}^{m} . The collection of these functions s:[m]\rightarrow\{-,+\} forms the vertex set of the tope graph for a hyperplane arrangement, with two such functions (vertices) being adjacent if their values differ on exactly one element of [m] . We note the tope graph

Read the complete text