For free Borel Z^d-grids, every grid has a Borel (2^d-1)-polychromatic coloring, while ergodic grids admit no Borel 2^d-polychromatic coloring, so the Borel threshold is 2^d-1.
Polychromatic Colorings of Unions of Geometric Hypergraphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider the polychromatic coloring problems for unions of two or more geometric hypergraphs on the same vertex sets of points in the plane. We show, inter alia, that the union of bottomless rectangles and horizontal strips does in general not allow for polychromatic colorings. This strengthens the corresponding result of Chen, Pach, Szegedy, and Tardos [Random Struct. Algorithms, 34:11-23, 2009] for axis-aligned rectangles, and gives the first explicit (not randomized) construction of non-$2$-colorable hypergraphs defined by axis-parallel rectangles of arbitrarily large uniformity.
citation-role summary
background 1
citation-polarity summary
fields
math.LO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Borel Polychromatic Number of Grids
For free Borel Z^d-grids, every grid has a Borel (2^d-1)-polychromatic coloring, while ergodic grids admit no Borel 2^d-polychromatic coloring, so the Borel threshold is 2^d-1.