Conflict-Free Chromatic Numbers of Rectangle Hypergraphs

Definitions and mathematical statement

For a hypergraph $H=(V,\mathcal E)$, a conflict-free coloring with $q$ colors is a map $c:V\to\{1,\ldots,q\}$ such that every nonempty hyperedge $E\in\mathcal E$ contains a color occurring exactly once: \[ \forall E\in\mathcal E\ (E\ne\varnothing)\quad \exists v\in E\quad \forall w\in E\setminus\{v\},\ c(w)\ne c(v). \] The conflict-free chromatic number $\chi_{\mathrm{cf}}(H)$ is the least such $q$.

The source asks for the best possible asymptotic upper bound when the geometric hypergraph is formed by $n$ axis-parallel rectangles in the plane. It does not define the vertices and hyperedges. Under the customary dual incidence interpretation, for an indexed family $\mathcal R=(R_1,\ldots,R_n)$, put \[ H(\mathcal R)=\left(\{1,\ldots,n\},\{E_x:x\in\bigcup_iR_i\}\right), \qquad E_x=\{i:x\in R_i\}. \] Then one colors rectangles so that at each covered point some covering rectangle has a uniquely occurring color. In that interpretation the target is the asymptotic order, as $n\to\infty$, of \[ F(n)=\max_{\mathcal R\text{ a family of }n\text{ axis-parallel rectangles}} \chi_{\mathrm{cf}}(H(\mathcal R)). \] A best possible upper bound is understood in a worst-case sense over the allowed families, with sharpness requiring matching examples at the intended asymptotic scale.

This dual interpretation is explicitly provisional. A primal range hypergraph colors points and uses rectangle intersections with a point set as hyperedges, and other rectangle-incidence constructions are possible. The record does not select among them or specify boundary and degeneracy conventions. No particular known bound or proposed exponent is supplied, so none is asserted.

Short English statement

Determine the optimal worst-case asymptotic number of colors for conflict-free coloring of the intended rectangle hypergraphs. The usual rectangle-coloring incidence model is displayed, but the source does not define its hyperedges.

Sources

• Local UnsolvedMath registry, permanent ID $30001057$, source code catalogue entry, "Conflict-Free Chromatic Numbers of Rectangle Hypergraphs." No individual proposer is supplied.
• Discrete Geometry (2009), Oberwolfach Reports, DOI 10.4171/owr/2008/44, pp. 2477--2556, listed in the literature sources as "Tardos report": https://doi.org/10.4171/owr/2008/44.
• Supplied reference, "Keszegh": https://doi.org/10.1016/j.comgeo.2011.09.004.
• Supplied literature triage, checked 2026-08-21: status "open." It reports the optimum explicitly open in the source and later bounds and variants without the requested optimum. Exact bounds and variant hypotheses are absent. This is supplied dated curation, not independently verified; time-sensitive status and cited claims require independent verification.