Polychromatic Coloring of Tuples in Hypergraphs

Biniaz, Ahmad; De Carufel, Jean-Lou; Maheshwari, Anil; Smid, Michiel; Smorodinsky, Shakhar; Stojaković, Miloš

doi:10.4230/LIPIcs.SoCG.2025.19

Polychromatic Coloring of Tuples in Hypergraphs

Ahmad Biniaz

School of Computer Science, University of Windsor, Canada Jean-Lou De Carufel

School of Electrical Engineering and Computer Science, University of Ottawa, Canada Anil Maheshwari

School of Computer Science, Carleton University, Ottawa, Canada Michiel Smid

School of Computer Science, Carleton University, Ottawa, Canada Shakhar Smorodinsky

Department of Computer Science, Ben-Gurion University of the Negev, Be’er Sheva, Israel Miloš Stojaković

Department of Mathematics and Informatics, University of Novi Sad, Serbia

Abstract

A hypergraph $H$ consists of a set $V$ of vertices and a set $E$ of hyperedges that are subsets of $V$ . A $t$ -tuple of $H$ is a subset of $t$ vertices of $V$ . A $t$ -tuple $k$ -coloring of $H$ is a mapping of its $t$ -tuples into $k$ colors. A coloring is called $(t,k,f)$ -polychromatic if each hyperedge of $E$ that has at least $f$ vertices contains tuples of all the $k$ colors. Let $f_{H}(t,k)$ be the minimum $f$ such that $H$ has a $(t,k,f)$ -polychromatic coloring. For a family of hypergraphs $\mathcal{H}$ let $f_{\mathcal{H}}(t,k)$ be the maximum $f_{H}(t,k)$ over all hypergraphs $H$ in $\mathcal{H}$ . Determining $f_{\mathcal{H}}(t,k)$ has been an active research direction in recent years. This is challenging even for $t=1$ . We present several new results in this direction for $t\geq 2$ .

$\blacksquare$

Let $\mathcal{H}$ be the family of hypergraphs $H$ that is obtained by taking any set $P$ of points in $\mathbb{R}^{2}$ , setting $V:=P$ and $E:=\{d\cap P\colon d\text{ is a disk in }\mathbb{R}^{2}\}$ . We prove that $f_{\mathcal{H}}(2,k)\leq 3.7^{k}$ , that is, the pairs of points (2-tuples) can be $k$ -colored such that any disk containing at least $3.7^{k}$ points has pairs of all colors. We generalize this result to points and balls in higher dimensions.
$\blacksquare$

For the family $\mathcal{H}$ of hypergraphs that are defined by grid vertices and axis-parallel rectangles in the plane, we show that $f_{\mathcal{H}}(2,k)\leq\sqrt{ck\ln k}$ for some constant $c$ . We then generalize this to higher dimensions, to other shapes, and to tuples of larger size.
$\blacksquare$

For the family $\mathcal{H}$ of shrinkable hypergraphs of VC-dimension at most $d$ we prove that $f_{\mathcal{H}}(d{+}1,k)\leq c^{k}$ for some constant $c=c(d)$ . Towards this bound, we obtain a result of independent interest: Every hypergraph with $n$ vertices and with VC-dimension at most $d$ has a $(d{+}1)$ -tuple $T$ of depth at least $\frac{n}{c}$ , i.e., any hyperedge that contains $T$ also contains $\frac{n}{c}$ other vertices.
$\blacksquare$

For the relationship between $t$ -tuple coloring and vertex coloring in any hypergraph $H$ we establish the inequality $\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$ , referred to as the bichromatic coloring, we prove that $t+1\leq f_{H}(t,2)\leq\max\{f_{H}(1,2),t+1\}$ ; this improves upon the previous best known upper bound.
$\blacksquare$

We study the relationship between tuple coloring and epsilon nets. In particular we show that if $f_{H}(1,k)=O(k)$ for a hypergraph $H$ with $n$ vertices, then for any $0<\epsilon<1$ the $t$ -tuples of $H$ can be partitioned into $\Omega\left((\frac{\epsilon n}{t})^{t}\right)$ $\epsilon$ - $t$ -nets. This bound is tight when $t$ is a constant.

Keywords and phrases:

Hypergraph Coloring, Polychromatic Coloring, Geometric Hypergraphs, Cover Decomposable Hypergraphs, Epsilon Nets

Funding:

Ahmad Biniaz: Supported in part by NSERC.

Jean-Lou De Carufel: Supported in part by NSERC.

Anil Maheshwari: Supported in part by NSERC.

Michiel Smid: Supported in part by NSERC.

Shakhar Smorodinsky: Partially supported by Grant 1065/20 from the Israel Science Foundation, by the United States – Israel Binational Science Foundation (NSF-BSF grant no. 2022792) and by ERC grant no. 882971 “GeoScape” and by the Erdős Center.

Miloš Stojaković: Partly supported by Ministry of Science, Technological Development and Innovation of Republic of Serbia (Grants 451-03-137/2025-03/200125 & 451-03-136/2025-03/200125). Partly supported by Provincial Secretariat for Higher Education and Scientific Research, Province of Vojvodina (Grant No. 142-451-2686/2021).

Copyright and License:

© Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar
Smorodinsky, and Miloš Stojaković; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Related Version:

Full Version: https://arxiv.org/abs/2503.22449 [12]

Acknowledgements:

This work was initiated at the 20th Gremo’s Workshop on Open Problems, held in Wergenstein, Switzerland, in June 2023. It was then continued at the 11th Annual Workshop on Geometry and Graphs, held at the Bellairs Research Institute in Holetown, Barbados, in March 2024. We thank the organizers and participants of both workshops. We also thank the reviewers of SoCG 2025 who verified our proofs and provided valuable feedback.

DOI:

10.4230/LIPIcs.SoCG.2025.19

Event:

41st International Symposium on Computational Geometry (SoCG 2025)

Editors:

Oswin Aichholzer and Haitao Wang

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

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, 46]). Perhaps the study of these topics gained more attention after a question of Pach [39] in 1980:¹¹1This 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 that any hyperedge of $H$ that has at least $f_{\mathcal{H}}(k)$ vertices contains points of all colors. If no such number exists, then $f_{\mathcal{H}}(k):=\infty$ . If $f_{\mathcal{H}}(2)$ exists, then $\mathcal{H}$ is called cover-decomposable – a term that Pach introduced for $k=2$ .

Determining $f_{\mathcal{H}}(k)$ is an active research direction in both abstract and geometric hypergraphs; see e.g. [2, 14, 16, 17, 18, 20] and the references therein. Geometric hypergraphs, in particular, have received special attention. These hypergraphs are typically defined by points and convex bodies in some fixed constant dimension. For instance, let $C$ be a convex body in $\mathbb{R}^{2}$ and let $\mathcal{H}$ be the family of all hypergraphs $H$ that is obtained by taking any set $P$ of points in $\mathbb{R}^{2}$ , setting $V:=P$ and $E:=\{C^{\prime}\cap P\colon C^{\prime}\text{ is a translate of }C\}$ . As mentioned above, if $C$ is a disk then $f_{\mathcal{H}}(2)$ does not exist and hence $\mathcal{H}$ is not cover-decomposable [44], and if $C$ is a convex polygon then $f_{\mathcal{H}}(2)$ exists and $\mathcal{H}$ is cover-decomposable [45]. Finding $f_{\mathcal{H}}(k)$ could be more challenging if we could scale or rotate the convex body. For example if $C$ is the family of axis-parallel squares then $f_{\mathcal{H}}(2)\leq 215$ [2], and if $C$ is the family of axis-parallel rectangles then $f_{\mathcal{H}}(2)$ does not exist [21].

A natural question thus arises: For hypergraphs that are not cover-decomposable with respect to the coloring of vertices, such as those defined by disks and axis-parallel rectangles, can we prove a positive result when we color subsets rather then the vertices? This leads to a natural generalization of the problem: color pairs, triples, or tuples of points. This generalization is referred to as tuple coloring. Let $H=(V,E)$ be a hypergraph. For a natural number $t$ , a $t$ -tuple of $H$ is a subset of $t$ vertices of $V$ . The number of $t$ -tuples of $H$ is $\binom{|V|}{t}$ . A $t$ -tuple $k$ -coloring of $H$ is mapping of its $t$ -tuples into $k$ colors. For $t=1$ , this is equivalent to vertex coloring. A coloring is called $(t,k,f)$ -polychromatic if each hyperedge of $E$ that has at least $f$ vertices contains tuples of all the $k$ colors. Let $f_{H}(t,k)$ denote the least integer $f$ such that $H$ has a $(t,k,f)$ -polychromatic coloring. For a hypergraph family $\mathcal{H}$ let $f_{\mathcal{H}}(t,k)$ denote the maximum $f_{H}(t,k)$ over all hypergraphs $H$ in $\mathcal{H}$ . In other words, $f_{\mathcal{H}}(t,k)$ is the minimum number for which every hypergraph in $\mathcal{H}$ has a $(t,k,f_{\mathcal{H}}(t,k))$ -polychromatic coloring. For the standard vertex coloring, where $t=1$ , the value $f_{\mathcal{H}}(1,k)$ is equal to $f_{\mathcal{H}}(k)$ as defined above. With this definition, $\mathcal{H}$ is cover-decomposable if $f_{\mathcal{H}}(1,2)$ exists. The family $\mathcal{H}$ is called $t$ -cover-decomposable, for $t\geq 2$ , if $f_{\mathcal{H}}(t,2)$ exists.

1.1 Other related results

There is a rich literature for vertex-coloring (i.e. when $t=1$ ) of geometric hypergraphs. In these hypergraphs, the vertices are usually defined by points and the hyperedges are defined by geometric shapes such as disks, rectangles, squares, bottomless rectangles, strips, quadrants, triangles, octants, and halfplanes; see, for example [2, 7, 8, 10, 16, 20, 21, 26, 31, 44, 45] and a recent article by Planken and Ueckerdt [46] that gives a summary of the results.

For $t\geq 2$ , coloring $t$ -tuples in hypergraphs is closely related to Ramsey-type problems (see [35] for Ramsey problems in hypergraphs). In particular, it follows from Ramsey’s theorem that for any two natural numbers $t$ and $d$ , where $t\leq d$ , the family of complete $d$ -uniform hypergraphs is not $t$ -cover-decomposable, i.e., $f_{\mathcal{H}}(t,2)$ is unbounded.

A recent work of Ackerman, Keszegh, and Pálvölgyi [1] is devoted to determining $f_{\mathcal{H}}(t,k)$ for $t\geq 2$ in geometric hypergraphs that are defined by halfspaces, pseudo-disks, and boxes. In particular, for the family $\mathcal{H}$ of hypergraphs that are defined by points and axis-parallel boxes in dimension $d\geq 2$ they show that $f_{\mathcal{H}}(t,k)\leq k^{2^{d-1}}+t-1$ when $t\geq 2$ (to better appreciate this bound we shall recall that $f_{\mathcal{H}}(t,k)$ is unbounded when $t=1$ , as shown in [21]). From this result it follows that for the family $\mathcal{H}$ of hypergraphs that are defined by points and homothets²²2A homothet of an object is obtained by translating and scaling the object. of a fixed convex polytope with $h$ facets in some dimension it holds that $f_{\mathcal{H}}(t,k)\leq k^{2^{h-1}}+t-1$ [1].

1.2 Preliminaries

When the family or hypergraphs or a particular hypergraph is clear from the context we may drop the subscript and simply write $f(t,k)$ for $f_{\mathcal{H}}(t,k)$ and $f_{H}(t,k)$ . First we define the notion of shrinkability which is a common property of many geometric hypergraphs.

Definition 1.1 (Shrinkability).

A hypergraph $H$ is shrinkable if for every hyperedge $e\in H$ and for every integer $1\leq i\leq|e|$ there exists a hyperedge $e^{\prime}$ in $H$ such that $e^{\prime}\subseteq e$ and $|e^{\prime}|=i$ .

The VC-dimension of a hypergraph is a measure of its complexity, and it plays a central role in statistical learning, computational geometry, and other areas of computer science and combinatorics (see, e.g., [4, 13, 33, 36]).

Definition 1.2 (VC-dimension).

The VC-dimension of a hypergraph $H=(V,E)$ is the size of the largest subset $S\subseteq V$ such that for every subset $B\subseteq S$ there is a hyperedge $e\in E$ where $e\cap S=B$ . Such a subset $S$ is said to be “shattered” by $H$ .

The following inequality, usually referred to as the Sauer-Shelah-Perles lemma [15, 48, 50], relates the number of vertices and hyperedges of a hypergraph of VC-dimension $d$ :

|E|\leq\sum_{i=0}^{d}{\binom{|V|}{i}}.

For a hypergraph $H=(V,E)$ and a subset $X\subseteq V$ the projection of $H$ to $X$ is the hypergraph $H[X]=(X,\{e\cap X\colon e\in E\})$ . The VC-dimension of $H[X]$ is, at most, the VC-dimension of $H$ because any subset that is shattered by $H[X]$ is also shattered by $H$ .

Let $P$ be a set of points in the plane. The depth of a pair $\{x,y\}$ of points in $P$ , denoted by $d_{P}(x,y)$ , is defined as the maximum integer $i$ such that any disk containing $x$ and $y$ contains at least $i$ other points of $P$ . Notice that $0\leq d_{P}(x,y)\leq|P|-2$ . The existence of pairs of large depth (also known as deep pairs) is studied in [11, 24, 28, 29, 38, 47]. The notion of depth can be generalized to tuples of points and to higher dimensions as the maximum number $i$ such that any ball containing a deep tuple also contains $i$ other points. We extend the notion of depth further into hypergraphs.

Definition 1.3 (Depth).

Let $H=(V,E)$ be a hypergraph and $S$ be a subset of $V$ . The depth $d_{H}(S)$ of $S$ is defined as the maximum integer such that for every hyperedge $e\in E$ that contains $S$ , we have $|e{\setminus}S|\geq d_{H}(S)$ . If no hyperedge contains $S$ then $d_{H}(S):=|V{\setminus}S|.$

Note that if $S$ has depth $i$ , then in particular every hyperedge that contains $S$ contains at least $i$ other vertices. The notion of depth is monotone with respect to projections, in the sense that for any $X\subseteq V$ , we have $d_{H[X]}(S)\leq d_{H}(S)$ .

Let $H$ be a hypergraph and $0<\epsilon<1$ be a real number. A subset $S$ of vertices is called an $\epsilon$ -net for $H$ if any hyperedge $e$ of size at least $\epsilon|V|$ contains a vertex from $S$ . This notion was introduced by Haussler and Welzl [27]. It was then generalized by Mustafa and Ray [37] to tuples and appears under $\epsilon$ - $t$ -nets; see also [5, 23].

Definition 1.4 ( $\epsilon$ - $t$ -Net).

Let $H=(V,E)$ be a hypergraph, $\epsilon\in(0,1)$ be a real number, and $t$ be a natural number. A subset $N$ of $t$ -tuples of $V$ is called an $\epsilon$ - $t$ -net if any hyperedge $e$ in $E$ of size at least $\epsilon|V|$ contains at least one of the $t$ -tuples in $N$ .

1.3 Our contributions

We present upper bounds on $f(t,k)$ for several families of geometric hypergraphs and hypergraphs of bounded VC-dimension. Some of our bounds are new, and some improve over previously known bounds. These bounds are interesting because, for abstract hypergraphs, $f(t,k)$ is unbounded even if the hypergraph is uniform and $k=2$ (due to Ramsey’s theorem; see [35]). We also study the relationship between vertex-coloring, tuple-coloring, cover-decomposability, and epsilon $t$ -nets.

Recall that $f(t,2)$ , with $t=1$ , is unbounded for hypergraphs that are defined by points and disks in the plane [44] . We prove, however, that it is bounded for $t=2$ . A point set $P$ in dimension $d$ is said to be in general position if no $(d+2)$ points of $P$ lie on a sphere.

Theorem 1.5.

Let $\mathcal{H}$ be the family that contains any hypergraph $H$ that can be obtained by taking a finite set $P$ of points in $\mathbb{R}^{2}$ in general position setting $V(H):=P$ and $E(H):=\{d\cap P:\text{$d$ is a disk in $\mathbb{R}^{2}$}\}$ . Then for any natural number $k$ it holds that $f_{\mathcal{H}}(2,k)\leq 3.7^{k}$ .

In other words, for any finite set $P$ of points in the plane, the $\binom{|P|}{2}$ pairs of points can be $k$ -colored such that any disk containing at least $3.7^{k}$ points must also contain a pair (of points) from each of the $k$ color classes. To obtain this bound, we show some properties of containment of points in disks and also employ a result about the depth of pairs of points – a well-studied topic in discrete and computational geometry [24, 47]. We then generalize this result to tuples and balls in higher dimensions. The parameter $e$ below denotes Euler’s number.

Theorem 1.6.

Let $d\geq 3$ be an integer and set $t:=\lfloor\frac{d+3}{2}\rfloor$ . Let $\mathcal{H}$ be the family of all hypergraphs $H$ that can be obtained by taking a finite set $P$ of points in $\mathbb{R}^{d}$ in general position setting $V(H):=P$ and $E(H):=\{b\cap P:\text{$b$ is a ball in $\mathbb{R}^{d}$}\}$ . Then for any natural number $k$ it holds that $f_{\mathcal{H}}(t,k)\leq\left(\frac{4}{5ed^{3}}\right)^{k}$ .

For points and axis-parallel rectangles in the plane, we know from [21] that $f(t,2)$ is unbounded when $t=1$ . However for $t=2$ a result of [1] implies that $f(2,k)\leq k^{2}+1$ . We study the same problem but for grid points.

Theorem 1.7.

Let $\mathcal{H}$ be the family of all hypergraphs $H$ that can be obtained by taking the vertex set $P$ of a regular grid in $\mathbb{R}^{2}$ setting $V(H){:=}P$ and $E(H){:=}\{r\cap P:r$ is an axis-parallel rectangle in $\mathbb{R}^{2}\}$ . Then for any natural number $k\geq 2$ it holds that $f_{\mathcal{H}}(2,k)\leq\sqrt{ck\ln k}$ , for some constant $c\geq 126$ .

To better appreciate this bound, observe that $f(2,k)=\Omega(\sqrt{k})$ for any hypergraph (see also Section 5). Theorem 1.8 (proven in the full version of the paper [12]) generalizes this result.

Theorem 1.8.

Let $\mathcal{H}$ be the family of all hypergraphs that can be obtained by grid points and boxes (or balls) in any fixed dimension $d\geq 2$ . Then for any natural numbers $t\geq 1$ and $k\geq 2$ it holds that $f_{\mathcal{H}}(t,k)=O\left(\left(k\ln k\right)^{1/t}\right)$ .

We also study hypergraphs of bounded VC-dimension.

Theorem 1.9.

For every shrinkable hypergraph $H$ with VC-dimension at least 2 and at most $d$ and with $n\geq 2d+2$ vertices it holds that $f_{H}(d+1,k)\leq c^{k-1}$ for any $k\geq 1$ and any $c\geq 4(d+1)^{d+1}$ .

This result applies to many families of geometric hypergraphs. For example, hypergraphs defined by points and halfspaces, boxes, or balls in $\mathbb{R}^{d}$ are shrinkable and have bounded VC dimensions. Along with a proof of this result, we show the existence of a tuple of large depth in hypergraphs of bounded VC-dimension, which is of independent interest.

Theorem 1.10.

For every hypergraph $H$ with VC-dimension at least 2 and at most $d$ and with $n\geq 2d+2$ vertices there exists a $(d+1)$ -tuple $T$ of vertices such that $d_{H}(T)\geq\frac{n}{c}$ , for $c=4(d+1)^{d+1}$ .

For hypergraphs where $f(1,x)$ is linear in $x$ , we prove the following asymptotic tight bounds for their tuple-coloring and for decomposition of their tuples into epsilon $t$ -nets.

Theorem 1.11.

Let $H$ be a hypergraph for which $f_{H}(1,x)=O(x)$ , for any $x\geq 1$ . Then for any natural numbers $t$ and $k$ with $tk^{1/t}\geq 1$ we have $f_{H}(t,k)=\Theta(tk^{\frac{1}{t}}).$

Theorem 1.12.

Let $H$ be a hypergraph with $n$ vertices such that $f_{H}(1,x)=O(x)$ , for any $x\geq 1$ . Then for any $0<\epsilon<1$ and any $t\geq 1$ the $t$ -tuples of vertices of $H$ can be decomposed into $\Omega\left((\frac{\epsilon n}{t})^{t}\right)$ pairwise disjoint $\epsilon$ - $t$ -nets for $H$ . This bound is asymptotically tight when $t$ is a constant.

For an implication of Theorem 1.11 consider the family $\mathcal{H}$ of hypergraphs that are defined by points and halfplanes in $\mathbb{R}^{2}$ . From a result of Smorodinsky and Yuditsky [52] we know that $f_{\mathcal{H}}(1,x)\leq 2x{-}1$ , i.e., any set of points in the plane can be colored by $x$ colors such that any halfplane containing at least $2x{-}1$ points contains points of all colors. Therefore, Theorem 1.11 implies that $f_{\mathcal{H}}(t,k)=\Theta(tk^{\frac{1}{t}})$ .

Finally, we study the relationship between $f(1,k)$ and $f(t,k)$ for $k=2$ , which is usually referred to as bichromatic coloring. It is implied from a result of Ackerman, Keszegh, and Pálvölgyi [1, Proposition 4] that $f_{H}=(t,2)\leq\max\{f_{H}(1,2),2t-1\}$ for any family $H$ and any $t\geq 2$ . We present the following improved upper bound.

Theorem 1.13.

For any hypergraph $H$ and any integer $t\geq 2$ it holds that

t+1\leq f_{H}(t,2)\leq\max\{f_{H}(1,2),t+1\}.

The matching term $t+1$ in the lower and upper bounds of Theorem 1.13 determines the exact value of $f(t,2)$ for some classes of hypergraphs. For instance, when $H$ is defined by points and halfplanes in $\mathbb{R}^{2}$ , the result of Smorodinsky and Yuditsky [52] gives $f_{H}(1,2)=3$ , and thus Theorem 1.13 implies the following corollary.

Corollary 1.14.

Let $t\geq 2$ be an integer. For the family $\mathcal{H}$ of hypergraphs that are defined by points and halfplanes in $\mathbb{R}^{2}$ , it holds that $f_{\mathcal{H}}(t,2)=t+1$ .

2 Coloring Tuples of Points with respect to Disks and Balls

In this section, we prove Theorem 1.5 and Theorem 1.6. Our proofs relies on some simple structural properties of the containment of points in disks and balls. They also employ some results about the existence of deep tuples in point sets. Without loss of generality, all point sets that are considered in this section are assumed to be in general position.

2.1 Points and disks in $\mathbb{R}^{2}$

Let $\mathcal{H}$ be the family of hypergraphs defined by points and disks in the plane. That is, $\mathcal{H}$ contains any hypergraph $H$ that can be obtained by taking a finite set $P$ of points in $\mathbb{R}^{2}$ setting $V(H):=P$ and $E(H):=\{d\cap P:\text{$d$ is a disk in $\mathbb{R}^{2}$}\}$ . In this section we prove that $f_{\mathcal{H}}(2,k)\leq 3.7^{k}$ . We say that a disk $d$ contains a point $p$ if $p$ is in the interior or on the boundary of $d$ . Alternatively, we say that $p$ is in $d$ .

One part of our proof employs the following result of Ramos and Viaña [47]; this is a stronger version of a result that previously appeared in [24].

Lemma 2.1 (Ramos and Viaña [47]).

In any set of $n$ points in the plane, there is a pair of points such that any circle through them has, both inside and outside, at least $\frac{n}{4.7}$ points (excluding the two points themselves).

This result is obtained by using the duality (of circles in $\mathbb{R}^{2}$ and planes in $\mathbb{R}^{3}$ ) and some known results on facets of points in $\mathbb{R}^{3}$ . The pair that is obtained by Lemma 2.1 has the property that any circle through them has at least $\frac{n}{4.7}$ and at most $n{-}\frac{n}{4.7}{-}2$ points inside. Combining this with the notion of depth, we get the following corollary.

Corollary 2.2.

In any set of $n$ points in the plane there is a pair $\{x,y\}$ such that

\frac{n}{4.7}\leq d_{P}(x,y)<\frac{3.7n}{4.7}.

The following lemmas, though very simple, play important roles in our proof. We denote the boundary circle of a disk $D$ by $\partial D$ .

Figure 1: (a) Shrinking

D

to lose

q

. (b) Enlarging

D

along the ray from

q

to

c

.

Lemma 2.3.

Let $P$ be a finite set of points in the plane and let $D$ be a disk with $|D\cap P|=j$ for some $j\geq 1$ . There exists a disk $D^{\prime}$ such that $(D^{\prime}\cap P)\subseteq D$ and $|D^{\prime}\cap P|=j-1$ .

Proof.

Fix $D$ at its center $c$ and shrink it until a point $q\in P$ appears on $\partial D$ for the first time. If $q$ is the only point of $P$ on $\partial D$ , we shrink $D$ slightly to lose $q$ , as in Figure 1(a). Assume that there are other points of $P$ on $\partial D$ . Fix $D$ at $q$ and enlarge it slightly along the ray from $q$ to $c$ such that all other points on $\partial D$ fall inside $D$ and no new point appears in $D$ , as in Figure 1(b). Now, $q$ is the only point on $\partial D$ . Again, we fix $D$ at the center of the new disk and shrink it slightly to lose $q$ . $\hfill\blacktriangleleft$

By repeatedly applying Lemma 2.3, one can shrink/enlarge a disk $D$ to lose 1, 2, 3, or more points of $P$ . Therefore, we get the following more general lemma.

Lemma 2.4.

Let $P$ be a finite set of points and $D$ be a disk with $|D\cap P|=j$ . For any integer $0\leq i\leq j$ there exists a disk $D^{\prime}$ such that $(D^{\prime}\cap P)\subseteq D$ and $|D^{\prime}\cap P|=i$ .

Lemma 2.5.

Let $D$ be a disk and $x, y$ be two points in the interior of $D$ . There exists a disk that is contained in the interior of $D$ such that its boundary passes through $x$ and $y$ .

Proof.

Fix $D$ at its center $c$ and shrink it until a point, say $x$ , appears on $\partial D$ for the first time. Then fix $D$ at $x$ and shrink it along the segment $c x$ until $y$ appears on $\partial D$ . This disk satisfies the constraints of the lemma. $\hfill\blacktriangleleft$

Lemma 2.6.

Let $P$ be a finite set of points in the plane, and let $S$ be a subset of $P$ . Then for any pair $\{x,y\}$ in $S$ it holds that $d_{S}(x,y)\leq d_{P}(x,y)$ .

Proof.

This is true because for any disk $D$ in the plane, the number of points of $P$ in $D$ is at least the number of points of $S$ in $D$ . $\hfill\blacktriangleleft$

We are ready for the proof of Theorem 1.5.

Proof of Theorem 1.5.

Consider any hypergraph $H$ in $\mathcal{H}$ with vertex set $P$ . We color each pair $\{x,y\}$ of points in $P$ with one of the $k$ colors $\{0,1,\ldots,k-1\}$ as follows:

\text{color of }\{x,y\}=\begin{cases}0&\quad\text{if }d_{P}(x,y)=0\\ i+1&\quad\text{if }3.7^{i}\leq d_{P}(x,y)<3.7^{i{+}1}\text{ for some }i\in\{0,% 1,\ldots,k-3\}\\ k-1&\quad\text{if }d_{P}(x,y)\geq 3.7^{k{-}2}.\end{cases}

We prove that any disk $D$ containing at least $3.7^{k}$ points has pairs of all the $k$ colors.

By an application of Lemma 2.4 there is a disk $D_{0}$ such that $(D_{0}\cap P)\subseteq D$ and $|D_{0}\cap P|=2$ . The two points in $D_{0}$ have depth 0 and thus are colored 0.

Figure 2: Illustration of the proof of Theorem 1.5.

For each $i\in\{0,\ldots,k-2\}$ , we show that there is a pair of points with color $i{+}1$ in $D$ . Let $D_{i}$ be a disk such that $(D_{i}\cap P)\subseteq D$ and $|D_{i}\cap P|=4.7\cdot 3.7^{i}$ (such a disk exists by Lemma 2.4 and the fact that $4.7\cdot 3.7^{i}<3.7^{k}\leq|D\cap P|$ ). Let $P^{\prime}$ be the set of points in $D_{i}$ . See Figure 2. By Corollary 2.2 the set $P^{\prime}$ contains a pair $\{x,y\}$ such that any disk through them has at least $\frac{|P^{\prime}|}{4.7}=3.7^{i}$ and at most $\frac{3.7|P^{\prime}|}{4.7}-2=3.7^{i{+}1}-2$ points of $P^{\prime}$ inside. Thus $3.7^{i}\leq d_{P^{\prime}}(x,y)<3.7^{i{+}1}$ . We argue that these bounds also hold with respect to $P$ , that is $3.7^{i}\leq d_{P}(x,y)<3.7^{i{+}1}$ . The lower bound is implied from Lemma 2.6 because $d_{P^{\prime}}(x,y)\leq d_{P}(x,y)$ . To verify the upper bound, we take an arbitrary disk $D_{xy}$ through $x$ and $y$ in the interior of $D_{i}$ (such a disk exists by Lemma 2.5). The disk $D_{xy}$ contains at most $3.7^{i{+}1}$ points of $P^{\prime}$ . Since $D_{xy}$ does not contain any point outside $D$ , it has at most $3.7^{i{+}1}$ points of $P$ . This verifies the upper bound on $d_{P}(x,y)$ . Therefore, the pair $\{x,y\}$ has color $i{+}1$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark.

To assist the readability of the proof of Theorem 1.5 we avoided rounding when applying Lemma 2.4; this has a negligible impact on the proof. The disk $D_{i}$ would be chosen to have $\lceil 4.7\cdot 3.7^{i}\rceil$ points, which is smaller than $3.7^{k}$ . The depth of the pair $\{x,y\}$ in $P^{\prime}$ would be at least $\frac{\lceil 4.7\cdot 3.7^{i}\rceil}{4.7}\geq 3.7^{i}$ and at most $|P^{\prime}|{-}\frac{|P^{\prime}|}{4.7}{-}2\leq\frac{3.7\lceil 4.7\cdot 3.7^{i% }\rceil}{4.7}{-}2<3.7^{i+1}$ .

$\blacktriangleright$ Remark.

Ramos and Viaña [47] conjectured that the correct bound in Lemma 2.1 should be $\lfloor\frac{n}{4}\rfloor-1$ . This bound, if true, would be the best achievable [29]. Moreover, it would immediately improve the bound of Theorem 1.5 to $3^{k}$ .

2.2 Points and balls in $\mathbb{R}^{d}$

Our previous result for pairs and disks can be generalized for tuples and balls in higher dimensions. We only need results analogous to Lemma 2.1 (or Corollary 2.2) and Lemma 2.4 in higher dimensions. The following lemma is analogous to Lemma 2.1.

Lemma 2.7 (Smorodinsky, Sulovský, and Wagner [51]).

In any set of $n$ points in $\mathbb{R}^{d}$ there is a subset $S$ of size $\lfloor\frac{d+3}{2}\rfloor$ such that any ball containing $S$ contains at least $\frac{4n}{5ed^{3}}$ points.

The coefficient $\frac{4}{5ed^{3}}$ in the lemma is an improvement over the previous (smaller) constant due to Bárány et al. [11]. It is surprising that the bound $\lfloor\frac{d+3}{2}\rfloor$ in the lemma is strongly sharp as proved in [11], in the sense that, there is a set $P$ of points in $\mathbb{R}^{d}$ (obtained on the moment curve) such that for any subset $S$ of $P$ with $|S|<\lfloor\frac{d+3}{2}\rfloor$ there is a ball that contains $S$ but no other point of $P$ . An analogue to Lemma 2.4 can be obtained in a similar fashion by repeatedly shrinking the ball to lose one point in each iteration.

Lemma 2.8.

Let $P$ be a finite set of points in $\mathbb{R}^{d}$ and $B$ be a ball with $|B\cap P|=j$ for some $j\geq 1$ . There exists a ball $B^{\prime}$ such that $(B^{\prime}\cap P)\subseteq B$ and $|B^{\prime}\cap P|=j-1$ .

Proof.

Fix $B$ at its center $c$ and shrink it until, for the first time, a point $q\in P$ appears on $\partial B$ . If $\partial B$ contains other points of $P$ , fix $B$ at $q$ and enlarge slightly along $c q$ so that $q$ becomes the only point on $\partial B$ . Then fix $B$ at $c$ and shrink slightly to lose $q$ . $\hfill\blacktriangleleft$

We sketch a proof of Theorem 1.6, which is somewhat analogous to that of Theorem 1.5.

Proof Sketch for Theorem 1.6.

Our proof uses a coloring approach similar to that in the proof of Theorem 1.5. We color every tuple $T$ of size $t$ as follows. If the depth of $T$ is 0 then color it 0 if the depth is at least $\left(\frac{4}{5ed^{3}}\right)^{k-2}$ then color it $k-1$ , and if the depth is at least $\left(\frac{4}{5ed^{3}}\right)^{i}$ but smaller than $\left(\frac{4}{5ed^{3}}\right)^{i{+}1}$ then color it $i{+}1$ . Then by applications of Lemma 2.8 and Lemma 2.7 one can show that any ball containing at least $\left(\frac{4}{5ed^{3}}\right)^{k}$ points contains $t$ -tuples of all the $k$ colors. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark.

The proof of Theorem 1.6 is not completely analogous to that of Theorem 1.5. The proof of Theorem 1.5 relies on the existence of a pair whose depth is large but also not too large (Corollary 2.2). The latter part, however, is not given by Lemma 2.7, and thus the proof of Theorem 1.6 relies on the existence of a pair of large depth; later we will see a similar argument in the proof of Theorem 1.9. Such a proof would also work for Theorem 1.5, giving a bound of $4.7^{k}$ instead of $3.7^{k}$ .

$\blacktriangleright$ Remark.

The bound of Theorem 1.6 also applies to hypergraphs defined by points and halfspaces in dimension $d$ because a halfspace can be seen as a very large ball.

3 Coloring Tuples of Grid Points

Here we prove Theorem 1.7. Our main tool is the Lovász local lemma [25]. Recall that $\mathcal{H}$ is the family of all hypergraphs $H$ that is obtained by taking the vertex set $P$ of a regular grid in $\mathbb{R}^{2}$ setting $V(H){:=}P$ and $E(H){:=}\{r\cap P:r$ is an axis-parallel rectangle in $\mathbb{R}^{2}\}$ . We prove for any natural number $k\geq 2$ that $f_{\mathcal{H}}(2,k)\leq\sqrt{ck\ln k}$ , for some constant $c\geq 126$ .

Proof of Theorem 1.7.

Set $m:=\sqrt{ck\ln k}$ . Consider any hypergraph in $\mathcal{H}$ . It suffices to prove the statement for hyperedges (i.e. rectangles) that contain at least $m$ and at most $2m$ points, because any rectangle with more than $2m$ points can be shrunk to have between $m$ and $2m$ points. Any polychromatic coloring with respect to shrunk rectangles is also polychromatic coloring with respect to original rectangles.

We prove the existence of a $k$ -coloring of pairs of $P$ using the probabilistic method and the Lovász local lemma [25]; the coloring itself can be computed by the constructive proof of the local lemma that is given by Moser and Tardos [34]. We color the pairs in $P$ by one of the colors from $\{0,\dots,k-1\}$ uniformly at random. Let $R$ be any rectangle containing at least $m$ and at most $2m$ points. The number of pairs in $R$ is at least $\binom{m}{2}\geq{\frac{1}{4}ck\ln k}$ . Consider any color $i\in\{0,\dots,k{-}1\}$ . The probability that a pair $\{x,y\}$ is not colored $i$ is

\operatorname{\mathrm{Pr}}(\{x,y\}\text{ is not colored }i)=1-\frac{1}{k}\leq e% ^{\frac{-1}{k}}.

Since the pairs are colored independently, the probability that no pair in $R$ is colored $i$ is

\operatorname{\mathrm{Pr}}(\text{no color }i\text{ in }R)\leq\left(e^{\frac{-1% }{k}}\right)^{\frac{1}{4}ck\ln k}=\frac{1}{k^{c/4}}.

Summing over all the $k$ colors, the union bound implies that the probability of a “bad” event $E_{R}$ that the rectangle $R$ is not polychromatic (not having at least one of the $k$ colors) is

p=\operatorname{\mathrm{Pr}}(E_{R})\leq\frac{1}{k^{\frac{c}{4}{-}1}}.

Notice that for two rectangles $R$ and $R^{\prime}$ that do not overlap on any grid point the events $E_{R}$ and $E_{R^{\prime}}$ are independent.

Fix a rectangle $R$ . The length and width of $R$ is at most $2m$ . Thus, $R$ lies in a square $S$ of side length $2m$ . The rectangle $R$ can overlap only with rectangles that are at most $2m$ points away from $R$ in each direction. Thus, the overlapping rectangles must lie in a (bigger) square $S^{+}$ of side length $6m$ . The number of points in $S^{+}$ is $(6m)^{2}$ . Thus, the number of overlapping rectangles is at most $(6m)^{4}$ because each such rectangle can be defined by two points (say bottom left and top right points). Therefore, any bad event $E_{R}$ is independent of all but at most

d=6^{4}m^{4}=6^{4}c^{2}k^{2}\ln^{2}k\leq 6^{4}c^{2}k^{4}

other events. We claim that $4pd<1$ . Indeed, notice that

4pd\leq 4\frac{1}{k^{\frac{c}{4}{-}1}}6^{4}c^{2}k^{4}=\frac{4\cdot 6^{4}c^{2}}% {k^{\frac{c}{4}{-}5}}\leq\frac{4\cdot 6^{4}c^{2}}{2^{\frac{c}{4}{-}5}},

where the last inequality is valid because $k\geq 2$ . The last expression is a decreasing function in $c$ over the interval $[126,+\infty)$ , and its value is less than $1$ at $c=126$ . Since $4pd<1$ , the local lemma implies that with a positive probability none of the bad events occur, which in turn implies the existence of a $k$ -coloring of pairs in $P$ such that every rectangle containing at least $m$ points is polychromatic. This completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 3.1.

Due to our desire to have a short proof, we did not optimize the constant $c$ in Theorem 1.7. It can be improved in several ways, for instance, (i) one can shrink rectangles to have between $m$ and $m+\sqrt{m}$ points instead of $m$ and $2m$ points, (ii) one can consider the neighborhood of $R$ itself instead of the neighborhood of the enclosing square $S^{+}$ which is larger, (iii) to count rectangles intersecting $R$ one can exclude those that contain less than $m$ points, and (iv) by using the stronger threshold of $epd<1$ for the local lemma [49].

4 Coloring Tuples in Hypergraphs of Bounded VC-Dimension

In this section we first prove Theorem 1.10 – the existence of a $(d+1)$ -tuple of depth at least $\frac{n}{c}$ , with $c=4(d+1)^{d+1}$ , in any hypergraph $H$ of VC-dimension at least 2 and at most $d$ and with $n\geq 2d+2$ vertices. This result, of independent interest, is analogous to Lemma 2.1 and Lemma 2.7. Our proof uses the probabilistic method, which is a common technique in combinatorics and discrete geometry [6, 22]. We then use this result to prove Theorem 1.9.

Proof of Theorem 1.10.

Let $V$ be the vertex set of $H$ and $\mathcal{E}$ be the hyperedge set of $H$ . Let $k$ be the maximum depth of a $(d+1)$ -tuple in $V$ with respect to $H$ .

If $H$ has a $(d+1)$ -tuple $T$ that is not in any hyperedge of $\mathcal{E}$ then, by definition, $d_{H}=n-(d+1)\geq\frac{n}{2}$ and the lemma holds. Therefore, we assume that each $(d+1)$ -tuple $T$ belongs to some hyperedge of $\mathcal{E}$ . Let $e_{T}\in\mathcal{E}$ be a hyperedge that identifies the depth of $T$ , i.e, $T\subseteq e_{T}$ and $d_{H}(T)=|e_{T}|-(d+1)$ .

Let $X\subseteq V$ be a random sample of the vertices from $V$ where each vertex is chosen from $X$ independently with a fixed probability $1/n\leq p\leq 1$ (to be determined). Let $\mathcal{E}^{\prime}$ be the set of all hyperedges in $H[X]$ with cardinality equal to $d+1$ . Notice that $|X|$ and $|\mathcal{E}^{\prime}|$ are random variables. Also, notice that the VC-dimension $d^{\prime}$ of the projection $H[X]$ is at most $d$ . Thus by the Sauer-Shelah-Perles lemma [48, 50, 15] we have $|\mathcal{E}^{\prime}|\leq\sum_{i=0}^{d^{\prime}}{\binom{|X|}{i}}$ . This inequality also holds for the expectations, and we have

	$\displaystyle\mathbb{E}(\|\mathcal{E}^{\prime}\|)$	$\displaystyle\leq\mathbb{E}\left(\sum_{i=0}^{d^{\prime}}{\binom{\|X\|}{i}}\right)$
		$\displaystyle{\color[rgb]{0,0,0}\leq\mathbb{E}\left(\sum_{i=0}^{d}{\binom{\|X\|}% {i}}\right)}$
		$\displaystyle\leq\mathbb{E}\Big{(}\|X\|(\|X\|-1)\cdots(\|X\|-d+1)\Big{)}$
		$\displaystyle=\sum_{i=0}^{n}i(i-1)\cdots(i-d+1)\binom{n}{i}p^{i}(1-p)^{n-i}$
		$\displaystyle=\sum_{i={d}}^{n}\frac{n(n-1)\cdots(n-i+1)}{(i-d)!}p^{i}(1-p)^{n-i}$
		$\displaystyle=n(n-1)\cdots(n-d+1)p^{d}\sum_{i={d}}^{n}\frac{(n-d)\cdots(n-i+1)% }{(i-d)!}p^{i-d}(1-p)^{(n-d)-(i-d)}$
		$\displaystyle=n(n-1)\cdots(n-d+1)p^{d}$
		$\displaystyle\leq(np)^{d}.$

For each $(d+1)$ -tuple $T$ in $V$ the probability that $T\in\mathcal{E}^{\prime}$ is at least the probability that $e_{T}\cap X=T$ which is exactly $p^{d+1}(1-p)^{d_{H}(T)}$ . Each such probability is at least $p^{d+1}(1-p)^{k}$ because $d_{H}(T)\leq k$ for all $T$ . By interpreting $|\mathcal{E}^{\prime}|$ as the sum of binary indicator variables (one for each $(d+1)$ -tuple) and then applying the linearity of expectation, we get

p^{d+1}(1-p)^{k}{\binom{n}{d+1}}\leq\mathbb{E}(|\mathcal{E}^{\prime}|).

Combining this with the upper bound $(np)^{d}$ and setting $p:=\frac{1}{k}$ we get

{\binom{n}{d+1}}\leq\frac{kn^{d}}{(1-\frac{1}{k})^{k}}.

Since $(1-1/k)^{k}\geq\frac{1}{4}$ , we have

{\binom{n}{d+1}}\leq 4kn^{d}.

So $k\geq\frac{\binom{n}{d+1}}{4n^{d}}\geq\frac{n}{c}$ for $c=4(d+1)^{d+1}$ . This completes the proof. $\hfill\blacktriangleleft$

Now we use Theorem 1.10 to prove Theorem 1.9 which states that for every shrinkable hypergraph $H$ with VC-dimension at least 2 and at most $d$ and with $n\geq 2d+2$ we have $f_{H}(d+1,k)\leq c^{k-1}$ , for any $k\geq 1$ and any $c\geq 4(d+1)^{d+1}$ .

Proof of Theorem 1.9.

Our proof is somewhat similar to that of Theorem 1.5. We color each $(d+1)$ -tuple of vertices of $H$ with one of the $k$ colors $\{0,1,\ldots,k-1\}$ as follows:

\text{color of }T=\begin{cases}0&\quad\text{if }d_{H}(T)=0\\ i+1&\quad\text{if }c^{i}\leq d_{H}(T)<c^{i{+}1}\text{ for some }i\in\{0,1,% \ldots,k-3\}\\ k-1&\quad\text{if }d_{H}(T)\geq c^{k-2}.\end{cases}

We prove that any hyperedge $e$ of $H$ that contains at least $c^{k{-}1}$ vertices, has $(d+1)$ -tuples of all the $k$ colors. Since $H$ is shrinkable there is a hyperedge $e_{0}$ such that $e_{0}\subset e$ and $|e_{0}|=d+1$ . The hyperedge $e_{0}$ itself is a $(d+1)$ -tuple of depth $0$ , and hence is colored $0$ .

For each $i\in\{0,\ldots,k-2\}$ we show that there is a $(d+1)$ -tuple with color $i{+}1$ in $e$ . Let $e_{i}$ be a hyperedge such that $e_{i}\subseteq e$ and $|e_{i}|=c^{i+1}$ ( $e_{i}$ exists by shrinkability of $H$ and the fact that $c^{i+1}\leq c^{k-1}\leq|e|$ ). Let $V$ be the set of vertices in $e_{i}$ . The VC-dimension of $H[V]$ is at most the VC-dimension of $H$ , which is at most $d$ . The number of vertices of $H[V]$ is $|V|=c^{i{+}1}\geq c\geq 4(d+1)^{d{+}1}\geq 2d+2$ . Hence by Theorem 1.10 the hypergraph $H[V]$ has a $(d+1)$ -tuple $T$ of depth at least $\frac{|V|}{c}=c^{i}$ . On the other hand, the depth of $T$ in $H[V]$ is at most $c^{i+1}-(d+1)$ because this is the most number of vertices (other than $T$ ) that an edge of $H[V]$ can have. Thus $c^{i}\leq d_{H[V]}(T)<c^{i{+}1}$ . We argue that these bounds also hold with respect to $H$ , that is $c^{i}\leq d_{H}(T)<c^{i{+}1}$ . The lower bound is implied from the monotonicity of depth with respect to projections. The upper bound is verified by the edge $e_{i}$ itself, which is an edge of $H$ , it contains $T$ , and it has at most $c^{i{+}1}-(d+1)$ other vertices of $H$ . Therefore, $T$ has color $i+1$ . $\hfill\blacktriangleleft$

5 Relationships Between $f(1,k)$ , $f(t,k)$ , and $\epsilon$ - $𝒕$ -Nets

To have a $(t,k,f(t,k))$ -polychromatic coloring, every edge with at least $f(t,k)$ vertices must have $t$ -tuples of all the $k$ colors. This implies that $\binom{{f(t,k)}}{t}\geq k$ . By the standard upper bound for the binomial coefficient, we have $\binom{{f(t,k)}}{t}\leq\left(\frac{e\cdot f(t,k)}{t}\right)^{t}$ . Combining the two inequalities yields the lower bound

f(t,k)\geq\frac{1}{e}\cdot tk^{\frac{1}{t}}.

(1)

The following folklore result, though very simple, gives an upper bound on $f(t,k)$ in terms of $f(1,tk^{\frac{1}{t}})$ . We have not seen a proof of this result elsewhere; we give a short proof.

Lemma 5.1.

For any hypergraph $H$ and natural numbers $t$ and $k$ with $tk^{\frac{1}{t}}\geq 1$ it holds that $f_{H}(t,k)\leq f_{H}(1,tk^{\frac{1}{t}})$ .

Proof.

Set $x:=tk^{\frac{1}{t}}$ and color the vertices with $x$ colors such that any edge with $f_{H}(1,x)$ vertices is polychromatic. Let $C_{1}$ be the set of these $x$ colors. Now consider all combinations of $t$ different colors in $C_{1}$ . We have $\binom{x}{t}$ many such combinations. Consider each combination as a new color class, and let $C_{t}$ be the set of the new colors (there is a one-to-one correspondence between the colors in $C_{t}$ and the combinations of $t$ colors in $C_{1}$ ). The standard lower bound for binomial coefficient yields

\binom{x}{t}=\binom{tk^{\frac{1}{t}}}{t}\geq\left(\frac{tk^{\frac{1}{t}}}{t}% \right)^{t}=k.

Thus $C_{t}$ has at least $k$ colors. We use the colors in $C_{t}$ to color each $t$ -tuple $T$ of vertices of $H$ . If the vertices of $T$ are colored by $t$ different colors in $C_{1}$ , we color $T$ by the corresponding color in $C_{t}$ . If the vertices of $T$ are colored by less than $t$ colors in $C_{1}$ (i.e., some vertices have the same color), we color $T$ by an arbitrary color in $C_{t}$ .

To prove that our coloring is polychromatic, consider any hyperedge $e$ with at least $f_{H}(1,x)$ vertices. Since $e$ is polychromatic with respect to the vertex coloring by $C_{1}$ , it contains $x$ vertices of distinct colors. Of these vertices, each combination of size $t$ would be a $t$ -tuple that is colored by a unique color in $C_{t}$ . Based on this and the one-to-one correspondence introduced earlier, we conclude that all colors of $C_{t}$ appear in $t$ -tuples of $e$ , and hence $e$ is polychromatic with respect to $t$ -tuple coloring by $C_{t}$ . $\hfill\blacktriangleleft$

Proof of Theorem 1.11.

A combination of (1) and Lemma 5.1 gives an asymptotically tight bound for $f_{H}(t,k)$ when $f_{H}(1,x)$ is linear in $x$ . The statement of the theorem then follows by setting $x:=tk^{1/t}$ . $\hfill\blacktriangleleft$

5.1 Relationship to $\epsilon$ - $𝒕$ -nets

The existence of small-size $\epsilon$ -nets was first shown by Haussler and Welzl [27] who proved that any finite hypergraph with VC-dimension $d$ has an $\epsilon$ -net of size $O((d/\epsilon)\log(d/\epsilon))$ , a bound that was later improved to $O((d/\epsilon)\log(1/\epsilon))$ in [32]. The $\epsilon$ -nets are studied extensively in computer science and have found applications in areas such as computational geometry, algorithms, machine learning, and social choice theory; see, e.g., [3, 9, 13, 19]. Alon et al. [5] showed the existence of small-size $\epsilon$ - $t$ -nets in various geometric hypergraphs and hypergraphs with bounded VC-dimension.

Here, we prove Theorem 1.12 that gives a decomposition of $t$ -tuples into $\epsilon$ - $t$ -nets. It shows the existence of $\Omega\left((\frac{\epsilon n}{t})^{t}\right)$ pairwise disjoint $\epsilon$ - $t$ -nets in a hypergraph $H$ with $n$ vertices for which $f_{H}(1,x)=O(x)$ .

Proof of Theorem 1.12.

From Theorem 5.1 and linearity of $f_{H}(1,x)$ we have $f_{H}(t,k)=f_{H}(1,tk^{\frac{1}{t}})=O(tk^{\frac{1}{t}})$ , for any $k$ where $tk^{\frac{1}{t}}\geq 1$ . Let $k^{\prime}$ , with $tk^{\prime\frac{1}{t}}\geq 1$ , be the largest integer such that $f_{H}(t,k^{\prime})\leq\epsilon n$ (notice that $f_{H}(t,k^{\prime}{+}1)>\epsilon n$ ). Then, every hyperedge of size at least $\epsilon n$ contains tuples of all color classes. This means that each of the $k^{\prime}$ color classes is an $\epsilon$ - $t$ -net. To estimate $k^{\prime}$ we have $\epsilon n<f_{H}(t,k^{\prime}{+}1)=O(t(k^{\prime}{+}1)^{\frac{1}{t}})$ . This would imply that $k^{\prime}=\Omega\left((\frac{\epsilon n}{t})^{t}\right)$ . When $t$ is a constant this gives $\Omega(\epsilon^{t}n^{t})$ .

To verify the tightness of this bound for constant $t$ , consider a hyperedge $e$ with exactly $\epsilon n$ vertices. The number of distinct $t$ -tuples in $e$ is $\binom{{\epsilon n}}{t}\leq\left({\frac{e\cdot\epsilon n}{t}}\right)^{t}=O(% \epsilon^{t}n^{t})$ . This means that we cannot decompose $t$ -tuples into more than $O(\epsilon^{t}n^{t})$ families of $\epsilon$ - $t$ -nets because otherwise $e$ would violate the $\epsilon$ - $t$ -net property of some color class. $\hfill\blacktriangleleft$

5.2 Cover-decomposability

The case $k=2$ is usually referred to as bichromatic coloring. The notion of cover-decomposability is also derived from this case. Recall that a hypergraph is cover-decomposable if $f(1,2)$ is bounded, and it is $t$ -cover-decomposable if $f(t,2)$ is bounded.

Below we prove that $t+1\leq f_{H}(t,2)\leq\max\{f_{H}(1,2),t+1\}$ for any hypergraph $H$ . This improves upon the previous upper bound of $\max\{f_{H}(1,2),2t-1\}$ , given in [1, Proposition 4].

Proof of Theorem 1.13.

The lower bound is obvious because in order for an edge to be polychromatic, it must contain at least two distinct $t$ -tuples, and hence at least $t+1$ vertices ( $t-1$ vertices could be shared between the two $t$ -tuples).

Now we prove the upper bound. The upper bound holds if $f_{H}(1,2)$ is unbounded. Assume that $f_{H}(1,2)$ is bounded. Let $V$ be the set of vertices of $H$ , and let $\phi\colon V\rightarrow\{\text{red},\text{blue}\}$ be a two-coloring of the vertices in $V$ that achieves $f_{H}(1,2)$ . We use $\phi$ to obtain a two-coloring $\xi$ of the $t$ -tuples of $V$ such that $\xi\colon{\binom{V}{t}}\rightarrow\{\text{odd},\text{even}\}$ , where $\binom{V}{t}$ denotes the set of all $t$ -element subsets of $V$ . We color each $t$ -tuple $T$ by the parity of the number of its blue vertices. If the number of blue vertices in $T$ is odd, then we color it odd, and if the number of blue vertices in $T$ is even, then we color it even. We show that this is a valid two-coloring of $t$ -tuples, in the sense that any hyperedge $e\in H$ of cardinality at least $\max\{f_{H}(1,2),t+1\}$ contains two $t$ -tuples such that one is colored odd and the other is colored even.

Since $|e|\geq f_{H}(1,2)$ , $e$ is polychromatic under $\phi$ . Thus, there are two vertices in $e$ , say $r$ and $b$ , colored red and blue, respectively. Since $|e|\geq t+1$ , $e{\setminus}\{r,b\}$ has at least $t-1$ vertices. Pick an arbitrary subset $t^{\prime}$ of $e{\setminus}\{r,b\}$ of size exactly $t-1$ . Then $t^{\prime}\cup\{r\}$ and $t^{\prime}\cup\{b\}$ are two $t$ -tuples in $e$ and the cardinality of their blue vertices differs by $1$ . Therefore, one of them is colored odd, and the other is colored even. $\hfill\blacktriangleleft$

6 Conclusions

We presented several new results on polychromatic coloring of tuples in hypergraphs. In particular we gave an exponential bound (in terms of the number of colors) for polychromatic coloring of pairs of points in the plane with respect to disks (Theorem 1.5) – such a bound does not exist for coloring each point individually. One natural question is whether a polynomial upper bound is achievable for coloring pairs. Another natural question is to close the gap between $\Omega(\sqrt{k})$ and $O(\sqrt{k\ln k})$ for polychromatic coloring of pairs of grid points with respect to axis-aligned rectangles. It would also be interesting to explore similar bounds for other point sets and other objects, for example, one may relate the bounds to the fatness of objects.

References

[1] Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi. Coloring Delaunay-edges and their generalizations. Computational Geometry, 96:101745, 2021. doi:10.1016/J.COMGEO.2021.101745.
[2] Eyal Ackerman, Balázs Keszegh, and Máté Vizer. Coloring points with respect to squares. Discret. Comput. Geom., 58(4):757–784, 2017. Also in SoCG’16. doi:10.1007/S00454-017-9902-Y.
[3] Noga Alon, Graham R. Brightwell, Hal A. Kierstead, Alexandr V. Kostochka, and Peter Winkler. Dominating sets in $k$ -majority tournaments. J. Comb. Theory B, 96(3):374–387, 2006. doi:10.1016/J.JCTB.2005.09.003.
[4] Noga Alon, David Haussler, and Emo Welzl. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension. In Proceedings of the 3rd annual symposium on Computational geometry (SoCG), pages 331–340. ACM, 1987. doi:10.1145/41958.41994.
[5] Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The $\epsilon$ - $t$ -net problem. Discret. Comput. Geom., 68(2):618–644, 2022. Also in SoCG’20. doi:10.1007/S00454-022-00376-X.
[6] Noga Alon and Joel H. Spencer. The Probabilistic Method, Third Edition. Wiley, 2008.
[7] Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, and Perouz Taslakian. Colorful strips. Graphs Comb., 27(3):327–339, 2011. doi:10.1007/S00373-011-1014-5.
[8] Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, and Pedro Ramos. Decomposition of multiple coverings into more parts. Discret. Comput. Geom., 44(3):706–723, 2010. doi:10.1007/S00454-009-9238-3.
[9] Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Approximate polytope membership queries. SIAM J. Comput., 47(1):1–51, 2018. Also in SODA’17. doi:10.1137/16M1061096.
[10] Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Michael Hoffmann, Kolja B. Knauer, Stefan Langerman, Michal Lason, Piotr Micek, Günter Rote, and Torsten Ueckerdt. Coloring hypergraphs induced by dynamic point sets and bottomless rectangles. In In Proceedings of the 13th International Symposium on Algorithms and Data Structures (WADS), pages 73–84. Springer, 2013. doi:10.1007/978-3-642-40104-6_7.
[11] Imre Bárány, James H. Schmerl, Stuart J. Sidney, and Jorge Urrutia. A combinatorial result about points and balls in Euclidean space. Discret. Comput. Geom., 4:259–262, 1989. doi:10.1007/BF02187727.
[12] Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Milos Stojakovic. Polychromatic coloring of tuples in hypergraphs. CoRR, 2025. doi:10.48550/arXiv.2503.22449.
[13] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 36(4):929–965, 1989. doi:10.1145/76359.76371.
[14] Béla Bollobás, David Pritchard, Thomas Rothvoß, and Alex D. Scott. Cover-decomposition and polychromatic numbers. SIAM J. Discret. Math., 27(1):240–256, 2013. Also in ESA’11. doi:10.1137/110856332.
[15] Sarit Buzaglo, Rom Pinchasi, and Günter Rote. Topological Hypergraphs, pages 71–81. Springer New York, 2013. doi:10.1007/978-1-4614-0110-0_6.
[16] Jean Cardinal, Kolja Knauer, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, and Narmada Varadarajan. Colouring bottomless rectangles and arborescences. Comput. Geom., 115:102020, 2023. doi:10.1016/J.COMGEO.2023.102020.
[17] Jean Cardinal, Kolja B. Knauer, Piotr Micek, and Torsten Ueckerdt. Making triangles colorful. J. Comput. Geom., 4(1):240–246, 2013. doi:10.20382/JOCG.V4I1A10.
[18] Jean Cardinal, Kolja B. Knauer, Piotr Micek, and Torsten Ueckerdt. Making octants colorful and related covering decomposition problems. SIAM J. Discret. Math., 28(4):1948–1959, 2014. Also in SODA’14. doi:10.1137/140955975.
[19] Timothy M. Chan. Improved deterministic algorithms for linear programming in low dimensions. ACM Trans. Algorithms, 14(3):30:1–30:10, 2018. Also in SODA’16. doi:10.1145/3155312.
[20] Vera Chekan and Torsten Ueckerdt. Polychromatic colorings of unions of geometric hypergraphs. In Proceedings of the 48th International Workshop Graph-Theoretic Concepts in Computer Science (WG), pages 144–157. Springer, 2022. doi:10.1007/978-3-031-15914-5_11.
[21] Xiaomin Chen, János Pach, Mario Szegedy, and Gábor Tardos. Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Random Struct. Algorithms, 34(1):11–23, 2009. Also in SODA’08. doi:10.1002/RSA.20246.
[22] Kenneth L. Clarkson and Peter W. Shor. Applications of random sampling in computational geometry, II. Discret. Comput. Geom., 4(1):387–421, 1989. Also in SoCG’88. doi:10.1007/BF02187740.
[23] Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa. Shallow packings, semialgebraic set systems, Macbeath regions, and polynomial partitioning. Discret. Comput. Geom., 61(4):756–777, 2019. Also in SoCG’17. doi:10.1007/S00454-019-00075-0.
[24] Herbert Edelsbrunner, N. Hasan, Reimund Seidel, and Xiaojun Shen. Circles through two points that always enclose many points. Geometriae Dedicata, 32:1–12, 1989. doi:10.1007/BF00181432.
[25] Paul Erdős and László Lovász. Problems and results on $3$ -chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado, and V.T. Sós, editors, Infinite and finite sets (to P. Erdős on his 60th birthday), volume II, pages 609–627. North-Holland, 1975.
[26] Matt Gibson and Kasturi R. Varadarajan. Optimally decomposing coverings with translates of a convex polygon. Discret. Comput. Geom., 46(2):313–333, 2011. doi:10.1007/S00454-011-9353-9.
[27] David Haussler and Emo Welzl. epsilon-nets and simplex range queries. Discret. Comput. Geom., 2:127–151, 1987. Also in SoCG’86. doi:10.1007/BF02187876.
[28] Ryan Hayward. A note on the circle containment problem. Discret. Comput. Geom., 4:263–264, 1989. doi:10.1007/BF02187728.
[29] Ryan Hayward, David Rappaport, and Rephael Wenger. Some extremal results on circles containing points. Discret. Comput. Geom., 4(3):253–258, 1989. doi:10.1007/BF02187726.
[30] Balázs Keszegh and Dömötör Pálvölgyi. The geometric hypergraph zoo (beta). URL: https://coge.elte.hu/cogezoo.html.
[31] Balázs Keszegh and Dömötör Pálvölgyi. More on decomposing coverings by octants. J. Comput. Geom., 6(1):300–315, 2015. doi:10.20382/JOCG.V6I1A13.
[32] János Komlós, János Pach, and Gerhard J. Woeginger. Almost tight bounds for epsilon-nets. Discret. Comput. Geom., 7:163–173, 1992. doi:10.1007/BF02187833.
[33] Jirí Matoušek. Bounded VC-dimension implies a fractional Helly theorem. Discret. Comput. Geom., 31(2):251–255, 2004. doi:10.1007/S00454-003-2859-Z.
[34] Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2):11:1–11:15, 2010. doi:10.1145/1667053.1667060.
[35] Dhruv Mubayi and Andrew Suk. A Survey of Hypergraph Ramsey Problems, pages 405–428. Springer International Publishing, 2020. doi:10.1007/978-3-030-55857-4_16.
[36] Nabil Mustafa and Kasturi Varadarajan. Epsilon-approximations and epsilon-nets. In Handbook of Discrete and Computational Geometry. HAL open science, 2017.
[37] Nabil H. Mustafa and Saurabh Ray. $\epsilon$ -Mnets: Hitting geometric set systems with subsets. Discret. Comput. Geom., 57(3):625–640, 2017. doi:10.1007/S00454-016-9845-8.
[38] Victor Neumann-Lara and Jorge Urrutia. A combinatorial result on points and circles on the plane. Discret. Math., 69(2):173–178, 1988. doi:10.1016/0012-365X(88)90015-5.
[39] János Pach. Decomposition of multiple packing and covering. Kolloquium über Diskrete Geometrie, Salzburg, Inst. Math. U. Salzburg, pages 169–178, 1980.
[40] János Pach. Covering the plane with convex polygons. Discret. Comput. Geom., 1:73–81, 1986. doi:10.1007/BF02187684.
[41] János Pach, Dömötör Pálvölgyi, and Géza Tóth. Survey on decomposition of multiple coverings. Geometry – Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth, pages 219–257, 2013.
[42] János Pach, Gábor Tardos, and Géza Tóth. Indecomposable coverings. In China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory (CJCDGCGT), pages 135–148. Springer, 2005. doi:10.1007/978-3-540-70666-3_15.
[43] János Pach and Géza Tóth. Decomposition of multiple coverings into many parts. Comput. Geom., 42(2):127–133, 2009. Also in SoCG’07. doi:10.1016/J.COMGEO.2008.08.002.
[44] János Pach and Dömötör Pálvölgyi. Unsplittable coverings in the plane. Advances in Mathematics, 302:433–457, 2016. doi:10.1016/j.aim.2016.07.011.
[45] Dömötör Pálvölgyi and Géza Tóth. Convex polygons are cover-decomposable. Discret. Comput. Geom., 43(3):483–496, 2010. doi:10.1007/S00454-009-9133-Y.
[46] Tim Planken and Torsten Ueckerdt. Polychromatic colorings of geometric hypergraphs via shallow hitting sets. In In Proceedings of the 40th International Symposium on Computational Geometry (SoCG), pages 74:1–74:14, 2024. doi:10.4230/LIPICS.SOCG.2024.74.
[47] Pedro A. Ramos and Raquel Viaña. Depth of segments and circles through points enclosing many points: a note. Comput. Geom., 42(4):338–341, 2009. doi:10.1016/J.COMGEO.2008.07.001.
[48] Norbert Sauer. On the density of families of sets. J. Comb. Theory A, 13(1):145–147, 1972. doi:10.1016/0097-3165(72)90019-2.
[49] James B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241–245, 1985. doi:10.1007/BF02579368.
[50] Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247–261, 1972. doi:10.2140/pjm.1972.41.247.
[51] Shakhar Smorodinsky, Marek Sulovský, and Uli Wagner. On center regions and balls containing many points. In Proceedings of the 14th Annual International Conference on Computing and Combinatorics (COCOON), pages 363–373. Springer, 2008. doi:10.1007/978-3-540-69733-6_36.
[52] Shakhar Smorodinsky and Yelena Yuditsky. Polychromatic coloring for half-planes. J. Comb. Theory A, 119(1):146–154, 2012. Also in SWAT’10. doi:10.1016/J.JCTA.2011.07.001.

[bib.bib1] [1] Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi. Coloring Delaunay-edges and their generalizations. Computational Geometry, 96:101745, 2021. doi:10.1016/J.COMGEO.2021.101745.

[bib.bib2] [2] Eyal Ackerman, Balázs Keszegh, and Máté Vizer. Coloring points with respect to squares. Discret. Comput. Geom., 58(4):757–784, 2017. Also in SoCG’16. doi:10.1007/S00454-017-9902-Y.

[bib.bib3] [3] Noga Alon, Graham R. Brightwell, Hal A. Kierstead, Alexandr V. Kostochka, and Peter Winkler. Dominating sets in $k$ -majority tournaments. J. Comb. Theory B, 96(3):374–387, 2006. doi:10.1016/J.JCTB.2005.09.003.

[bib.bib4] [4] Noga Alon, David Haussler, and Emo Welzl. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension. In Proceedings of the 3rd annual symposium on Computational geometry (SoCG), pages 331–340. ACM, 1987. doi:10.1145/41958.41994.

[bib.bib5] [5] Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The $\epsilon$ - $t$ -net problem. Discret. Comput. Geom., 68(2):618–644, 2022. Also in SoCG’20. doi:10.1007/S00454-022-00376-X.

[bib.bib6] [6] Noga Alon and Joel H. Spencer. The Probabilistic Method, Third Edition. Wiley, 2008.

[bib.bib7] [7] Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, and Perouz Taslakian. Colorful strips. Graphs Comb., 27(3):327–339, 2011. doi:10.1007/S00373-011-1014-5.

[bib.bib8] [8] Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, and Pedro Ramos. Decomposition of multiple coverings into more parts. Discret. Comput. Geom., 44(3):706–723, 2010. doi:10.1007/S00454-009-9238-3.

[bib.bib9] [9] Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Approximate polytope membership queries. SIAM J. Comput., 47(1):1–51, 2018. Also in SODA’17. doi:10.1137/16M1061096.

[bib.bib10] [10] Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Michael Hoffmann, Kolja B. Knauer, Stefan Langerman, Michal Lason, Piotr Micek, Günter Rote, and Torsten Ueckerdt. Coloring hypergraphs induced by dynamic point sets and bottomless rectangles. In In Proceedings of the 13th International Symposium on Algorithms and Data Structures (WADS), pages 73–84. Springer, 2013. doi:10.1007/978-3-642-40104-6_7.

[bib.bib11] [11] Imre Bárány, James H. Schmerl, Stuart J. Sidney, and Jorge Urrutia. A combinatorial result about points and balls in Euclidean space. Discret. Comput. Geom., 4:259–262, 1989. doi:10.1007/BF02187727.

[bib.bib12] [12] Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Milos Stojakovic. Polychromatic coloring of tuples in hypergraphs. CoRR, 2025. doi:10.48550/arXiv.2503.22449.

[bib.bib13] [13] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 36(4):929–965, 1989. doi:10.1145/76359.76371.

[bib.bib14] [14] Béla Bollobás, David Pritchard, Thomas Rothvoß, and Alex D. Scott. Cover-decomposition and polychromatic numbers. SIAM J. Discret. Math., 27(1):240–256, 2013. Also in ESA’11. doi:10.1137/110856332.

[bib.bib15] [15] Sarit Buzaglo, Rom Pinchasi, and Günter Rote. Topological Hypergraphs, pages 71–81. Springer New York, 2013. doi:10.1007/978-1-4614-0110-0_6.

[bib.bib16] [16] Jean Cardinal, Kolja Knauer, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, and Narmada Varadarajan. Colouring bottomless rectangles and arborescences. Comput. Geom., 115:102020, 2023. doi:10.1016/J.COMGEO.2023.102020.

[bib.bib17] [17] Jean Cardinal, Kolja B. Knauer, Piotr Micek, and Torsten Ueckerdt. Making triangles colorful. J. Comput. Geom., 4(1):240–246, 2013. doi:10.20382/JOCG.V4I1A10.

[bib.bib18] [18] Jean Cardinal, Kolja B. Knauer, Piotr Micek, and Torsten Ueckerdt. Making octants colorful and related covering decomposition problems. SIAM J. Discret. Math., 28(4):1948–1959, 2014. Also in SODA’14. doi:10.1137/140955975.

[bib.bib19] [19] Timothy M. Chan. Improved deterministic algorithms for linear programming in low dimensions. ACM Trans. Algorithms, 14(3):30:1–30:10, 2018. Also in SODA’16. doi:10.1145/3155312.

[bib.bib20] [20] Vera Chekan and Torsten Ueckerdt. Polychromatic colorings of unions of geometric hypergraphs. In Proceedings of the 48th International Workshop Graph-Theoretic Concepts in Computer Science (WG), pages 144–157. Springer, 2022. doi:10.1007/978-3-031-15914-5_11.

[bib.bib21] [21] Xiaomin Chen, János Pach, Mario Szegedy, and Gábor Tardos. Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Random Struct. Algorithms, 34(1):11–23, 2009. Also in SODA’08. doi:10.1002/RSA.20246.

[bib.bib22] [22] Kenneth L. Clarkson and Peter W. Shor. Applications of random sampling in computational geometry, II. Discret. Comput. Geom., 4(1):387–421, 1989. Also in SoCG’88. doi:10.1007/BF02187740.

[bib.bib23] [23] Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa. Shallow packings, semialgebraic set systems, Macbeath regions, and polynomial partitioning. Discret. Comput. Geom., 61(4):756–777, 2019. Also in SoCG’17. doi:10.1007/S00454-019-00075-0.

[bib.bib24] [24] Herbert Edelsbrunner, N. Hasan, Reimund Seidel, and Xiaojun Shen. Circles through two points that always enclose many points. Geometriae Dedicata, 32:1–12, 1989. doi:10.1007/BF00181432.

[bib.bib25] [25] Paul Erdős and László Lovász. Problems and results on $3$ -chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado, and V.T. Sós, editors, Infinite and finite sets (to P. Erdős on his 60th birthday), volume II, pages 609–627. North-Holland, 1975.

[bib.bib26] [26] Matt Gibson and Kasturi R. Varadarajan. Optimally decomposing coverings with translates of a convex polygon. Discret. Comput. Geom., 46(2):313–333, 2011. doi:10.1007/S00454-011-9353-9.

[bib.bib27] [27] David Haussler and Emo Welzl. epsilon-nets and simplex range queries. Discret. Comput. Geom., 2:127–151, 1987. Also in SoCG’86. doi:10.1007/BF02187876.

[bib.bib28] [28] Ryan Hayward. A note on the circle containment problem. Discret. Comput. Geom., 4:263–264, 1989. doi:10.1007/BF02187728.

[bib.bib29] [29] Ryan Hayward, David Rappaport, and Rephael Wenger. Some extremal results on circles containing points. Discret. Comput. Geom., 4(3):253–258, 1989. doi:10.1007/BF02187726.

[bib.bib30] [30] Balázs Keszegh and Dömötör Pálvölgyi. The geometric hypergraph zoo (beta). URL: https://coge.elte.hu/cogezoo.html.

[bib.bib31] [31] Balázs Keszegh and Dömötör Pálvölgyi. More on decomposing coverings by octants. J. Comput. Geom., 6(1):300–315, 2015. doi:10.20382/JOCG.V6I1A13.

[bib.bib32] [32] János Komlós, János Pach, and Gerhard J. Woeginger. Almost tight bounds for epsilon-nets. Discret. Comput. Geom., 7:163–173, 1992. doi:10.1007/BF02187833.

[bib.bib33] [33] Jirí Matoušek. Bounded VC-dimension implies a fractional Helly theorem. Discret. Comput. Geom., 31(2):251–255, 2004. doi:10.1007/S00454-003-2859-Z.

[bib.bib34] [34] Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2):11:1–11:15, 2010. doi:10.1145/1667053.1667060.

[bib.bib35] [35] Dhruv Mubayi and Andrew Suk. A Survey of Hypergraph Ramsey Problems, pages 405–428. Springer International Publishing, 2020. doi:10.1007/978-3-030-55857-4_16.

[bib.bib36] [36] Nabil Mustafa and Kasturi Varadarajan. Epsilon-approximations and epsilon-nets. In Handbook of Discrete and Computational Geometry. HAL open science, 2017.

[bib.bib37] [37] Nabil H. Mustafa and Saurabh Ray. $\epsilon$ -Mnets: Hitting geometric set systems with subsets. Discret. Comput. Geom., 57(3):625–640, 2017. doi:10.1007/S00454-016-9845-8.

[bib.bib38] [38] Victor Neumann-Lara and Jorge Urrutia. A combinatorial result on points and circles on the plane. Discret. Math., 69(2):173–178, 1988. doi:10.1016/0012-365X(88)90015-5.

[bib.bib39] [39] János Pach. Decomposition of multiple packing and covering. Kolloquium über Diskrete Geometrie, Salzburg, Inst. Math. U. Salzburg, pages 169–178, 1980.

[bib.bib40] [40] János Pach. Covering the plane with convex polygons. Discret. Comput. Geom., 1:73–81, 1986. doi:10.1007/BF02187684.

[bib.bib41] [41] János Pach, Dömötör Pálvölgyi, and Géza Tóth. Survey on decomposition of multiple coverings. Geometry – Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth, pages 219–257, 2013.

[bib.bib42] [42] János Pach, Gábor Tardos, and Géza Tóth. Indecomposable coverings. In China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory (CJCDGCGT), pages 135–148. Springer, 2005. doi:10.1007/978-3-540-70666-3_15.

[bib.bib43] [43] János Pach and Géza Tóth. Decomposition of multiple coverings into many parts. Comput. Geom., 42(2):127–133, 2009. Also in SoCG’07. doi:10.1016/J.COMGEO.2008.08.002.

[bib.bib44] [44] János Pach and Dömötör Pálvölgyi. Unsplittable coverings in the plane. Advances in Mathematics, 302:433–457, 2016. doi:10.1016/j.aim.2016.07.011.

[bib.bib45] [45] Dömötör Pálvölgyi and Géza Tóth. Convex polygons are cover-decomposable. Discret. Comput. Geom., 43(3):483–496, 2010. doi:10.1007/S00454-009-9133-Y.

[bib.bib46] [46] Tim Planken and Torsten Ueckerdt. Polychromatic colorings of geometric hypergraphs via shallow hitting sets. In In Proceedings of the 40th International Symposium on Computational Geometry (SoCG), pages 74:1–74:14, 2024. doi:10.4230/LIPICS.SOCG.2024.74.

[bib.bib47] [47] Pedro A. Ramos and Raquel Viaña. Depth of segments and circles through points enclosing many points: a note. Comput. Geom., 42(4):338–341, 2009. doi:10.1016/J.COMGEO.2008.07.001.

[bib.bib48] [48] Norbert Sauer. On the density of families of sets. J. Comb. Theory A, 13(1):145–147, 1972. doi:10.1016/0097-3165(72)90019-2.

[bib.bib49] [49] James B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241–245, 1985. doi:10.1007/BF02579368.

[bib.bib50] [50] Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247–261, 1972. doi:10.2140/pjm.1972.41.247.

[bib.bib51] [51] Shakhar Smorodinsky, Marek Sulovský, and Uli Wagner. On center regions and balls containing many points. In Proceedings of the 14th Annual International Conference on Computing and Combinatorics (COCOON), pages 363–373. Springer, 2008. doi:10.1007/978-3-540-69733-6_36.

[bib.bib52] [52] Shakhar Smorodinsky and Yelena Yuditsky. Polychromatic coloring for half-planes. J. Comb. Theory A, 119(1):146–154, 2012. Also in SWAT’10. doi:10.1016/J.JCTA.2011.07.001.

Polychromatic Coloring of Tuples in Hypergraphs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Other related results

1.2 Preliminaries

Definition 1.1 (Shrinkability).

Definition 1.2 (VC-dimension).

Definition 1.3 (Depth).

Definition 1.4 (ϵ-t-Net).

1.3 Our contributions

Theorem 1.5.

Theorem 1.6.

Theorem 1.7.

Theorem 1.8.

Theorem 1.9.

Theorem 1.10.

Theorem 1.11.

Theorem 1.12.

Theorem 1.13.

Corollary 1.14.

2 Coloring Tuples of Points with respect to Disks and Balls

2.1 Points and disks in ℝ𝟐

Lemma 2.1 (Ramos and Viaña [47]).

Corollary 2.2.

Lemma 2.3.

Proof.

Lemma 2.4.

Lemma 2.5.

Proof.

Lemma 2.6.

Proof.

Proof of Theorem 1.5.

▶ Remark.

▶ Remark.

2.2 Points and balls in ℝ𝒅

Lemma 2.7 (Smorodinsky, Sulovský, and Wagner [51]).

Lemma 2.8.

Proof.

Proof Sketch for Theorem 1.6.

▶ Remark.

▶ Remark.

3 Coloring Tuples of Grid Points

Proof of Theorem 1.7.

▶ Remark 3.1.

4 Coloring Tuples in Hypergraphs of Bounded VC-Dimension

Proof of Theorem 1.10.

Proof of Theorem 1.9.

5 Relationships Between 𝒇⁢(𝟏,𝒌), 𝒇⁢(𝒕,𝒌), and ϵ-𝒕-Nets

Lemma 5.1.

Proof.

Proof of Theorem 1.11.

5.1 Relationship to ϵ-𝒕-nets

Proof of Theorem 1.12.

5.2 Cover-decomposability

Proof of Theorem 1.13.

6 Conclusions

References

Definition 1.4 ( $\epsilon$ - $t$ -Net).

2.1 Points and disks in $\mathbb{R}^{2}$

$\blacktriangleright$ Remark.

$\blacktriangleright$ Remark.

2.2 Points and balls in $\mathbb{R}^{d}$

$\blacktriangleright$ Remark.

$\blacktriangleright$ Remark.

$\blacktriangleright$ Remark 3.1.

5 Relationships Between $f(1,k)$ , $f(t,k)$ , and $\epsilon$ - $𝒕$ -Nets

5.1 Relationship to $\epsilon$ - $𝒕$ -nets