Shift Chain Colorings and Disk Covering Paths

Definitions and mathematical statement

Shift-chain coloring. Let $k\geq 1$ be an integer and let $(V,<)$ be a linearly ordered vertex set. A $k$-uniform hypergraph is a pair $H=(V,E)$, where every $e\in E$ is a $k$-element subset of $V$. Write each edge uniquely as $e=\{e_1<\cdots<e_k\}$. The hypergraph is a shift-chain if, for every $e,f\in E$, \[ \left(e_i\leq f_i\text{ for every }1\leq i\leq k\right) \quad\text{or}\quad \left(f_i\leq e_i\text{ for every }1\leq i\leq k\right). \] A proper two-coloring is a map $\chi:V\to\{0,1\}$ such that every edge contains vertices of both colors.

The question asks whether there exists an integer $k_0\geq 1$ such that, for every integer $k\geq k_0$, every $k$-uniform shift-chain has a proper two-coloring. The supplied record does not specify whether only finite vertex sets are intended or whether arbitrary linearly ordered vertex sets are allowed. These are distinct scope choices, and neither is selected here as the definitive formulation.

Paths in a doubly covered region. Let $\mathcal D$ be a family of closed Euclidean unit discs covering ${\mathbb{R}}^2$; thus every member has the form \[ \overline B(a,1)=\{x\in{\mathbb{R}}^2:\|x-a\|_2\leq 1\}, \qquad a\in{\mathbb{R}}^2, \] and $\bigcup_{D\in\mathcal D}D={\mathbb{R}}^2$. Define its doubly covered region by \[ T(\mathcal D)=\{x\in{\mathbb{R}}^2:x\text{ belongs to at least two members of }\mathcal D\}. \] The literal corrected question asks whether there exists a universal constant $c\geq 0$ such that, for every such covering $\mathcal D$ and every $p,q\in{\mathbb{R}}^2$, there is a rectifiable continuous path $\gamma:[0,1]\to{\mathbb{R}}^2$ satisfying \[ \gamma(0)=p,\qquad \gamma(1)=q,\qquad \gamma([0,1])\subseteq T(\mathcal D),\qquad \operatorname{length}(\gamma)\leq\sqrt{2}\,\|p-q\|_2+c. \] Here the same $c$ must work for all coverings and all endpoint pairs, including coincident endpoints. Containment of the entire path forces both endpoints to belong to $T(\mathcal D)$, whereas the supplied statement says any two points without imposing that restriction. It is unresolved whether the intended quantifier is instead $p,q\in T(\mathcal D)$, or whether another endpoint convention or covering hypothesis is missing. No local finiteness assumption is supplied.

The original statement gives the coefficient $2$ in place of $\sqrt{2}$. The supplied corrected statement and its verification note explicitly identify $\sqrt{2}$ as the restored coefficient; that is the coefficient displayed above. This records the supplied correction without independently validating it.

Short English statement

The first question asks whether all shift-chains admit a coloring with no monochromatic edge once the edge size is sufficiently large; the intended size class of vertex sets is unspecified. The second asks for a universal additive constant in a $\sqrt{2}\,d+c$ bound for paths through the doubly covered part of a closed-unit-disc covering. Its endpoint quantifiers require clarification. The supplied record labels the combined problem partially solved; this draft does not independently verify that assessment.

Sources

• Local UnsolvedMath registry, data/unsolvedmath/problems.json, permanent ID $30001896$, source problem code catalogue entry, title: Shift Chain Colorings and Disk Covering Paths. The supplied collection is Oberwolfach Reports Open Problems. The proposed year is recorded as $2011$; no individual proposer is supplied.
• Supplied report citation: Discrete Geometry (2012), Oberwolfach Reports, pp. 2459--2548, DOI 10.4171/owr/2011/44. Supplied source URL: https://doi.org/10.4171/owr/2011/44. The background attributes the problems to mathematical workshop discussions documented in Oberwolfach Reports.
• Supplied literature source: OWR 44 (2012), https://doi.org/10.4171/owr/2011/44. Literature checked at: 2026-08-21. This is supplied dated curation, not an independently verified literature assessment. It labels the status partially solved and states that the shift-chain question remains unresolved beyond small counterexamples and restricted positive cases, while the doubly-covered-disc path problem has improved bounds and lattice-covering cases. The supplied background explicitly calls for independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified. Its verification note says that the official report was checked and that the shift-chain definition and square-root path-length coefficient were restored. This is a statement about the supplied verification record; no independent source visit or verification is claimed here.