Long Alternating Paths in Colored Line Arrangements

Definitions and mathematical statement

Use the standard interpretation of a line arrangement in the real affine plane. Let $n\in{\mathbb{N}}$ be positive, and let $\mathcal L=\mathcal L_r\sqcup\mathcal L_b\sqcup\mathcal L_g$ consist of $3n$ distinct lines in ${\mathbb{R}}^2$, with $|\mathcal L_r|=|\mathcal L_b|=|\mathcal L_g|=n$. The lines in these three classes are colored red, blue, and green, respectively. Interpret general position as requiring that no two lines are parallel and no three lines pass through a common point.

The cells of the arrangement are the connected components of \[ {\mathbb{R}}^2\setminus\bigcup_{\ell\in\mathcal L}\ell. \] Define its dual graph $G(\mathcal L)$ to have one vertex for each cell, with two vertices adjacent when their cells share a boundary interval of positive length. Color each dual edge by the color of the unique arrangement line supporting that shared boundary interval. Both bounded and unbounded cells are included.

A simple dual path $P=(F_0,F_1,\ldots,F_m)$ consists of distinct cells with successive cells adjacent. Its length is $m$, the number of dual edges. It is alternating if \[ \operatorname{col}(F_{i-1}F_i)\ne\operatorname{col}(F_iF_{i+1}) \qquad(1\le i<m). \] Thus consecutive crossings must have different colors; no fixed cyclic order of the three colors is required, and an arrangement line may be crossed more than once.

Question. Do there exist constants $c,C>0$ and $n_0\in{\mathbb{N}}$, independent of the arrangement, such that for every integer $n\ge n_0$ and every arrangement satisfying these hypotheses, there is a simple alternating dual path $P$ with \[ cn^2\le |E(P)|\le Cn^2? \] This expresses the supplied requirement of length $\Theta(n^2)$ with uniform constants.

Interpretive qualifications. The supplied record does not explicitly define the ambient plane, general position, or the path convention. The formulation above uses the usual real affine, nonparallel and nonconcurrent, simple-path conventions and counts length in edges. These conventions require confirmation against the original source. The supplied record labels the problem open; that label and its literature assessment are supplied curation, not independently verified mathematical conclusions.

Short English statement

For every arrangement of $n$ red, $n$ blue, and $n$ green lines in general position, must there be a path through quadratically many distinct cells such that successive boundary crossings have different colors? The quadratic constants must be uniform over all such arrangements. The draft uses explicit conventional interpretations that require source review.

Sources

• Local UnsolvedMath registry, permanent ID $30002668$, title: Long Alternating Paths in Colored Line Arrangements; source problem code catalogue entry; collection: Oberwolfach Reports Open Problems. The supplied proposed year is 2014; no individual proposer is identified.
• Supplied source citation: Discrete Geometry (2015), Oberwolfach Reports, DOI 10.4171/owr/2014/40, pp. 2235--2296. https://doi.org/10.4171/owr/2014/40. The record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2015 label and the supplied 2014 proposed year are retained without independent bibliographic reconciliation.
• Supplied literature source, labeled "Oberwolfach report": https://ems.press/content/serial-article-files/46530.
• Supplied literature source, labeled "Hoffmann--Kleist--Miltzow, long dual paths": https://arxiv.org/abs/1506.03728.
• Supplied literature source, labeled "Aichholzer et al., cell paths in colored arrangements": https://doi.org/10.46298/dmtcs.2088.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that quadratic dual paths exist in uncolored arrangements, while known colored results give counterexamples or weaker bounds without settling this balanced three-color question. This is supplied dated literature triage derived from the OWR curation, not independently verified here; the status and cited claims require independent verification.
• The supplied statement status is corrected_verified. Its accompanying verification note reports only safe notation, typography, and TeX-delimiter cleanup, with hypotheses, quantifiers, and subquestions preserved. This metadata is not an independent mathematical verification of this draft.