An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes

Abstract

The goal of this paper is to give a new, abstract approach to cover-decomposition and polychromatic colorings using hypergraphs on ordered vertex sets. We introduce an abstract version of a framework by Smorodinsky and Yuditsky, used for polychromatic coloring halfplanes, and apply it to so-called ABA-free hypergraphs, which are a generalization of interval graphs. Using our methods, we prove that $(2k-1)$-uniform ABA-free hypergraphs have a polychromatic k-coloring, a problem posed by the second author. We also prove the same for hypergraphs defined on a point set by pseudohalfplanes. These results are best possible.

We also introduce several new notions that seem to be important for investigating polychromatic colorings and $\epsilon$-nets, such as shallow hitting sets. We pose several open problems related to them. For example, is it true that given a finite point set S on a sphere and a set of halfspheres $\mathcal {F}$, such that $\{S\cap F\mid F\in \mathcal {F}\}$ is a Sperner family, we can select an $R\subset S$ such that $1\le |F\cap R|\le 2$ holds for every $F\in \mathcal {F}$?

Research supported by Hungarian Scientific Research Fund (OTKA), under grant NN 102029, NK 78439, PD 104386, PD 108406, by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The study of proper and polychromatic colorings of geometric hypergraphs has attracted much attention, not only because this is a very basic and natural theoretical problem but also because such problems often have important applications. One such application area is resource allocation, e.g., battery consumption in sensor networks. Moreover, the coloring of geometric shapes in the plane is related to the problems of cover-decomposability, conflict-free colorings and $\epsilon$-nets; these problems have applications in sensor networks and frequency assignment as well as other areas. For surveys on these and related problems see [13, 18].

In a (primal) geometric hypergraph polychromatic coloring problem, we are given a natural number k, a set of points and a collection of regions in $\mathbb {R}^d$, and our goal is to k-color the points such that every region that contains at least m(k) points contains a point of every color, where m is some function that we try to minimize. We call such a coloring a polychromatic k-coloring. In a dual geometric hypergraph polychromatic coloring problem, our goal is to k-color the regions such that every point which is contained in at least m(k) regions is contained in a region of every color. In other words, in the dual version our goal is to decompose an m(k)-fold covering of some point set into k coverings. The primal and the dual versions are equivalent if the underlying regions are the translates of some fixed set. For the proof of this statement and an extensive survey of results related to cover-decomposition, see e.g., [13]. Below we mention some of these results, stated in the equivalent primal form.

The most general result about translates of polygons is that given a fixed convex polygon, there exists a c (that depends only on the polygon) such that any finite point set has a polychromatic k-coloring such that any translate of the fixed convex polygon that contains at least $m(k)=c\cdot k$ points contains a point of every color [6]. Non-convex polygons for which such a finite m(k) (for any $k\ge 2$) exists have been classified [14, 17].

As it was shown recently [16], there is no such finite m(2) for convex sets with a smooth boundary, e.g., for the translates of a disc. However, it was also shown in the same paper that for the translates of any unbounded convex set $m(2)=3$ is sufficient. In this paper we extend this result to every k, showing that $m(k)=2k-1$ is an optimal function for unbounded convex sets.

For homothets of a given shape the primal and dual problems are not equivalent. For homothets of a triangle (a case closely related to the case of translates of octants [9, 10]), there are several results, the current best are $m(k)= O(k^{4.53})$ in the primal version [2, 11] and $m(k)= O(k^{5.53})$ in the dual version [3]. For the homothets of other convex polygons, in the dual case there is no finite m(2) [12], and in the primal case only conditional results are known [11], namely, that the existence of a finite m(2) implies the existence of an m(k) that grows at most polynomially in k. In fact, it is even possible that for any polychromatic coloring problem $m(k)=O(m(2))$.

For other shapes, cover-decomposability has been studied less, in these cases the investigation of polychromatic-colorings is motivated rather by conflict-free colorings or $\epsilon$-nets. Most closely related to our paper, coloring halfplanes for small values were investigated in [5, 7, 8], and polychromatic k-colorings in [19]. We generalize all the (primal and dual) results of the latter paper to pseudohalfplanes. Note that translates of an unbounded convex set form a set of pseudohalfplanes, thus the above mentioned result about unbounded convex sets is a special case of this generalization to pseudohalfplanes.

Besides generalizing earlier results, our contribution is a more abstract approach to the above problems. Namely, we introduce the notion of ABA-free families (see Definition 1) and shallow hitting sets (see Definition 5).

1.1 Definitions and Statements of Main Results

Definition 1

A hypergraph $\mathcal H$ with an ordered vertex set is called ABA-free if H does not contain two hyperedges A and B for which there are three vertices $x<y<z$ such that $x,z\in A\setminus B$ and $y\in B\setminus A$.

A hypergraph with an unordered vertex set is ABA-free if its vertices have an ordering with which the hypergraph is ABA-free.¹

Remark 1

ABA-free hypergraphs were first defined in [16] under the name special shift-chains, as they are a special case of shift-chains introduced in [15].

Example 2

An interval hypergraph is a hypergraph whose vertices are some points of $\mathbb {R}$, and hyperedges are some intervals from $\mathbb {R}$, with the incidences preserved. By definition, every interval hypergraph is ABA-free and in fact every ABA-free hypergraph is similar, in a way, to an interval hypergraph.

Example 3

[16]. Let S be a set of points in the plane with different x-coordinates and let C be a convex set that contains a vertical halfline. Define a hypergraph $\mathcal H$ whose vertex set is the x-coordinates of the points of S. A set of numbers X is a hyperedge of $\mathcal H$ if there is a translate of C such that the x-coordinates of the points of S contained in the translate is exactly X. The hypergraph $\mathcal H$ defined this way is ABA-free.

Example 4

Let S be a set of points in the plane in general position. Define a hypergraph $\mathcal H$ whose vertex set is the x-coordinates of the points of S. A set of numbers X is a hyperedge of $\mathcal H$ if there is a positive halfplane H (i.e., that contains a vertical positive halfline) such that the x-coordinates of the points of S contained in H is exactly X. The hypergraph $\mathcal H$ defined this way is ABA-free.

The above examples show how to reduce geometric problems to abstract problems about ABA-free hypergraphs. Observe that given an S, by choosing an appropriately big parabola, all hyperedges defined by positive halfplanes is also defined by some translate of this parabola, thus the first example is more general than the second. Even more, as we will see later in Sect. 3, finite ABA-free hypergraphs have an equivalent geometric representation with graphic pseudoline arrangements (sets are defined by the regions above the pseudolines, for the definitions and details see Sect. 3) and both translates of the boundary of an unbounded convex set and lines in the plane form graphic pseudoline arrangements, showing again that the above examples are special cases of ABA-free hypergraphs.

To study polychromatic coloring problems, we also introduce the following definition, which is implicitly used in [19], but deserves to be defined explicitly as it seems to be important in the study of polychromatic colorings.

Definition 5

A set R is a c-shallow hitting set of the hypergraph $\mathcal H$ if for every $H\in \mathcal H$ we have $1\le |R\cap H|\le c$.

Actually, almost all our results are based on shallow hitting sets.

Observation 6

An induced subhypergraph of an ABA-free hypergraph is also ABA-free.

Our main results and the organization of the rest of this paper is as follows.

In Sect. 2 we prove (following closely the ideas of Smorodinsky and Yuditsky [19]) that every $(2k-1)$-uniform ABA-free hypergraph has a polychromatic coloring with k colors. We then observe that the dual of this problem is equivalent to the primal, which implies that the edges of every $(2k-1)$-uniform ABA-free hypergraph can be colored with k colors, such that if a vertex v is in a subfamily $\mathcal {H}_v$ of at least $m(k)=2k-1$ of the edges of $\mathcal {H}$, then $\mathcal {H}_v$ contains a hyperedge from each of the k color classes.

In Sect. 3 we give an abstract equivalent definition (using ABA-free hypergraphs) of hypergraphs defined by pseudohalfplanes, and we prove that given a finite set of points S and a pseudohalfplane arrangement $\mathcal {H}$, we can k-color S such that any pseudohalfplane in $\mathcal {H}$ that contains at least $m(k)=2k-1$ points of S contains all k colors. Both results are sharp. Note that these results imply the same for hypergraphs defined by unbounded convex sets.

In Sect. 5 we discuss dual and other versions of the problem. For example we prove that given a pseudohalfplane arrangement $\mathcal {H}$, we can k-color $\mathcal {H}$ such that if a point p belongs to a subfamily $\mathcal {H}_p$ of at least $m(k)=3k-2$ of the pseudohalfplanes of $\mathcal {H}$, then $\mathcal {H}_p$ contains a pseudohalfplane from each of the k color classes. This result might not be sharp, the best known lower bound for m(k) is $2k-1$ [19]. We also discuss consequences about $\epsilon$-nets on pseudohalfplanes.

We denote the symmetric difference of two sets, A and B, by $A\varDelta B$, the complement of a hyperedge F by $\bar{F}$ and for a family $\mathcal {F}$ we use $\bar{\mathcal {F}}=\{\bar{F} | F\in \mathcal {F}\}$. We will suppose (unless stated otherwise) that all hypergraph and point sets are finite, and denote the smallest (resp. largest) element of an ordered set H by $\min (H)$ (resp. $\max (H)$).

2 ABA-free Hypergraphs

Suppose we are given an ABA-free hypergraph $\mathcal H$ on n vertices. As the hypergraph is ABA-free, for any pair of sets $A, B \in \mathcal H$ either there are $a<b$ such that $a\in A\setminus B$ and $b\in B\setminus A$, or there are $b<a$ such that $a\in A\setminus B$ and $b\in B\setminus A$, or none of them, but not both as that would contradict ABA-freeness.

Define $A<B$ if and only if there are $a<b$ such that $a\in A\setminus B$ and $b\in B\setminus A$. Define $A\le B$ if and only if either $A=B$ (as sets) or $A<B$. By the above observation, this is well-defined, and it gives a partial ordering of the sets.

Definition 7

A vertex a is skippable if there exists an $A\!\in \! \mathcal {H}$ such that $\min (A)\!< a < \max (A)$ and $a\notin A$. In this case we say that A skips a. A vertex a is unskippable if there is no such A.

Observation 8

If a vertex a is unskippable in some ABA-free hypergraph $\mathcal {H}$, then after adding the one-element edge $\{a\}$ to $\mathcal {H}$, it remains ABA-free.

Note that the following two lemmas show that the unskippable vertices of an ABA-free hypergraph behave similarly to vertices on the convex hull of a hypergraph on a point set defined by halfplanes. These two lemmas make it possible to use the framework of [19] on ABA-free hypergraphs.

Lemma 9

If $\mathcal H$ is finite ABA-free, then every $A\in \mathcal H$ contains an unskippable vertex.

Remark 2

Note that finiteness is needed, as the hypergraph whose vertex set is $\mathbb Z$ and edge set is $\{ \mathbb Z\setminus \{n\}\mid n\in \mathbb Z\}$ is ABA-free without unskippable vertices.

Proof

Take an arbitrary set $A\in \mathcal {H}$, suppose that it does not contain an unskippable vertex, we will reach a contradiction. Call $a\in A$ rightskippable if there is a $B\in \mathcal {H}$ rightskipping a, that is for which $a\in A\setminus B$ and there are $b_1, b_2\in B$ such that $b_1<a<b_2$ where $b_2\in B\setminus A$.

If A contains no unskippable vertex, $\max (A)$ must be rightskippable (any set skipping $\max (A)$ must also rightskip $\max (A)$). Also, $\min (A)$ cannot be rightskippable, as otherwise A and the set B rightskipping $\min (A)$ would violate ABA-freeness (we would get $b_1<\min (A)<b_2$ where $b_1,b_2\in B\setminus A, \min (A)\in A\setminus B$). Therefore we can take the largest $a\in A$ that is not rightskippable. By the assumption, it is skipped by a set, call it B, i.e., $b_1<a<b_2$ where $b_1, b_2\in B \not \ni a$. Moreover, wlog., suppose that $b_2$ is the smallest element of B which is bigger than a. Since a is not rightskippable, $b_2\in A$ must also hold. As $b_2\in A$ is rightskippable, there is a C such that $c_1<b_2<c_2$ where $c_1, c_2\in C$ and $b_2\notin C, c_2\notin A$. Wlog., suppose $c_1$ is the largest element of C which is smaller than $b_2$. If $c_1<a$, then C would rightskip a, a contradiction. Thus, $b_1<a\le c_1,$ and from the choice of $b_2$ we conclude that $c_1\notin B$. As $c_2\notin A$, also $c_2\notin B$, otherwise B would rightskip a. Putting all together, we get $c_1<b_2<c_2$, thus B and C contradict ABA-freeness.

Recall that a hypergraph is called Sperner if no two of its sets (i.e., hyperedges) contain each other, we further assume in it that the hypergraph is nonempty, i.e., it contains at least one edge.

Lemma 10

If $\mathcal H$ is finite, ABA-free and Sperner, then any minimal hitting set of $\mathcal H$ that contains only unskippable vertices is 2-shallow.

Proof

Let R be a minimal hitting set of unskippable vertices. Assume to the contrary that there exists a set A such that $|A\cap R|\ge 3$. Let $l=\min (A\cap R)$ and $r=\max (A\cap R)$. There exists a third vertex $l<a<r$ in $A\cap R$. We claim that $R'=R\setminus \{a\}$ hits all sets of $\mathcal H$, contradicting its minimality. Assume on the contrary that $R'$ is disjoint from some $B\in \mathcal H$. As R must hit B, we have $R\cap B=\{a\}$. If there is a $b\in B\setminus A$ such that $l<b<r$, that would contradict the ABA-free property. If there is a $b\in B$ such that $b<l<a$ or $a<r<b$, that would contradict that l and r are unskippable. Thus $B\subset A$, contradicting that $\mathcal H$ is Sperner.

Now we present the framework of [19] modified for ABA-free hypergraphs. Our algorithm to give a polychromatic k-coloring of the vertices of an ABA-free hypergraph with edges of size at least $2k-1$ is as follows.

Algorithm 11

At the beginning we are given an ABA-free hypergraph $\mathcal H$ with edges of size at least $2k-1$.

Repeat $k-1$ times ($i=1,\dots ,k-1$) the general step i of the algorithm:

At the beginning of step i we have an ABA-free hypergraph $\mathcal H$ with edges of size at least $2k-2i+1$. If any hyperedge contains another, then delete the bigger hyperedge. Repeat this until no hyperedge contains another, thus making our hypergraph Sperner. Next, take the set of all unskippable vertices, which is a hitting set by Lemma 9 and delete vertices from this set until it becomes a minimal hitting set R. By Lemma 10 R is a 2-shallow hitting set, color its vertices with the i-th color. Delete these vertices from $\mathcal H$ (the edges of the new hypergraph are the ones induced by the remaining vertices). Using Observation 6, at the end of this step i, we have an ABA-free hypergraph with edges of size at least $2k-2i-1$.

After $k-1$ iterations of the above, we are left with a 1-uniform hypergraph whose vertices we can color with the k-th color.

Algorithm 11 implies the following theorem.

Theorem 12

Given a finite ABA-free ${\mathcal H}$ we can color its vertices with k colors such that every $A\in {\mathcal H}$ whose size is at least $2k-1$ contains all k colors.

Notice that the above theorem is sharp, as taking $\mathcal H$ to be all subsets of size $2k-2$ from $2k-1$ vertices, in any coloring of the vertices, one color must occur at most once and is thus missed by some hyperedge.

We state another corollary of Lemma 9 that we need later. Before that, we need another simple claim.

Proposition 13

Suppose we insert a new vertex, v, somewhere into the (ordered) vertex set of an ABA-free hypergraph, $\mathcal {H}$, and add v to every edge that contains a vertex before and another vertex after v, then we get an ABA-free hypergraph.

Proof

We show that if in the new hypergraph, $\mathcal {H}'$, two hyperedges $A'$ and $B'$ violate ABA-freeness, then we can find two hyperedges A and B in the original hypergraph, $\mathcal {H}$, that also violate ABA-freeness, which would be a contradiction. We define $A=A'\setminus \{v\}$ and $B=B'\setminus \{v\}$. If both $A'$ and $B'$ contain or do not contain v, then by definition A and B also violate the condition. If, say, $v\notin A'$ and $v\in B'$, then without loss of generality we can suppose that all the vertices of $A=A'$ are before v. This means that if there are $x<y<z$ such that $x,z\in A'\setminus B'$ and $y\in B'\setminus A'$, then necessarily $v=z$. But as $B'$ has an element $z'$ that is bigger than v, we have $x,z'\in A\setminus B$ and $y\in B\setminus A$, a contradiction.

Lemma 14

If $\mathcal H$ is ABA-free, $A\in \mathcal {H}$, then there is a vertex $a\in A$ such that $\mathcal {H}\cup \{A\setminus \{a\}\}$ is also ABA-free.

Proof

If $|A|=1$, then trivially $\mathcal H$ can be extended with $\emptyset$. If $|A|>1$, then we proceed by induction on the size of A. Using Lemma 9, there is an unskippable vertex $v\in A$. Delete this vertex from $\mathcal {H}$ to obtain some ABA-free $\mathcal {H}_v$ and let $A_v=A\setminus \{v\}$. Using induction on $A_v$, there is an $A_v'=A_v\setminus \{a\}$ such that $\mathcal {H}_v\cup \{A_v'\}$ is also ABA-free. We claim that with $A'=A_v'\cup \{v\}=A\setminus \{a\}$, the family $\mathcal {H}\cup \{A'\}$ is also ABA-free.

Notice that adding back v to $\mathcal {H}_v$ is very similar to the operation of Proposition 13, as v is unskippable in $\mathcal {H}$. The only difference is that we might also have to add it to some further hyperedges, ending in or starting at v. But a hyperedge that contains v cannot violate the ABA-free condition with $A'$, since it also contains v, so the corresponding hyperedges in $\mathcal {H}_v$ would also violate the ABA-free condition.

Notice that with the repeated application of Lemma 14 we can extend any ABA-free hypergraph, such that in any set A there is a vertex a for which $\{a\}$ is a singleton edge, implying that a is unskippable in A. Thus in fact Lemma 14 is equivalent to Lemma 9. Moreover, in Sect. 3, in the more general context of pseudohalfplanes, it will be the abstract equivalent of a known and important property of pseudohalfplanes.

We prove another interesting property of ABA-free hypergraphs before which we need the following definition.

Definition 15

The dual of a hypergraph $\mathcal H$, denoted by $\mathcal H^*$, is such that its vertices are the hyperedges of $\mathcal H$ and its hyperedges are the vertices of $\mathcal H$ with the same incidences as in $\mathcal H$.

Proposition 16

If ${\mathcal H}$ is ABA-free, then its dual ${\mathcal H^*}$ is also ABA-free with respect to some ordering of its vertices.

Proof

Take the partial order “<” of the hyperedges of $\mathcal H$ and extend this arbitrarily into a total order $<^*$. We claim that ${\mathcal H^*}$ is ABA-free if its vertices are ordered with respect to $<^*$. To check the condition, suppose for a contradiction that $H_x<^*H_y<^*H_z$ and $a\in (H_x\cap H_z)\setminus H_y$ and $b\in H_y\setminus (H_x\cup H_z)$. Without loss of generality, suppose that $a<b$. But in this case $H_z<H_y$ holds, contradicting $H_y<^*H_z$.

Corollary 17

The edges of every $(2k-1)$-uniform ABA-free hypergraph can be colored with k colors, such that if a vertex v is in a subfamily $\mathcal {H}_v$ of at least $m(k)=2k-1$ of the edges of $\mathcal {H}$, then $\mathcal {H}_v$ contains a hyperedge from each of the k color classes.

Corollary 18

Any $(2k-1)$-fold covering of a finite point set with the translates of an unbounded convex planar set is decomposable into k coverings.

3 Pseudohalfplanes

Here we extend a result of Smorodinsky and Yuditsky [19]. A pseudoline arrangement is a finite collection of simple curves in the plane in general position (i.e., no three curves have a common point) such that any two are either disjoint or intersect once and in the intersection point they cross. Some further definitions and well-known results about pseudoline arrangements are collected below, which can be found in [1]. We also recommend [4] where generalizations of classical theorems are proved for topological affine planes.

An infinite pseudoline arrangement is such that cutting a pseudoline in two, both parts are unbounded. A curve is graphic if it is the graph of a function, i.e., an x-monotone infinite curve that intersects every vertical line of the plane. A graphic pseudoline arrangement is such that every curve is graphic. We say that two pseudoline arrangements are equivalent if there is a bijection between their pseudolines such that the order in which a pseudoline intersects the other pseudolines remains the same. A pseudohalfplane arrangement is an infinite pseudoline arrangement, with a side of each pseudoline selected (note that the two sides of a pseudoline are well-defined regions in this case).

Facts About Pseudoline Arrangements

• I. (Levi Enlargement Lemma) Given a pseudoline arrangement, any two points of the plane can be connected by a new pseudoline (if they are not connected already).

• II. Given a pseudoline arrangement, we can find a(n infinite) pseudoline arrangement in which every pair of pseudolines intersects exactly once, and the order in which a pseudoline intersects the other pseudolines remains the same (ignoring the new intersections).

• III. Given an infinite pseudoline arrangement, we can find an equivalent graphic pseudoline arrangement.

From these facts it follows that in the definition of a pseudohalfplane we can (and will) suppose that the underlying pseudoline arrangement is a graphic pseudoline arrangement.

Notice that ABA-free hypergraphs are in a natural bijection with (graphic) pseudoline arrangements and sets of points, such that each hyperedge corresponds to the subset of points above a pseudoline.

Proposition 19

Given in the plane a set of points S (with all different x-coordinates) and a graphic pseudoline arrangement L, define the hypergraph $\mathcal{H}_{S,L}$ with vertex set S such that for each pseudoline $l\in L$ the set of points above l is a hyperedge of $\mathcal{H}_{S,L}$. Then $\mathcal{H}_{S,L}$ is ABA-free with the order on the vertices defined by the x-coordinates.

Conversely, given an ABA-free hypergraph $\mathcal H$, there exists a set of points S and a graphic pseudoline arrangement L such that $\mathcal{H}=\mathcal{H}_{S,L}$.

Proof

The first part is almost trivial, suppose that there are two hyperedges A, B in $\mathcal{H}_{S,L}$ having an ABA-sequence on the vertices corresponding to the points $a,b,c\in S$. The pseudolines corresponding to the hyperedges A and B are denoted by $\ell _A$ and $\ell _B$. The pseudoline $\ell _A$ intersects the vertical line through a below a, the vertical line through b above b and the vertical line through c above c, while $\ell _A$ intersects these in the opposite way (above/below/above). Thus these lines must intersect in the vertical strip between a and b and also in the strip between b and c, thus having two intersections, a contradiction.

The second part of the proof is also quite natural. Given an ABA-free hypergraph $\mathcal{H}(V,E)$ with an ordering on V, we want to realize it with a planar point set S and a graphic pseudoline arrangement L. Let S be |V| points on the x axis corresponding to the vertices in V such that the order on V is the same as the order given by the x-coordinates on S. From now on we identify the vertices of Vwith the corresponding points of V.

For a given $A\in \mathcal H$ it is easy to draw an $\ell _A$ graphic curve for which the points of S above $\ell _A$ are exactly in A. Draw a pseudoline $\ell _A$ for every $A\in \mathcal H$, such that there are finitely many intersections among these pseudolines, all of them crossings. What we get is an arrangement of graphic curves, but it can happen that they intersect more than twice. Now among such drawings take one which has the minimal number of intersections, we claim that this is a pseudoline arrangement.

Assume on the contrary, that there are two curves $\ell _A$ and $\ell _B$ intersecting (at least) twice. Let two consecutive (in the x-order) intersection points be p and q, where p has smaller x-coordinate than q. Without loss of generality, $\ell _A$ is above $\ell _B$ close to the left of p and close to the right of q, while $\ell _A$ is below $\ell _B$ in the open vertical strip between p and q. This structure is usually called a lens, and we want to eliminate it in a standard way, decreasing the number of intersections. We can change the part of $\ell _A$ and $\ell _B$ to the left of p (and to the right from the intersection $p'$ next to and left of p if there is any) and change their drawing locally around p (and $p'$ if it exists) such that we get rid of the intersection at p, see Fig. 1. If there are no points of S between $\ell _A$ and $\ell _B$ and to the left of p (and to the right of $p'$), then this redrawing does not change the hyperedges defined by $\ell _A$ and $\ell _B$, so we get a representation of $\mathcal H$ with less intersections, a contradiction. Thus there is a point $(p'<)a<p$ below $\ell _A$ and above $\ell _B$. Similarly, there must be a point $p<b<q$ above $\ell _A$ and below $\ell _B$ and finally a point $q<c$ below $\ell _A$ and above $\ell _B$, otherwise we could redraw the pseudolines with less intersections. These three points $a<b<c$ contradict the ABA-freeness of $\mathcal H$ as by the definition of the pseudolines, $b\in A\setminus B$ and $a,c\in B\setminus A$.

Fig. 1.

Redrawing a lens to decrease the number of intersections

From these, it follows that the hypergraphs defined by points contained in pseudohalfplanes have the following structure.

Definition 20

A hypergraph $\mathcal {H}$ on an ordered set of points S is called a pseudohalfplane-hypergraph if there exists an ABA-free hypergraph $\mathcal {F}$ on S such that $\mathcal {H}\subset \mathcal {F}\cup \bar{\mathcal {F}}$.

Note that $\bar{\mathcal {F}}$ is also ABA-free with the same ordering of the points. We refer to the edges of a pseudohalfplane-hypergraph also as pseudohalfplanes.

Using Lemma 14 on a hyperedge of a pseudohalfplane-hypergraph, we get the following.

Proposition 21

Given a pseudohalfplane-hypergraph $\mathcal {H}$, and an edge A of $\mathcal {H}$, we can add a new hyperedge $A'$ contained completely in A that contains all but one of the points of A, such that $\mathcal {H}$ remains a pseudohalfplane-hypergraph.

In the geometric setting this corresponds to the known and useful fact that given a pseudohalfplane arrangement and a finite set of points A contained in the pseudohalfplane H, we can add a new pseudohalfplane $H'$ contained completely in H that contains all but one of the points of A.

Now we show how to extend Theorem 12 to pseudohalfplane arrangements, i.e., to the case when the points of S below a line also define a hyperedge.

Theorem 22

Given a finite set of points S and a pseudohalfplane arrangement $\mathcal {H}$, we can color S with k colors such that any pseudohalfplane in $\mathcal {H}$ that contains at least $2k-1$ points of S contains all k colors. Equivalently, the vertices S of a finite pseudohalfplane-hypergraph can be colored with k colors such that any hyperedge containing at least $2k-1$ points contains all k colors.

We remark that a similar statement is not true for the union of two arbitrary ABA-free hypergraphs (instead of an ABA-free hypergraph and its complement), in fact the union of two arbitrary ABA-free hypergraphs might not be 2-colorable, see [16] for such a construction.

4 Proof of Theorem 22

Proof

Our proof is completely about the abstract setting, yet it translates naturally to the geometric setting, also the figures illustrate the geometric interpretations.

By definition there exists an ABA-free $\mathcal {F}$ such that $\mathcal {H}\subset \mathcal {F}\cup \bar{\mathcal {F}}$. Call $\mathcal {U}=\mathcal {H}\cap \mathcal {F}$ the upsets and $\mathcal {D}=\mathcal {H}\cap \bar{\mathcal {F}}$ the downsets, observe that both $\mathcal {U}$ and $\mathcal {D}$ are ABA-free.

Further, the unskippable vertices of $\mathcal {U}$ (resp. $\mathcal {D}$) are called top (resp. bottom) vertices. The top and bottom vertices are called the unskippable vertices of $\mathcal {H}$. Recall that by adding these unskippable vertices as one-element edges to $\mathcal {H}$, $\mathcal {H}$ remains to be a pseudohalfplane-hypergraph, as we can extend $\mathcal {F}$ and $\bar{\mathcal {F}}$ with the appropriate hyperedge (this is a convenient way of thinking about top/bottom vertices in the geometric setting, as seen later in the figures).

Fig. 2.

Proof of Lemma 24

Observation 23

If x is top and X is a downset and $x\in X$, then X contains all vertices that are bigger or all vertices that are smaller than x. The same holds if x is bottom, X is an upset and $x\in X$.

Lemma 24

If $\mathcal {H}$ is a finite Sperner pseudohalfplane-hypergraph, then any minimal hitting set of $\mathcal H$ that contains only unskippable vertices is 2-shallow.

Proof

Let R be a minimal hitting set of unskippable vertices. Suppose for a contradiction that $\{a,b,c\}\subset R\cap X$ and $a<b<c$ for some $X\in \mathcal {H}$. Without loss of generality, suppose that b is top. As R is minimal, let B be a set for which $B\cap R=\{b\}$. From Observation 23 it follows that B is an upset.

First suppose that X is an upset. As $B\not \subset X$, take a $b_2\in B\setminus X$. As B and X are both upsets and thus have the ABA-free property, we have $b_2<a$ or $c<b_2$. Without loss of generality, we can suppose $c<b_2$. If c is top, $\{c\}$ and B violate ABA-freeness. See Fig. 2a. If c is bottom, then using Observation 23, X contains all the vertices that are smaller than c. Take a set $A\not \subset X$ for which $A\cap R=\{a\}$. This set must contain an $a_2\in A\setminus X$ and so we must have $c<a_2$. If A is an upset, as it does not contain b and recall $a<b<a_2$, A and $\{b\}$ violate ABA-freeness. See Fig. 2b. If A is a downset, as it does not contain c and recall $a<c<a_2$, A and $\{c\}$ violate ABA-freeness, both cases lead to a contradiction.

The case when X is a downset is similar. Using Observation 23 for X and $\{b\}$ we can suppose without loss of generality that X contains all vertices that are smaller than b. Take a set $A\not \subset X$ for which $A\cap R=\{a\}$ and an $a_2\in A\setminus X$. As X contains all vertices smaller than b, we have $b<a_2$. A cannot be an upset, as then it would contain b, so it is a downset. If $b<a_2<c$, then A and X would violate ABA-freeness, thus we must have $c<a_2$. This means c cannot be bottom, so it is top. Using Observation 23, X contains all the vertices that are smaller than c. But then $B\setminus X$ must have an element that is bigger than c, contradicting the ABA-freeness of B and $\{c\}$.

From here the rest of the proof is the same. Our algorithm to give a k-coloring of the vertices of $\mathcal {H}$ such that every pseudohalfplane of size at least $2k-1$ contains all k colors is as follows. Using Proposition 21, it is enough to consider pseudohalfplanes of size exactly $2k-1$. Apply Lemma 24 to select a 2-shallow hitting set R and color its vertices with the first color. Delete these vertices and apply induction on k.

5 The Dual Problem and Signed ABA-free Hypergraphs

We are also interested in coloring pseudohalfplanes with k colors such that all points that are covered many times will be contained for each k colors in a pseudohalfplane of that color. For example, we can also generalize the dual result about coloring halfplanes of [19] to pseudohalfplanes.

Theorem 25

Given a pseudohalfplane arrangement $\mathcal {H}$, we can color $\mathcal {H}$ with k colors such that if a point p belongs to a subset $\mathcal {H}_p$ of at least $3k-2$ of the pseudohalfplanes of $\mathcal {H}$ then $\mathcal {H}_p$ contains a pseudohalfplane of every color.

Theorem 25 follows from Theorem 29, that we will state and prove later.

However, instead of coloring pseudohalfplanes, we stick to coloring points with respect to pseudohalfplanes and work with dual hypergraphs, where the vertex-hyperedge incidences are preserved, but vertices become hyperedges and hyperedges become vertices. Since we have already seen in Sect. 3 the equivalence of our abstract definition and the standard definition of a pseudohalfplane arrangement, we can use the well-known properties of the dual arrangement (see, e.g., [1]) to obtain the following.

Proposition 26

A dual pseudohalfplane-hypergraph is a hypergraph $\mathcal {H}$ on an ordered set of vertices S such that there exists a set $X\subset S$ and an ABA-free hypergraph $\mathcal F$ on S such that the edges of $\mathcal {H}$ are the edges $F\varDelta X$ for every $F\in \mathcal F$.

Proof

Using Definition 20, let $\mathcal {F}$ be an ABA-free hypergraph that represents the original pseudohalfplane-hypergraph, that is, every pseudohalfplane is equal to a set $F\in \mathcal {F}$ or to a set $F\in \bar{\mathcal {F}}$. Using Proposition 16, the dual of $\mathcal {F}$ is an ABA-free hypergraph, $\mathcal {F}^*$, whose vertices $\{v_F:F\in \mathcal {F}\}$ correspond to the edges of $\mathcal {F}$ (ordered in some way) and whose edges $\{f_p:p\in S\}$ correspond to the vertices of $\mathcal {F}$, with incidence relations preserved, i.e., $f_p=\{v_F:p\in F\}$. Now we add also the set of vertices $\{v_{\bar{F}}:\bar{F}\in \mathcal {F}\}$ corresponding to the edges of $\bar{\mathcal {F}}$. Each vertex $v_{\bar{F}}$ is put right after vertex $v_F$ in the order. The edges change in the following way. As in $\mathcal {F}$ we have $p\notin F\in \mathcal {F}$ if and only if $p\in \bar{F}$, in the dual the corresponding edge is $h_p=\{v_F:p\in F\}\cup \{v_{\bar{F}}:p\in \bar{F}\}$ contains exactly one of $v_F$ and $v_{\bar{F}}$. First, without loss of generality, we can suppose that for every $A\in \mathcal {F}$, $\mathcal {H}$ contains at least one of $A\in \mathcal {F}$ and $\bar{A}\in \bar{\mathcal {F}}$, otherwise we can delete A from $\mathcal {F}$ too. Further, we can suppose that $\mathcal {H}$ contains exactly one of $A\in \mathcal {F}$ and $\bar{A}\in \bar{\mathcal {F}}$, as if it contains both, we can add another copy $A'$ of A to $\mathcal {F}$ ($\mathcal {F}$ is then a(n ABA-free) multihypergraph) and regard $\bar{A}$ as $\bar{A'}$. This way it can never happen that both $A\in \mathcal {H}$ and $\bar{A}\in \mathcal {H}$, thus in the dual only one of the corresponding vertices are present. Thus, we can relabel to $w_A$ the one vertex that is present in $\mathcal {H}$ among $v_A$ and $v_{\bar{A}}$. After the relabeling we have $V=\{w_A:A\in \mathcal {F}\}$. Denote by X the set of vertices of V for which $w_A=v_{\bar{A}}$. Now an arbitrary edge $h_p=\{v_F:p\in F\}\cup \{v_{\bar{F}}:p\in \bar{F}\}=\{w_F:p\in F\cap \bar{X}\}\cup \{w_F:p\in \bar{F}\cap X\}=f'_p \varDelta X$, where $\varDelta$ denotes the symmetric difference of two sets and $f'_p=\{w_F:v_F\in f_P\}$, i.e., $f_p$ injected in the natural way into the relabeled set V. These $f'_p$ define the same (up to this projection) ABA-free hyperedge $\mathcal G$ as $\mathcal {F}^*$.

Now we define a common generalization of the primal and dual definitions.

Definition 27

A signed pseudohalfplane-hypergraph is a hypergraph $\mathcal {H}$ on an ordered set of vertices S such that there exists a set $X\subset S$ and an ABA-free hypergraph $\mathcal F$ on S such that the edges of $\mathcal {H}$ are some subset of $\{F\varDelta X, \bar{F} \varDelta X \mid F\in \mathcal F\}$.

It is easy to see that the dual of such a signed pseudohalfplane-hypergraph is also a signed pseudohalfplane-hypergraph, just like in Proposition 16. Furthermore, there is a nice geometric representation of such hypergraphs; $\mathcal {H}$ is a signed pseudohalfplane-hypergraph if and only if there is a set of points, S, on the surface of a sphere and a pseudohalfsphere arrangement $\mathcal {F}$ on the sphere such that the incidences among S and $\mathcal {F}$ give $\mathcal {H}$. (Here we omit the exact definition of pseudohalfsphere arrangements, which are a generalization of a collection of some halfspheres of a sphere. The interested reader can find it in [1].)

Another popular geometric representation on the plane, adding signs to lines and points, is the following. The vertices correspond to a set of points in the plane together with a direction (up or down), and the edges correspond to a set of (x-monotone) pseudolines with a sign ($+$ or −). The hyperedge corresponding to a positive pseudoline is the set of points that point towards the pseudoline, while the hyperedge corresponding to a negative pseudoline is the set of points that point away from the pseudoline. Positive pseudolines correspond to $\mathcal {F}$, negative pseudolines to $\bar{\mathcal {F}}$, up points correspond to X and down points correspond to $\bar{X}$. With this interpretation, ABA-free hypergraphs have only + and up signs, pseudohalfplane-hypergraphs have ± and up signs, dual pseudohalfplane-hypergraphs have + and up/down signs.

In the next table we summarize the best known results about these hypergraphs, with respect to how many points each edge has to contain to have a polychromatic k-coloring and the values of the smallest c for which there exists a c-shallow hitting set for Sperner families.

	Polychromatic k-coloring	Shallow hitting set
ABA-free hypergraphs	$2k-1$ (Theorem 12)	2 (Lemma 10)
Pseudohalfplane-hypergraphs	$2k-1$ (Theorem 22)	2 (Lemma 24)
Dual pseudohalfplane-hypergraphs	$\le 3k-2$ (Theorem 25)	$\le 3$ (Theorem 29)
Signed pseudohalfplane-hypergraphs	$\le 4k-3$ (Corollary 28)	?

We conjecture that even Sperner pseudohalfsphere arrangements have a 2-shallow hitting set, which would also imply (using the framework described above Theorem 12) that any family whose sets have size at least $2k-1$ admits a polychromatic k-coloring, but we could not even prove for any constant c that a c-shallow hitting set exists.

As we can find a polychromatic k-coloring of the points of X and $\bar{X}$ independently with respect to the sets of $\mathcal {F}$ and $\bar{\mathcal {F}}$, respectively, of size at least $2k-1$ using Theorem 22, the following is true.

Corollary 28

Given a finite set of points S on the sphere and a pseudohalfsphere arrangement $\mathcal {H}$, we can color S with k colors such that any pseudohalfsphere in $\mathcal {H}$ that contains at least $4k-3$ points of S contains all k colors. Equivalently, the vertices S of a finite signed pseudohalfplane-hypergraph can be colored with k colors such that any hyperedge containing at least $4k-3$ points contains all k colors.

To finish, we first need to prove the following theorem, which, using the usual framework, will imply Theorem 25.

Theorem 29

Every Sperner dual pseudohalfplane hypergraph has a 3-shallow hitting set.

The proof of this result follows again closely the argument of [19] and the interested reader can find it in the full version of the paper.