Polychromatic Coloring of Tuples in Hypergraphs
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Miloš Stojaković · 2025
Read Polychromatic Coloring of Tuples in Hypergraphs by Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Miloš Stojaković (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22449.txt.
Introduction
Ahmad Biniaz and five co-authors bound how many points a region must hold before it contains small sets of every color, in a paper from 2025. Coloring tuples of points rather than single points is a fresh twist on classic polychromatic problems. Hypergraphs supply the general language.
For points in the plane with disks as regions, pairs can be colored so any disk with at least about 3.7 to the power k points holds pairs of all k colors. For abstract hypergraphs of bounded complexity, similar exponential bounds hold. They also prove deep tuples exist inside big hypergraphs and relate tuple coloring thresholds to ordinary vertex coloring ones.
Catalog record
| CREATOR | Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Miloš Stojaković |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22449
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Polychromatic Coloring of Tuples in Hypergraphs Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Miloš Stojaković Abstract A hypergraph H H consists of a set V V of vertices and a set E E of hyperedges that are subsets of V V . A t t - tuple of H H is a subset of t t vertices of V V . A t t -tuple k k - coloring of H H is a mapping of its t t -tuples into k k colors. A coloring is called ( t , k , f ) (t,k,f) - polychromatic if each hyperedge of E E that has at least f f vertices contains tuples of all the k k colors. Let f H ( t , k ) f_{H}(t,k) be the minimum f f such that H H has a ( t , k , f ) (t,k,f) -polychromatic coloring. For a family of hypergraphs ℋ \mathcal{H} let f ℋ ( t , k ) f_{\mathcal{H}}(t,k) be the maximum f H ( t , k ) f_{H}(t,k) over all hypergraphs H H in ℋ \mathcal{H} . Determining f ℋ ( t , k ) f_{\mathcal{H}}(t,k) has been an active research direction in recent years. This is challenging even for t = 1 t=1 . We present several new results in this direction for t ≥ 2 t\geq 2 . • Let ℋ \mathcal{H} be the family of hypergraphs H H that is obtained by taking any set P P of points in ℝ 2 \mathbb{R}^{2} , setting V := P V:=P and E := { d ∩ P : d is a disk in ℝ 2 } E:=\{d\cap P\colon d\text{ is a disk in }\mathbb{R}^{2}\} . We prove that f ℋ ( 2 , k ) ≤ 3.7 k f_{\mathcal{H}}(2,k)\leq 3.7^{k} , that is, the pairs of points (2-tuples) can be k k -colored such that any disk containing at least 3.7 k 3.7^{k} points has pairs of all colors. We generalize this result to points and balls in higher dimensions. • For the family ℋ \mathcal{H} of hypergraphs that are defined by grid vertices and axis-parallel rectangles in the plane, we show that f ℋ ( 2 , k ) ≤ c k ln k f_{\mathcal{H}}(2,k)\leq\sqrt{ck\ln k} for some constant c c . We then generalize this to higher dimensions, to other shapes, and to tuples of larger size. • For the family ℋ \mathcal{H} of shrinkable hypergraphs of VC-dimension at most d d we prove that f ℋ ( d + 1 , k ) ≤ c k f_{\mathcal{H}}(d{+}1,k)\leq c^{k} for some constant c = c ( d ) c=c(d) . Towards this bound, we obtain a result of independent interest: Every hypergraph with n n vertices and with VC-dimension at most d d has a ( d + 1 ) (d{+}1) -tuple T T of depth at least n c \frac{n}{c} , i.e., any hyperedge that contains T T also contains n c \frac{n}{c} other vertices. We also present analogous bounds for coloring pairs of points with respect to pseudo-disks in the plane. • For the relationship between t t -tuple coloring and vertex coloring in any hypergraph H H we establish the inequality 1 e ⋅ t k 1 t ≤ f H ( t , k ) ≤ f H ( 1 , t k 1 t ) \frac{1}{e}\cdot tk^{\frac{1}{t}}\leq f_{H}(t,k)\leq f_{H}(1,tk^{\frac{1}{t}}) . For the special case of k = 2 k=2 , referred to as the bichromatic coloring, we prove that t + 1 ≤ f H ( t , 2 ) ≤ max { f H ( 1 , 2 ) , t + 1 } t+1\leq f_{H}(t,2)\leq\max\{f_{H}(1,2),t+1\} ; this improves upon the previous best known upper bound. • We study the relationship between tuple coloring and epsilon nets. In particular we show that if f H ( 1 , k ) = O ( k ) f_{H}(1,k)=O(k) for a hypergraph H H with n n vertices, then for any 0 < ϵ < 1 0<\epsilon<1 the t t -tuples of H H can be partitioned into Ω ( ( ϵ n t ) t ) \Omega\left((\frac{\epsilon n}{t})^{t}\right) ϵ \epsilon - t t -nets. This bound is tight when t t is a constant. 1 Introduction Polychromatic coloring and cover-decomposition of hypergraphs have rich backgrounds. They have been studied for both abstract and geometric hypergraphs as early as 1980 (see, e.g., [ 39 , 40 , 42 , 43 ] ) and are still active research areas (see, e.g., [ 1 , 2 , 14 , 16 , 18 , 47 ] ). Perhaps the study of these topics gained more attention after a question of Pach [ 39 ] in 1980: 1 1 1 This is a dual form of the original question that is stated in terms of f -folds and coverings; see [ 44 ] . Does there exist a constant f such that every finite set of points in the plane can be colored with two colors in such a way that any unit disk that contains f points contains points of both colors? This question initiated the study of polychromatic coloring in geometric hypergraphs. Surprisingly enough, the answer to the question turned out to be negative, as it was proved in 2016 by Pach and Pálvölgyi [ 44 ] . In particular, they showed that for any natural number f , there is a finite set P of points in the plane such that for any 2 -coloring of P , one can find a unit disk containing at least f points of one color and no point of the other color. The same question can be asked for other convex bodies and for more than two colors: Given a convex body C and any natural number k\geq 2 , is there a function f\colon\mathbb{N}\mapsto\mathbb{N} such that any finite point set in the plane can be k -colored such that any translate of C that contains at least f(k) points, contains points of all the k colors? For instance, Pálvölgyi and Tóth [ 45 ] proved that f(k) exists when C is a convex polygon—it was shown later [ 8 , 26 ] that f(k)=O(k) . The negative answer of [ 44 ] to the original question of Pach implies that f(2) does not exist if C is a disk. More results and details in this direction can be found in the survey article by Pach, Pálvölgyi and Tóth [ 41 ] and the webpage maintained by Keszegh and Pálvölgyi [ 30 ] . The containment of points in disks (and other convex bodies) can be represented by geometric hypergraphs, also known as range spaces. A hypergraph H=(V,E) consists of a set V of vertices and a set E of hyperedges that are subsets of V . A (possibly infinite) set of hypergraphs is called a family of hypergraphs. Let f_{\mathcal{H}}(k) be the smallest natural number such that the vertices of any hypergraph H in \mathcal{H} can be k -colored such