2
$\begingroup$

Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. The dual graph of the hyperplane arrangement is the graph with the vertex set the set of regions in $\mathbb{R}^d$ bounded by $H_1,\cdots,H_n$. There is an edge between two vertices if the corresponding regions (which are $d$-dimensional polytopes) share a common facet. Denote by $\Gamma(\mathscr{A})$ the dual graph of the simple hyperplane arrangement $\mathscr{A}$.

Now my question is:

Does $\Gamma(\mathscr{A})$ admit a Hamiltonian path? By definition, a Hamiltonian path is a path that visits each vertex of the graph exactly once.

Since the regions bounded by the hyperplanes in $\mathbb{R}^d$ can be labelled by sign sequences, namely a vector $\alpha\in\{+,-\}^n$, we can realize $\Gamma(\mathscr{A})$ as a subgraph of the $n$-dimensional hypercube, and the latter is known to have a Hamiltonian path (actually, a Hamiltonian cycle), but I don't know how this observation could be helpful since there are many sign sequences in $\{+,-\}^n$ which are not associated to a non-empty region.

I know almost nothing about combinatorics, hopefully the question makes some sense.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ ncbi.nlm.nih.gov/pmc/articles/PMC6605083 hope this helps $\endgroup$
    – Peter Wu
    Commented Mar 14 at 3:41
  • $\begingroup$ If I understand it correctly, your definition of simple is equivalent to the normal vectors being linearly independent, so up to a change of basis it seems like you only get coordinate hyperplane arrangements (in which case the dual graph is just an hypercube). $\endgroup$
    – Antoine Labelle
    Commented Mar 14 at 5:00
  • $\begingroup$ @AntoineLabelle Why？I didn't require the normal vectors to be linearly independent. $\endgroup$
    – YHBKJ
    Commented Mar 14 at 5:05
  • $\begingroup$ Isn't that equivalent to asking that the intersection of any $k$ hyperplanes among the arrangement has codimension $k$? $\endgroup$
    – Antoine Labelle
    Commented Mar 14 at 5:09
  • $\begingroup$ @AntoineLabelle If you have the $x$ and $y$ coordinate axes in $\mathbb{R}^2$ and $x+y=1$, this is a simple hyperplane arrangement, but the normal vectors of the 3 hyperplanes are not linearly independent. $\endgroup$
    – YHBKJ
    Commented Mar 14 at 5:11

1 Answer 1

Reset to default
2
$\begingroup$

Already in the plane there are arrangements such that the longest path in their dual covers roughly at most $2/3$ of the regions, therefore they are not Hamiltonian. The reason is that the dual graph is bipartite, and for some arrangements one part of the bipartition can be about twice as large as the other part.

See e.g. the remark at the end of Section 2 in U. Hoffmann, L. Kleist and T. Miltzow, Upper and Lower Bounds on Long Dual-Paths in Line Arrangements, https://arxiv.org/abs/1506.03728.

For an example of such an arrangement, see Figure 2 in Z. Füredi and I. Palásti, Arrangements of lines with a large number of triangles, Proc. Amer. Math. Soc. 92 (1984), 561-566, https://www.ams.org/journals/proc/1984-092-04/S0002-9939-1984-0760946-2/.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .