text:
\begin{document}

\title{Coloring Delaunay-Edges and their Generalizations\thanks{Research by the first author was partially supported by ERC AdG Disconv and MTA EU10/2016-11001. Research by the second author was supported by the National Research, Development and Innovation Office -- NKFIH under the grant K 116769. Research by the second and third authors was supported by the Lend\"ulet program of the Hungarian Academy of Sciences (MTA), under grant number LP2017-19/2017.}}

\author{Eyal Ackerman\inst{1} \and
Bal\'azs Keszegh\inst{2,3} \and
D\"om\"ot\"or P\'alv\"olgyi\inst{3}}

\authorrunning{E. Ackerman et al.}

\institute{Department of Mathematics, Physics, and Computer Science,
	University of Haifa at Oranim, 	Tivon 36006, Israel. E-mail: \email{ackerman@sci.haifa.ac.il}
	\and
Alfr\'ed R{\'e}nyi Institute of Mathematics, Hungarian Academy of Sciences Re\'altanoda u. 13-15 Budapest, 1053 Hungary. E-mail: \email{keszegh@renyi.hu}
\and
MTA-ELTE Lend\"ulet Combinatorial Geometry Research Group, Institute of Mathematics, E\"otv\"os Lor\'and University (ELTE), Budapest, Hungary.}

\maketitle

\begin{abstract}
	We consider geometric hypergraphs whose vertex set is a finite set of points (e.g., in the plane),
	and whose hyperedges are the intersections of this set with a family of geometric regions (e.g., axis-parallel rectangles).
	A typical coloring problem for such geometric hypergraphs asks, given an integer $k$, for the existence of an integer $m=m(k)$, such that every set of points can be $k$-colored such that every hyperedge of size at least $m$ contains points of different (or all $k$) colors.

	We generalize this notion by introducing coloring of (unordered) \emph{$t$-tuples} of points such that every hyperedge that contains enough points contains $t$-tuples of different (or all) colors.
	In particular, we consider all $t$-tuples and $t$-tuples that are themselves hyperedges.
	The latter, with $t=2$, is equivalent to coloring the edges of the so-called \emph{Delaunay-graph}.

	In this paper we study colorings of Delaunay-edges with respect to halfplanes, pseudo-disks, axis-parallel and bottomless rectangles, and also discuss colorings of $t$-tuples of geometric and abstract hypergraphs, and connections between the standard coloring of vertices and coloring of $t$-tuples of vertices.

\keywords{Delaunay-graph \and Delaunay-edges \and geometric hyperedges}
\end{abstract}

\section{Introduction}

We consider \emph{geometric} hypergraphs that we call \emph{Delaunay-hypergraphs} and are defined as follows: given a family of regions $\F$ and a set of points $S$, the vertex set of the hypergraph $G(S,\F)$ is $S$ and a subset $S'$ of $S$ is a hyperedge of $G(S,\F)$ if there exists a region $F\in \F$ such that $S'=S\cap F$.
A special case that has attracted attention in the literature is the case in which we only consider hyperedges of size two, called \emph{Delaunay-edges}. In this case $G$ is the so-called \emph{Delaunay-graph} of $S$ with respect to $\F$. This notion generalizes the well-known concept of Delaunay triangulation of planar point sets.

The Delaunay triangulation is of course planar. It is also known that the Delaunay-graph is planar when it is defined with respect to a planar set of points and a family of \emph{pseudo-disks}~\cite{buzaglo}. (A family of compact regions in the plane, each of which is bounded by a Jordan curve, is called a family of \emph{pseudo-disks} if every two boundary curves are disjoint or properly cross twice.)
Moreover, the second and third authors have recently proved that there is a plane embedding of this graph such that every edge lies within all the pseudo-disks that contain its endpoints~\cite{PD-plane}.
Note that halfplanes, disks, or more generally, homothets\footnote{The homothetic copy of a set is its scaled and translated copy (rotations are not allowed).} of a certain convex shape with a smooth\footnote{Any Delaunay-hypergraph that can be defined using the homothets of a convex set can also be defined as the Delaunay-hypergraph of a convex set with a smooth boundary.} boundary, are all families of pseudo-disks.
However, not every Delaunay-graph with respect to a planar point set is planar. For example, it is easy to see that if $\F$ is the family of all axis-parallel rectangles, then the Delaunay-graph may contain $K_{t,t}$ as a subgraph for every integer $t$.

The problem of coloring the vertices of Delaunay-hypergraphs has attracted a lot of attention. Specifically, for a Delaunay-hypergraph $G$ and an integer $k$, one wishes to determine the smallest integer $m$ such that the vertices of $G$ can be colored with $k$ colors such that every Delaunay-hyperedge of size at least $m$ contains vertices of different (or all $k$) colors.
The former is known as \emph{proper}, the latter as \emph{polychromatic} coloring.

In this paper we introduce a generalization of the problem of coloring the vertices of a (geometric) hypergraph. In particular, we wish to color (unordered) \emph{$t$-tuples} of vertices
such that every Delaunay-hyperedge with enough vertices contains $t$-tuples of different colors (or all $k$ colors). Note that when $t=1$, we get the usual (proper or polychromatic) coloring of vertices.
For $t \ge 2$ we identify two interesting variants:
In the first one, we color all the possible $t$-tuples of vertices, whereas in the second variant we only color $t$-tuples that are themselves Delaunay-hyperedges. For example, for $t=2$ we have a coloring of the \emph{Delaunay-edges}.

\subsection{Our contribution}

In Section \ref{sec:deledge} we consider proper coloring of $t$-tuples that are themselves Delaunay-hyperedges and prove the following results.

\begin{theorem}\label{thm:pseudo}
	Let $S$ be a finite set of points in the plane, let $\F$ be a family of pseudo-disks that is \emph{shrinkable} with respect to $S$ (see below). Then it is possible to color the Delaunay-edges of $S$ with respect to $\F$ with four colors, such that every pseudo-disk $F \in \F$ that contains at least three points from $S$ contains Delaunay-edges of two different colors.
\end{theorem}

Theorem \ref{thm:pseudo} is proved in Section \ref{sec:psdisk}.
Roughly speaking, a family $\F$ is \emph{shrinkable} with respect to $S$ if for every $F \in \F$ and a point $p \in S \cap F$ it holds that $\F$ contains a hyperedge that still contains $p$ and one less point from $S$ and $\F$.
Note that we do not require the $F' \in \F$ defining this new hyperedge to be a subset of $F$.
For example, disks are shrinkable with respect to any finite point set, but unit disks are not.
Theorem~\ref{thm:pseudo} also holds whenever $\F$ is a family of homothets of a compact convex set $C$ and $S$ is in general position with respect to $C$.
However, we can get better results in terms of the number of colors for two specific families.

\begin{theorem}\label{thm:halfplanes}
	Let $S$ be a finite set of points in the plane and let $\F$ be the family of halfplanes. Then the Delaunay-edges of $S$ with respect to $\F$ can be $2$-colored such that every halfplane that contains at least three Delaunay-edges contains two differently colored edges. This statement is false if we replace three with two.
\end{theorem}

Theorem \ref{thm:halfplanes} is proved in Section \ref{sec:hp}.

We remark that a halfplane may contain an arbitrary number of points from $S$ while containing only one Delaunay-edge; this is why we consider halfplanes that contain enough Delaunay-edges instead of halfplanes that contain enough points.

\begin{theorem} \label{thm:bless}
	Let $S$ be a finite set of points in the plane and let $\F$ be the family of bottomless rectangles. Then the Delaunay-edges of $S$ with respect to $\F$  can be $2$-colored such that every bottomless rectangle that contains at least four points from $S$ contains two differently colored edges. This statement is false if we replace four with three.
\end{theorem}

Theorem \ref{thm:bless} is proved in Section \ref{sec:bless}.

We also consider coloring Delaunay-edges with respect to axis-parallel rectangles. However, in this case we only managed to show that by using $O(\log n)$ colors one can guarantee that every rectangle that contains at least three points from $S$ contains two differently colored Delaunay-edges (proved in Section \ref{sec:ap}). We leave it as an open problem whether constantly many colors also suffice.

\medskip
Considering coloring of \emph{all} $t$-tuples of vertices of a hypergraph, we first study in Section~\ref{sec:allthyp} the case of \emph{abstract} hypergraphs (that is, which are not necessarily defined by geometric means).
In particular, we prove some results about how polychromatic colorability of $t$-tuples implies polychromatic colorability of $t'$-tuples, for $t'>t$.
Note that it is an open problem whether $2$-colorability of vertices implies polychromatic $k$-colorability of vertices, for $k>2$, see~\cite{PPT14}.

\medskip
Finally, in Section \ref{sec:alltgeom} we consider colorings of all $t$-tuples of vertices of a hypergraph defined by a point set and a family of geometric regions.
Given a finite family of halfspaces $\HH=\{H_1,\dots, H_h\}$ we call a region $R$ an \emph{$\HH$-region} if it is the intersection of finitely many halfspaces, such that each of them is a translate of one of the halfspaces in $\HH$.
Our main result about coloring all $t$-tuples is the following.

\begin{theorem}\label{thm:region}
	For every dimension $d$
	and integers $t\ge 2$, $k \ge 1,h\ge 1$ there exists an integer $m=m(t,k,h)$ with the following property: given a finite family of $h$ halfspaces $\HH$ in $\mathbb{R}^d$, the $t$-tuples of every finite set of points $S$ in $\mathbb{R}^d$ can be $k$-colored such that every $\HH$-region that contains at least $m$ points from $S$ contains a $t$-tuple of points of each of the $k$ colors.
\end{theorem}

As a corollary, similar results hold for $d$-dimensional axis-parallel boxes and homothets of a $d$-dimensional convex polytope.

\subsection{Related work}

We are not aware of any work that considers coloring of Delaunay-hyperedges or $t$-tuples of vertices as defined in this paper. There is however vast literature on coloring points with respect to Delaunay-hyperedges.
Here we briefly describe the results that are most relevant to our work.

As we mention above, it is known that we can properly $4$-color the points with respect to pseudo-disks since their Delaunay-graph is planar. On the other hand, there is no constant $m$ for which we can properly $2$-color the points with respect to (unit/pseudo-)disks containing at least $m$ points~\cite{PP13,PTT05}.
It is an open problem whether a proper $3$-coloring is always possible for a large enough $m$ for (unit/pseudo-)disks \cite{K11,KP16}.

Considering the family of axis-parallel rectangles, recall that the Delaunay-graph in this case is not necessarily planar. Estimating the chromatic number of the Delaunay-graph in this case is a famous open problem with a large gap between the best known lower bound of $\Omega(\frac{\log n}{\log\log n})$~\cite{chenpach} and the best known upper bound of $O(n^{0.368})$~\cite{chan12} (where $n$ is the size of $S$).
There is however a proper $O(\log n)$-coloring with respect to rectangles that contain at least $3$ points from $S$~\cite{eyalrom}.

There is a proper $2$-coloring with respect to bottomless rectangles containing $4$ points \cite{K11}, and more generally, for bottomless rectangles containing $3k-2$ points there is a polychromatic $k$-coloring~\cite{A13}. For halfplanes containing $3$ points there is a $2$-coloring~\cite{K11}, and more generally, for halfplanes containing $2k-1$ points there is a polychromatic $k$-coloring~\cite{SY10}.
We remark that it is an open problem whether $2$-colorability for some $m$ implies polychromatic $k$-colorability for some $m_k$; see \cite{PPT14}.
For more results, see the survey \cite{PPT14} or the webpage \cite{cogezoo}.

\smallskip
The geometric hypergraphs that we consider are usually called \emph{primal} hypergraphs. We briefly mention that one can define \emph{dual} hypergraphs where the vertices correspond to regions from $\F$ and the hyperedges correspond to points of the plane. One can even generalize these notions further, in particular one can define \emph{intersection} hypergraphs where both the vertices and hyperedges correspond to regions from $\F$ (or from two different families). All of these variants have a vast literature with connections to the notions of \emph{cover-decomposability} and \emph{conflict-free} coloring, that are not relevant to this work and hence are not mentioned.

\section{Coloring Delaunay-edges}\label{sec:deledge}

\begin{comment}
We have seen that for a very general class of families of regions we can color all $t$-tuples ($t\ge 2$) to avoid big monochromatic regions (a region is big if it contains many points from the given set of points $S$). In fact we could even require that all big regions contain a point with each of the colors we used. The problem becomes much harder by adding the natural restriction that we color only the $t$-tuples that can be cut out by a member of the family (which we call \emph{cuttable $t$-tuples}).

More formally, given a family of regions $\cal F$, a set of points $S$, and two integers $k$ and $t$, we wish to color each $t$-tuple $T$ of points from $S$ for which there is $F \in \F$ such that $F \cap S = T$, such that every region in $\F$ that contains at least $m$ points (where $m$ does not depend on $|S|$) contains two $t$-tuples with two different colors (in the case of proper coloring) or contains a $t$-tuple of each of the $k$ colors (in the case of polychromatic coloring).

Note that the coloring methods that were used in the previous section do not work in this case.
As an example, observe that $n$ points in the plane with increasing $x$- and $y$-coordinates, induce only $n-1$ cuttable pairs of points with respect to axis-parallel rectangles (as opposed to the total number of pairs being ${{n}\choose{2}}$). This is one reason why the proof of, say, Theorem~\ref{thm:rectangles} fails in this case.

It is also not clear whether a coloring of $t$-tuples implies a coloring of $t'$-tuples for $t'>t$, as was the case in Claim \ref{claim:chi} and Theorem~\ref{thm:t-ind}.

In this section we focus only on proper colorings where $t=2$, that is, we color the so-called \emph{Delaunay-edges} such that every region that contains many Delaunay-edges contains edges of different colors.
\end{comment}

Let $S$ be a finite set of points in the plane and let $\F$ be a family of regions. Recall that $G(S,\F)$ is the Delaunay-hypergraph whose vertex set is $S$ and whose hyperedge set consists of all subsets $S' \subseteq S$ for which there exist a region $F \in \F$ such that $S' = S \cap F$.

\begin{definition}
	The \emph{Delaunay-edges} of $S$ with respect to $\F$ are all the hyperedges of size two in $G(S,\F)$.
	The \emph{Delaunay-graph} $D(S,\F)$ is the graph whose vertex set is $S$ and whose edge set consists of the Delaunay-edges of $S$ with respect to $\F$.
\end{definition}

Our goal is to find a coloring such that every region in $\cal F$ that contains $m=m(\F)$ \emph{points} from $S$ contains two differently colored Delaunay-edges.
The families that we consider are psuedo-disks, axis-parallel rectangles, bottomless rectangles and halfplanes.

\begin{comment}
Unlike for coloring all $t$-tuples, now we do not consider abstract hypergraphs in general, as without appropriate restrictions there is no hope to have meaningful results, for example a hypergraph may not even contain Delaunay-edges. On the other hand the problem is of course interesting for non-geometric hypergraphs as well, for example Lemma \ref{lem:hasse} (see later) is such a result about hypergraphs defined on posets.
\end{comment}

\subsection{Coloring Delaunay-edges with respect to pseudo-disks}\label{sec:psdisk}

We say that a family of pseudo-disks $\F$ is \emph{saturated} with respect to a set of points $S$, if there is no region $R$ such that $\F \cup \{R\}$ is a family of pseudo-disks and $G(S,\F) \neq G(S,\F \cup \{R\})$.
Note that every family of pseudo-disks can be extended greedily to a saturated family with respect to $S$.

\subsubsection{The Delaunay-graph with respect to pseudo-disks}

\mybreak
Let $S$ be a set of points in the plane and let $\F$ be a family of regions.
It is well-known~\cite{Kvoronoi} that when $\F$ is the set of homothets of a convex shape (or any other convex pseudo-disk family),
then embedding the Delaunay-graph $D(S,\F)$ such that every two adjacent points in $S$ are connected by a straight-line segment results in a plane graph.
For Delaunay-graphs with respect to (non-convex) pseudo-disks this might not hold, but using the Hanani-Tutte theorem it is possible to show that the Delaunay-graph is always planar \cite{buzaglo}.
We need the following stronger result, which is proved in a companion paper~\cite{PD-plane}.

\begin{theorem}[\cite{PD-plane}]\label{thm:planedelgraph}
	Given a finite pseudo-disk family $\F$ and a point set $S$, there is a drawing of the Delaunay-graph $D(S,\F)$ such that every edge lies inside every pseudo-disk that contains both of its endpoints and no two edges cross.
\end{theorem}

A useful ingredient of the proof of Theorem \ref{thm:planedelgraph} is the following lemma of Buzaglo et al.~\cite{buzaglo}.

\begin{lemma}[\cite{buzaglo}]\label{lem:buzaglo}
	Let $D_0$ and $D_1$ be two pseudo-disks from a pseudo-disk family and let $\gamma_0$ and $\gamma_1$ be two curves such that $D_i$ contains $\gamma_i$ and does not contain the endpoints of $\gamma_{1-i}$, for $i=0,1$. Then $\gamma_0$ and $\gamma_1$ cross each other an even number of times.
\end{lemma}

We will use this lemma as well as the next one due to Pinchasi~\cite{Pin14}, whose proof applies a result of Snoeyink and Hershberger \cite{SH89}.

\begin{lemma}[\cite{Pin14}]\label{lem:shrink}
	Let $\cal B$ be a family of pairwise disjoint sets in the plane and let $\F$ be a family of pseudo-disks. Let $D$ be a member of $\F$ and suppose that $D$ intersects exactly $k\ge 2$ members of $\cal B$, one of which is $B \in \cal B$. Then for every integer $2 \le \ell \le k$ there exists $D' \subseteq D$ such that $D'$ intersects $B$ and exactly $\ell-1$ other sets from $\cal B$, and $\F \cup \{D'\}$ is a family of pseudo-disks.
\end{lemma}

\begin{definition}
We say that a family of regions $\F$ is \emph{shrinkable} with respect to $S$ if for every region $F\in \F$ with $|F\cap S|\ge 3$ and every $p\in F\cap S$ there exists another region $F'\in \F$ such that $p\in F'\cap S\subset F\cap S$ and $|F'\cap S|=|F\cap S|-1$.
\end{definition}

By setting $B$ to be $S$, Lemma \ref{lem:shrink} implies that a family of pseudo-disks which is saturated with respect to $S$ is also shrinkable with respect to $S$.

\subsubsection{Coloring Delaunay-edges with respect to pseudo-disks }

\mybreak
Let $S$ be a finite set of points in the plane, let $\F$ be a family of pseudo-disks that is shrinkable with respect to $S$. Theorem~\ref{thm:pseudo} states that it is possible to color the edges of the Delaunay-graph $D(S,\F)$ with four colors, such that every pseudo-disk $F \in \F$ that contains at least three points from $S$ contains Delaunay-edges of two different colors.

\begin{proof}[Proof of Theorem~\ref{thm:pseudo}]
	Let $D$ be a plane drawing of $D(S,\F)$ such that every Delaunay-edge lies inside every pseudo-disk that contains its endpoints.
	By Theorem~\ref{thm:planedelgraph} such a drawing exists.

	Let $J$ be a subgraph of the line graph of $D(S,\F)$ that is defined as follows.
	The vertex set of $J$ is the set of Delaunay-edges, and two Delaunay-edges $e$ and $e'$ are adjacent in $J$ if they share an endpoint and there is a pseudo-disk $F \in \F$ such that $F\cap S$ is exactly the three endpoints of $e$ and $e'$.

	Using $D$ we draw $J$ as follows (we do not distinguish between points and edges and their embeddings).
	For every Delaunay-edge $e$ we choose arbitrarily a point $p_e$ in the interior of this edge.
	Suppose that $e$ and $e'$ are two Delaunay-edges that are adjacent in $J$,
	and let $q \in S$ be the common endpoint of $e$ and $e'$.
	Then the drawing of the edge $\{e,e'\}$ of $J$ consists of the segment of $e$ between $p_e$ and $q$ and the segment of $e'$ between $q$ and $p_{e'}$.

	Note that the drawing of $J$ does not contain crossing edges, since $D$ is a plane graph.
	However, $J$ contains several overlaps between the drawn edges.

	\begin{proposition}\label{prop:Jplanar}
	The graph $J$ can be redrawn as a plane graph.
	\end{proposition}

		\begin{proof}
			In order to remove overlaps between the edges we re-draw the edges with the following procedure (see Figure~\ref{fig:redraw} for an illustration).

			\begin{figure}
				\centering
				\includegraphics[width=6cm]{redraw}
				\caption{Drawing $J$ in the proof of Theorem~\ref{thm:pseudo}.}
				\label{fig:redraw}
			\end{figure}

			First, we slightly inflate every edge and every point in $S$, such that every edge has a very small width and every point $q$ is replaced by a very small disk $C(q)$.
			Denote the neighbors of some point $q$ by $q_1,\ldots,q_l$ in clockwise order around $q$.
			We choose $l$ points, called \emph{ports}, on the intersection of the inflated edge $\{q_i,q\}$ and $C(q)$ for each $i$ (so in total $l^2$ ports).
			We denote the ports by $q_{ij}$, where the ports $q_{ij}$ ($1\le j\le l$) are ordered in counter-clockwise order for every $i$.
			Every edge $\{p_{\{q_i,q\}},p_{\{q,q_j\}}\}$ of $J$
			is drawn as follows: $p_{\{q_i,q\}}$ is connected to $q_{ij}$ with a curve $\gamma_{ij}$ inside the inflated $\{q_i,q\}$, then $q_{ij}$ is connected to $q_{ji}$ inside $C(q)$ with a straight-line segment, and finally $q_{ji}$ is connected to $p_{\{q_j,q\}}$ with a curve $\gamma_{ji}$ inside the inflated $\{q_j,q\}$.
			Due to the ordering of the ports, it is easy to achieve that for every $i$ the curves $\gamma_{ij}$ do not cross inside the inflated $\{q_i,q\}$.
			It is also easy to achieve that these curves do not cross the curves that go towards $q_i$ from $p_{q_iq}$ (which correspond to the edges of the line graph between the edges incident to $q_i$).
			Also, due to the ordering of the ports, drawings of $q_iq_j$ and $q_iq_k$ (for any $i,j,k$) do not intersect inside $C(q)$.

			We also need to show that no segments cross inside $C(q)$.
			Suppose that this is not the case and denote the endpoints of the respective edges (after a suitable reindexing) by $q_1,q_2,q_3,q_4$.
			Let $D$ and $D'$ be the pseudo-disks in $\F$ whose intersections with $S$ is $\{q_1,q,q_3\}$ and $\{q_2,q,q_4\}$, respectively.
			Since the Delaunay-edges are drawn such that they are contained in every pseudo-disk that contains their endpoints, it follows that our drawn curves lie inside $D$ and $D'$, respectively.
			Moreover, by Lemma~\ref{lem:buzaglo} they must cross an even number of times.
			Since the parts outside $C(p)$ are disjoint, and inside $C(p)$ the two segments can cross at most once, we get a contradiction.
			Therefore, we have proved that with this drawing $J$ is a plane graph.\qedwhite
		\end{proof}

	Since $J$ is a planar graph, it is $4$-colorable. We use a $4$-coloring of $J$ to color the Delaunay-edges of $D$.
	Now suppose that $D \in \F$ is a pseudo-disk that contains at least three points.
	Since $\F$ is shrinkable, it follows that there is a pseudo-disk $D' \in \F$ that contains exactly three points from $S \cap \F$.
	Lemma~\ref{lem:shrink} also implies that each of the three points from $S$ inside $D'$ is connected by a Delaunay-edge to one of the other two points. Therefore, $D'$ contains two Delaunay-edges that share a common endpoint and thus are colored with different colors.\qedwhite
\end{proof}

Note that Theorem~\ref{thm:pseudo} implies the same for saturated pseudo-disk families as a saturated family is always shrinkable. The following result concerning homothets of a convex compact set is also implied by Theorem~\ref{thm:pseudo}.

Let $C$ be a convex compact set and let $\partial C$ denote its boundary. We say that a set of points $S$ is in \emph{general position} with respect to $C$, if there is no homothet of $C$ that contains more than three points of $S$ on its boundary and no two points in $S$ define a line that is parallel to a line-segment which is contained in $\partial C$.

\begin{corollary} \label{cor:homothets}
	Let $C$ be a convex compact set and let $S$ be a finite planar set of points that is in general position with respect to $C$.
	Then it is possible to $4$-color the Delaunay-edges of $S$ with respect to the family of homothets of $C$ such that every homothet of $C$ that contains at least three points from $S$ contains Delaunay-edges of different colors.
\end{corollary}

\begin{proof}

	Let $\F$ be a finite subfamily of the set of homothets of $C$ such that if $C'$ is a homothet of $C$, then there is $C'' \in \F$ such that $C'' \cap S = C' \cap S$. One can show along the lines of the proof of Lemma~2.3 in~\cite{AKV15} that this subfamily is shrinkable with respect to $S$.

	We may assume that for every $C_1,C_2 \in \F$ the boundaries
	$\partial C_1$ and $\partial C_2$ intersect a finite number of times.
	Indeed, if there are overlaps between boundaries, then we can slightly inflate one of the homothets, say $C_1$, without changing $C_1 \cap S$ since $C_1$ is closed.

	It follows from the next folklore lemma (see, e.g., \cite[Corollary 2.1.2.2]{Ma2000}), that $\F$ is a family of pseudo-disks.

	\begin{lemma}
		\label{lem:pseudo-disks}
		Let $C$ be a convex and compact set and let $C_1$ and $C_2$ be homothets of $C$.
		Then if $\partial C_1$ and $\partial C_2$ intersect finitely many times, then they intersect in at most two points.
	\end{lemma}

	Since $\F$ is also shrinkable, the corollary now follows from Theorem~\ref{thm:pseudo}.\qedwhite
\end{proof}

\subsection{Coloring Delaunay-edges with respect to halfplanes}\label{sec:hp}

Let $S$ be a finite set of points in the plane and let $\F$ be the family of halfplanes. Note that a halfplane may contain an arbitrary number of points from $S$ while containing only one Delaunay-edge of $D(S,\F)$, see Figure~\ref{fig:halfplanes-many} for an example.
\begin{figure}
	\centering
	\begin{subfigure}[b]{0.4\textwidth}
		\includegraphics[width=\textwidth]{halfplanes-many}
		\caption{}
		\label{fig:halfplanes-many}
	\end{subfigure}
	\hspace{1cm}
	\begin{subfigure}[b]{0.4\textwidth}
		\includegraphics[width=\textwidth]{halfplanes}
		\caption{}
		\label{fig:halfplanes}
	\end{subfigure}
	\caption{(a) A halfplane may contain many points but only one Delaunay-edge. (b) Coloring the Delaunay-edges.}
\end{figure}
Therefore a claim along the lines of, e.g., Theorem~\ref{thm:bless} is impossible.
Thus, Theorem~\ref{thm:halfplanes} states that the edges of the Delaunay-graph $D(S,\F)$ can be $2$-colored such that every halfplane that contains at least three \emph{Delaunay-edges} contains two differently colored edges..

\begin{proof}[Proof of Theorem~\ref{thm:halfplanes}]
	For simplicity we assume that the points are in general position, as it is easy to modify the proof so that it works for points that are not in general position.

	Let $S$ be a finite set of points in the plane and let $\F$ be the family of halfplanes. The convex hull of $S$, $\CH(S)$, is a convex polygon whose vertices are points from $S$. Note that for each of the Delaunay-edges in the Delaunay-graph $D(S,\F)$ at least one of the two endpoints is a vertex of $\CH(S)$.
	Thus, $D(S,\F)$ consists of the sides of $\CH(S)$ and stars centered at each of the vertices of $\CH(S)$.

	Starting from an arbitrary vertex of $\CH(S)$ we go over all the Delaunay-edges adjacent to this vertex in a counter-clockwise order and color them alternatively with red and blue. Then we move to the next vertex of $\CH(S)$ in a clockwise order.
	Repeat the same process (the first edge adjacent to it is already colored), and so on until all the edges are colored (see Figure~\ref{fig:halfplanes} for an example).

	Let $e_1,e_2,\ldots,e_k$ be the Delaunay-edges listed in the order they were visited by the coloring algorithm.
	Note that every pair of consecutive edges are of different colors, except perhaps $e_1$ and $e_k$ which are of the same color if $k$ is odd.

	\begin{proposition}\label{prop:consecutive}
		If a halfplane $H$ contains two Delaunay-edges $e_i$ and $e_j$, $i<j$, then $H$ contains the edges $e_{j+1},\ldots,e_k,e_1,\ldots,e_{i-1}$ or the edges $e_{i+1},\ldots,e_{j-1}$.
	\end{proposition}

	\begin{proof}
		Suppose first that $e_i$ and $e_j$ share a vertex of $\CH(S)$ as an endpoint and denote it by $v$.
		Assume without loss of generality that all the edges $e_i,\ldots,e_j$ are incident to $v$ and let $v_l$ denote the other endpoint of $e_l$, $l=i,\ldots,j$.
		Assume for contradiction that $H$ does not contain $e_l$ for some  $i < l < j$.
		It follows that $v, v_i, v_l, v_j$ are in convex position such that this is also their clockwise or counter-clockwise order around their convex hull.
		However, then there cannot be a halfplane that separates $\{v,v_l\}$  from $\{v_i,v_j\}$ contradicting the fact that $\{v,v_l\}$ is a Delaunay-edge.

		Suppose now that $e_i$ and $e_j$ are disjoint and let $u$ and $u'$ be vertices of $\CH(S)$ such that $u$ is an endpoint of $e_i$ and $u'$ is an endpoint of $e_j$.
		Let $U$ be the vertices of $\CH(S)$ in the clockwise order from $u$ to $u'$, and assume without loss of generality that $H$ contains all of them (this can be assumed since if $H$ does not contain all of them, then it must contain all the vertices of $\CH(S)$ from $u'$ to $u$).
		We may also assume that $e_{i+1},\ldots,e_{j-1}$ are incident to the vertices in $U$.

		We claim that $H$ must contain each of these edges.
		Indeed, suppose that $H$ does not contain $e_l$, for some $i < l < j$.
		If none of $u$ and $u'$ is an endpoint of $e_l$, then let $u'' \in U$ be one of its endpoints and let $v_l$ be its other endpoint.
		As in the previous case, it follows that $u,u'',u',v_l$ are in convex position such that this is also their clockwise order around their convex hull.
		However, then there cannot be a halfplane that separates $\{u'',v_l\}$  from $\{u,u'\}$.
		Finally, suppose that one endpoint of $e_l$ is, without loss of generality, $u$ and let $v_l$ be its other endpoint. Denote also by $v_i$ the other endpoint of $e_i$.
		Then, as before, it follows that $u,v_i,v_l,u''$ are in convex position in this cyclic order. However, there should be a halfplane that separates $\{u,v_l\}$ from the other two vertices which is impossible.\qedwhite
	\end{proof}

	Suppose that $H \in \F$ is a halfplane that contains at least three Delaunay-edges. Then it follows from Proposition~\ref{prop:consecutive} that $H$ contains at least three consecutive Delaunay-edges and therefore it contains two edges of different colors.

	To see that the constant three in the theorem is tight,
	note that when $S$ is a set of an odd number of points in convex position, then it is impossible to $2$-color the Delaunay-edges of $D(S,\F)$ such that every halfplane that contains two Delaunay-edges contains edges of both colors. \qedwhite
\end{proof}

\subsection{Coloring Delaunay-edges with respect to bottomless rectangles}\label{sec:bless}

A \emph{bottomless} rectangle is the set of points $\{(x,y) \mid a \le x \le b, y \le c\}$ for some numbers $a,b,c$ such that $a \le b$.
Let $\F$ be the set of bottomless rectangles and let $S$ be a finite set of points in the plane.
As in the previous section, we may assume that no two points in $S$ share the same $x$- or $y$-coordinates.
It is known~\cite{K11} that it is possible to color the points in $S$ with two colors such that every bottomless rectangle that contains at least four points from $S$ contains two points of different colors.
This easily implies that the Delaunay-edges of $D(S,\F)$ can be colored with two colors such that every bottomless rectangle that contains at least five points from $S$ contains two Delaunay-edges of different colors.
Indeed, color first the points of $S$ such that every bottomless rectangle that contains four points from $S$ is non-monochromatic.
Then color every Delaunay-edge with the color of its leftmost endpoint.
Suppose that $R \in \F$ contains at least five points from $S$ and let $p_i$ be the $i$th point in $R \cap S$ from left to right.
There is a bottomless rectangle $R'$ such that $R' \cap S = \{p_1,p_2,p_3,p_4\}$, therefore there are two differently colored points among these points.
Since $\{p_i,p_{i+1}\}$ is a Delaunay-edge for every $i$, it follows that $R$ contains two Delaunay-edges of different colors.

Next we prove Theorem~\ref{thm:bless}. Namely, that containing four points from $S$ suffices for a bottomless rectangle to contain Delaunay-edges of different colors and this is tight. The proof is similar to proof of the aforementioned statement in~\cite{K11}.

\begin{proof}[Proof of Theorem~\ref{thm:bless}]
	We add the points in $S$ one-by-one from bottom to top.
	Note that any Delaunay-edge that is introduced when a point is added,
	remains a Delaunay-edge when adding the remaining points.

	At any moment call an edge \emph{neighborly} if it connects points that are next to each other in the horizontal order of points.
	Denote the points added so far by their order from left to right, $p_1,p_2,\ldots,p_k$, and let $p_i$ be the last point to be added.
	Thus, the neighborly edges are $\{p_j,p_{j+1}\}$, for $j=1,\ldots,k-1$.
	We maintain the invariant that there are no three consecutive neighborly edges of the same color.
	This is trivial to obtain for $k \le 3$, so assume that $k \ge 4$.
	When $p_i$ is added, it introduces either one (if $i=1$ or $i=k$) or two new neighborly edges (and causes an existing edge to cease being a neighborly edge).
	In the first case we color the new edge with a color that is different from the color of the single neighborly edge that shares an endpoint with the new edge.
	In the second case, if $i=2$ (resp., $i=k-1$), then we color the new edges $\{p_1,p_2\}$ and $\{p_2,p_3\}$ (resp., $\{p_{k-2},p_{k-1}\}$ and $\{p_{k-1},p_{k}\}$)
	with a color that is different from the color of $\{p_{3},p_{4}\}$ (resp., $\{p_{k-3},p_{k-2}\}$).
	When $2 < i < k-1$ there are two cases to consider:
	If $\{p_{i-2},p_{i-1}\}$ and $\{p_{i+1},p_{i+2}\}$ are of the same color, then we color the new edges $\{p_{i-1},p_{i}\}$ and $\{p_{i},p_{i+1}\}$ with the opposite color.
	Otherwise, if $\{p_{i-2},p_{i-1}\}$ and $\{p_{i+1},p_{i+2}\}$ are of different colors, then $\{p_{i-1},p_{i}\}$ is colored with the color of $\{p_{i+1},p_{i+2}\}$ and $\{p_{i},p_{i+1}\}$ is colored with the color of  $\{p_{i-2},p_{i-1}\}$.
	It is easy to verify that the invariant that there are no three consecutive neighborly edges of the same color is maintained in all cases.

	Suppose now that $R$ is a bottomless rectangle that contains at least four points.
	When the topmost point from $S \cap R$ was added, then all the points in $S \cap R$ formed $|S \cap R|-1 \ge 3$ consecutive neighborly edges.
	Therefore, not all of these edges are of the same color.
	Since these edges remain Delaunay-edges (perhaps non-neighborly) when the remaining points are added, $R$ contains Delaunay-edges of both colors.

	To see that it is not enough to consider bottomless rectangles that contain three points from $S$, consider the point set in Figure~\ref{fig:bless3} and assume it is colored as required.
	\begin{figure}
		\centering
		\includegraphics[width=5cm]{bless3}
		\caption{Considering bottomless rectangles containing three points is not enough.}
		\label{fig:bless3}
	\end{figure}
	Assume without loss of generality that $\{p_1,p_2\}$ is red.
	Then $\{p_2,p_3\}$ and $\{p_2,p_4\}$ must be both blue.
	This implies that $\{p_4,p_5\}$ must be red, and so $\{p_3,p_4\}$ must be blue.
	Therefore, all the Delaunay-edges in the bottomless rectangle that contains $p_2$, $p_3$ and $p_4$ are blue, a contradiction. \qedwhite
\end{proof}

\subsection{Coloring Delaunay-edges with respect to axis-parallel rectangles}\label{sec:ap}

For a partially ordered set $P=(X,\le)$ we say that $x \in X$ is an \emph{immediate predecessor} of $y \in X$ if $x < y$ and there is no $z \in X$ such that $x < y < z$ (where $x < y$ means that $x \le y$ and $x \ne y$).
The \emph{directed Hasse diagram} of $P$ is the directed graph $(X, \{ (x,y) \mid x$ is an immediate predecessor of $y\})$.
The following is easy to prove.

\begin{lemma}\label{lem:hasse}
	Let $P=(X,\le)$ be a partially ordered set such that $X$ is finite.
	Then it is possible to color the edges of the directed Hasse diagram of $P$
	with $\lceil \log_2 |X| \rceil$ colors such that there is no monochromatic path of length two.
\end{lemma}

\begin{proof}
	Denote $n=|X|$.
	It is enough to prove the lemma for $n=2^k$, $k \in \mathbb{N}$.
	We prove by induction on $k$.
	For $k=0$ the lemma holds.
	Let $P=(X,\le)$ be a poset where $|X|=n=2^k$ and $k>0$.
	Let $P^*=(X,\le^*)$ be a linear extension of $P$ and let $x_1 \le^* x_2 \le^* \ldots \le^* x_n$ be the elements of $X$ ordered according to $P^*$.
	Set $P_1=(X_1=\{x_1,\ldots,x_{n/2}\},\le)$ and  $P_2=(X_2=\{x_{n/2+1},\ldots,x_{n}\},\le)$.
	By the induction hypothesis the edge set of each of the directed Hasse diagrams of $P_1$ and $P_2$ can be colored with (the same set of) $k-1$ colors such that there is no monochromatic path of length two.

	By using the same coloring for the edges of the directed Hasse diagram of $P$ and introducing a new color for the edges $\{(x,y) \mid x \in X_1, y \in X_2\}$ we obtain the required coloring. \qedwhite
\end{proof}

\paragraph{Remark.}
The number of colors in Lemma~\ref{lem:hasse} cannot be an absolute constant.
In fact, for any integer $d>0$ there is no integer $c=c(d)$ such that it is possible
to color the edges of the directed Hasse diagram of any finite poset with $c$ colors
such that there is no monochromatic path of length $d$.
To see this, observe that if such an integer would exist, then it would be possible to properly color the vertices of the Hasse diagram of any poset $P$ with $O(1)$ colors which is known to be false~\cite{chenpach,KN91}.
Indeed, it is easy to verify that by assigning each vertex $v$ the color $(c',d')$ where $d'$ is the length of the longest monochromatic path ending at $v$ (in the directed Hasse diagram of $P$) and $c'$ is the color of that path one obtains a proper coloring with $O(1)$ colors.

\begin{corollary}
	Let $S$ be a finite set of $n$ points in the plane and let $\F$ be the family of
	axis-parallel rectangles.
	Then it is possible to color the edges of the (non-planar) Delaunay-graph $D(S,\F)$ with $O(\log n)$ colors such that every axis-parallel rectangle that contains at least three points from $S$ contains Delaunay-edges of different colors.
\end{corollary}

\begin{proof}
	We may assume without loss of generality that no two points in $S$ share the same $x$- or $y$-coordinates.\footnote{Note that we cannot just take an arbitrary perturbation, as we did for points. For example, if we have 3 collinear points inside a rectangle (thus two Delaunay-edges) we might introduce a new Delaunay-edge with an arbitrary perturbation.} Indeed, this can be obtained by a mapping $(x,y) \mapsto (x+\varepsilon y, y+\varepsilon x)$ for a very small $\varepsilon$ (that depends on $S$) without changing the hyperedges of $G(S,\F)$.

	Orient every edge of $D(S,\F)$ from left to right.
	Let $P_1=(S,\prec_1)$ where $(x,y) \prec_1 (x',y')$ if $x < x'$ and $y < y'$.
	Let $P_2=(S,\prec_2)$ where $(x,y) \prec_2 (x',y')$ if $x < x'$ and $y > y'$.
	Note that the edge set of the oriented Delaunay-graph is the union of the (disjoint) edge sets of the directed Hasse diagrams of $P_1$ and $P_2$.
	Therefore, it follows from Lemma~\ref{lem:hasse} that we can color these edges with $2\lceil\log_2 n\rceil$ colors such that there is no monochromatic path of length two.

	Let $R' \in \F$ be an axis-parallel rectangle that contains at least three points from $S$ and let $p_1,p_2,p_3$ be the leftmost points in $R'$, ordered from left to right.
	Then $(p_1,p_2)$ and $(p_2,p_3)$ are edges in the oriented Delaunay-graph $D(S,\F)$.
	If they belong to different Hasse diagrams, then they are of different colors.
	Otherwise, if they belong to the same Hasse diagram, then they are of different colors since they form a path of length two. \qedwhite
\end{proof}

\section{Coloring all \texorpdfstring{$t$}{t}-tuples of abstract hypergraphs}\label{sec:allthyp}

Henceforth we consider colorings of \emph{all} the (unordered) $t$-tuples of points.
In this section we show some general results that do not rely on geometry assumptions.
First, intuitively, as the number of all $t$-tuples increases considerably by increasing $t$, the coloring problem should become easier or at least not become (significantly) harder.
The next claim confirms this intuition in the following sense: proper $k$-colorability of $t$-tuples implies proper $2$-colorability of $t'$-tuples for $t'>t$ (while the corresponding $m$ might increase).

\begin{proposition}\label{prop:chi}
	Let $G$ be a hypergraph and suppose that for some positive integers $t$, $k$ and $m$ the $t$-tuples of the vertices of $G$ can be $k$-colored such that every hyperedge that contains at least $m$ vertices contains two differently colored $t$-tuples.
	Then for every integer $t' > t$ there exists an integer $m'=m'(t')$ such that the $t'$-tuples of the vertices of $G$ can be $2$-colored such that every hyperedge that contains at least $m'$ vertices contains two differently colored $t'$-tuples.
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{prop:chi}]
	We construct a coloring $c'$ of $t'$-tuples from the coloring $c$ of $t$-tuples.
	The color of a $t'$-tuple $T$ is red if every $t$-tuple of the vertices of $T$ is colored with the same color by $c$, and blue otherwise.
	By Ramsey's Theorem (for hypergraphs) we can choose $m'\ge m$ such that in any coloring of all $t$-tuples of a set of size $m'$ there is a monochromatic $t'$-tuple, i.e., whose every subset of size $t$ got the same color.
	This way in $c'$ every set of size at least $m'$ (and so also every hyperedge of size at least $m'$) contains a red $t'$-tuple. Also, in the coloring $c$ every hyperedge in $G$ of size $m\le m'$ was not monochromatic, thus such a hyperedge also contains a blue $t'$-tuple.\qedwhite
\end{proof}

One can of course can get better bounds on $m'$ if we construct a coloring more carefully instead of using Ramsey's theorem.
The following is such a claim for $t=1$ about polychromatic $k$-colorability.
We denote by $[n]$ the set $\{1,2,\ldots,n\}$ and by ${A}\choose{k}$ the $k$-element subsets
of a set $A$.

\begin{proposition}\label{prop:mk}
	Let $G=(V,E)$ be a hypergraph and let $k$ and $m$ be integers such that the vertices of $G$ can be $k$-colored such that every hyperedge of $G$ that contains at least $m$ vertices contains a vertex of each of the $k$ colors.
	Then for every integer $t'>1$ there are integers $k'=k'(k,t')$ and $m'=m'(m,k,t')$ such that there exists a $k'$-coloring of the $t'$-tuples of the vertices of $G$ such that every hyperedge of $G$ that contains at least $m'$ vertices contains a $t'$-tuple of each of the $k'$ colors.
	In particular, the above holds for $k'=\binom k{t'}+\sum_{i=0}^{t'-2} \binom{k-1}i$
	and $m'=\max\{m,k(t'-1)+1\}$ (note that $k'\ge k$ and if $t'>k$ then $k'=2^{k-1}$).

\end{proposition}

\begin{proof}
	Let $c:V \rightarrow [k]$ be a $k$-coloring of the vertices of $G$ as above,
	and set $k'=\binom k{t'}+\sum_{i=0}^{t'-2} \binom{k-1}i$.
	We will construct a $k'$-coloring $c'$ of the $t'$-tuples of vertices of $G$ such that $c'$ is a mapping to the union of the $t'$-element subsets of $[k]$ and the $i$-element subsets of $[k-1]$, for $i=0,\ldots,t'-2$. Thus, there are indeed $k'$ colors.

	The color of each $t'$-tuple $T$ will be determined by the multiset of the colors of its vertices, $c(T):=\{c(v) \mid v\in T\}$, as follows:

	\begin{itemize}
		\item If no color appears twice in $c(T)$ (only possible if $t'\le k$), then $c'(T)$ is the $t'$-element subset of $[k]$ defined by those colors, i.e., $c'(T)=c(T)$.
		\item If exactly one color (say, $r$) appears at least twice in $c(T)$ and each of the other $i$ colors in $c(T)$ appears once, then $c'(T)$ will be an $i$-element subset of $[k-1]$, determined as follows. Define a bijection $\varphi_r$ between $[k]\setminus \{r\}$ and $[k-1]$ such that $\varphi_r(j)=j-r$ for $r+1\le j\le k$ and $\varphi_r(j)=j-r+k$ for $1\le j\le r-1$. Then $c'(T)=\{\varphi_r(c(v)) \mid v\in T, c(v) \ne r\}$.
		\item Otherwise, define $c'(T)$ arbitrarily.
	\end{itemize}

	Now we need to show that all $k'$ colors appear in a hyperedge $e$ of size $m'=\max\{m,k(t'-1)+1\}$.
	Note that among the vertices of $e$ we have all $k$ colors from $[k]$ since $m' \ge m$.
	Let $U=\{v_1,v_2,\ldots,v_k\} \subseteq e$ be a set of vertices such that $c(v_i)=i$.
	If $t' \le k$, then the $\binom{k}{t'}$ $t'$-tuples of vertices from $U$ are colored by all colors in  $\binom{[k]}{t'}$.

	Now let $A$ be an $i$-element subset of $[k-1]$, for some $0 \le i \le t'-2$.
	By the pigeonhole principle there is a subset $U' \subseteq e$ of $t'$ vertices that are colored by the same color $r \in [k]$.
	Suppose that $T$ is a $t'$-tuple that consists of $t'-i \geq 2$ vertices from $U'$
	and every vertex $v_j \in U$ such that $\varphi_r(j) \in A$.
	Since $\varphi_r$ is a bijection there are $i$ such vertices and it follows that $c'(T)=A$.\qedwhite
\end{proof}

Surprisingly, such simple arguments fail for $t\ge 2$.
Below we give an example for $t=2$, $t'=3$ and $k=3$.

Suppose we are given a $3$-coloring of every pair of the vertex set of a hypergraph $G$ such that every hyperedge that contains at least $m$ vertices contains a pair of each of the $3$ colors, and we want to construct a $3$-coloring of the triples of vertices with the same property (possibly for a larger $m'$).
We show that this is not possible if the color of each triple depends only on the colors of the three pairs in it:

\begin{proposition}\label{prop:nocol}
	There is no mapping $\hat c$ from the $3$-element multisets of $[3]$ to $[3]$ such that the following holds for some $m'(m)$.
	For every hypergraph $G=(V,E)$ if $c:{{V}\choose{2}} \rightarrow [3]$ is a $3$-coloring of the pairs of vertices of $G$ such that every hyperedge that contains at least $m$ vertices contains pairs of all three colors, then $c$ and $\hat c$ defines a $3$-coloring $c':{{V}\choose{3}} \rightarrow [3]$ of the triples of vertices of $G$ such that every hyperedge that contains at least $m'(m)$ vertices contains triples of all three colors (where $c'(\{x,y,z\})=\hat c(\{c(\{x,y\}),c(\{x,z\}),c(\{y,z\})\})$ for every triple of vertices $\{x,y,z\}$).
\end{proposition}

\begin{proof}
	Suppose for contradiction that $\hat c$ and $m'$ as above exist.
	Note that there are ten $3$-element multisets of $[3]$, that is,
	there are ten possible colorings of the three pairs of a triple by $3$-colors: $\{1,1,1\}$, $\{1,1,2\}$, $\{1,1,3\}$, $\{2,2,1\}$, $\{2,2,2\}$, $\{2,2,3\}$, $\{3,3,1\}$, $\{3,3,2\}$,  $\{3,3,3\}$ and $\{1,2,3\}$.

	Let $G_1=(V_1,E_1)$ be a hypergraph such that $|V_1| = \max\{m,m'(m)\}$ and let $P_1 \subseteq {{V_1}\choose{2}}$ and $P_2 \subseteq {{V_1}\choose{2}}$ be two sets of pairs of vertices, such that no vertex belongs to two pairs in $P_1 \cup P_2$.
	Let $E_1$ consists of the hyperedge $V_1$ (all the vertices) and all the subsets of $V_1$ of size $\max\{m,4\}$ that contain a pair from $P_1$ and a pair from $P_2$.

	Suppose that $c_1$ is a $3$-coloring of the pairs in ${{V_1}\choose{2}}$ such that the color of every pair in $P_i$ is $i$, for $i=1,2$, and the color of every other pair is $3$.
	Then clearly every hyperedge of size at least $m$ contains a pair of each of the colors.
	Note that the colors of the three pairs defined by a triple of vertices is either
	$\{3,3,1\}$, $\{3,3,2\}$ or $\{3,3,3\}$.
	Consider the coloring of the triples as defined by $c_1$ and $\hat c$.
	Since the hyperedge $V_1$ must contain a triple of every color, it follows that $\hat c$ maps
	each of the above $3$-multisets of colors to a different color.

	Suppose now that $G_2=(V_2,E_2)$ is a hypergraph such that $|V_2| = 2\cdot\max\{m,m'(m)\}$ and let $A=\{a_1,a_2,\ldots,a_{|V_2|/2}\}$ and $B=\{b_1,b_2,\ldots,b_{|V_2|/2}\}$ be two disjoint subsets of vertices.
	Let $E_2$ consists of the hyperedge $V_2$ (all the vertices) and all the hyperedges $A \cup \{b_i\}$ and $B \cup \{a_i\}$, for some $i$.
	Let $P_1$ be the pairs of vertices of the form $\{a_i,a_j\}$ or $\{b_i,b_j\}$ (for $i \ne j$),
	Let $P_2$ be the pairs of vertices of the form $\{a_i,b_i\}$,
	and let $P_3$ be the (remaining) pairs of vertices of the form $\{a_i,b_j\}$ (for $i \ne j$).

	Suppose that $c_2$ is a $3$-coloring of the pairs in ${{V_2}\choose{2}}$ such that the color
	of every pair in $P_i$ is $i$, for $i=1,2,3$.
	Then clearly every hyperedge of size at least $m$ contains a pair of each of the colors.
	Note that the colors of the three pairs defined by a triple of vertices is either
	$\{1,1,1\}$, $\{1,2,3\}$ or $\{3,3,1\}$.
	Consider the coloring of the triples as defined by $c_2$ and $\hat c$.
	Since the hyperedge $V_2$ must contain a triple of every color, it follows that $\hat c$ maps
	each of the above $3$-multisets of colors to a different color.
	Therefore, 	$\{1,2,3\}$ is mapped to a color different from the colors of $\{1,1,1\}$ and $\{3,3,1\}$.
	Similarly, if we color the pairs in $P_1$ with $2$, the pairs in $P_2$ with $1$ and the pairs in $P_3$ with $3$, then we conclude that $\hat c$ maps $\{1,2,3\}$ to a color different from the colors of $\{2,2,2\}$ and $\{3,3,2\}$.
	And if we color the pairs in $P_1$ with $3$, the pairs in $P_2$ with $2$ and the pairs in $P_3$ with $1$, then we conclude that $\hat c$ maps $\{1,2,3\}$ to a color different from the colors of $\{3,3,3\}$ and $\{1,1,3\}$.
	Thus, according to $\hat c$ the color of $\{1,2,3\}$ is different from the colors of $\{3,3,1\}$, $\{3,3,2\}$ and $\{3,3,3\}$. However, we observed before that $\hat c$ maps these three $3$-multisets of colors to different colors, a contradiction.\qedwhite
\end{proof}

It is possible to change the constructions in the proof of Proposition~\ref{prop:nocol} such that every hyperedge that contains at least $m$ vertices contains many pairs of each of the colors, so even such an assumption is not strong enough to guarantee a coloring for triples.
One might try to get a $k$-coloring of $t'$-tuples from stronger conditions on the coloring of the $t$-tuples, however, we do not further study this question.

\section{Coloring all $t$-tuples of geometric hypergraphs}\label{sec:alltgeom}

In this section we consider mainly three (closely related) types of families of geometric regions, $\HH$-regions, homothets of a convex polytope and axis-parallel boxes.

Given $\cal F$ and $S$, we want to color all $t$-tuples of $S$ such that no member of $\cal F$ that has many points of $S$ is monochromatic, i.e., it contains two $t$-tuples that are colored with different colors.

\begin{definition}
	Given a finite family of halfspaces $\HH=\{H_1,\dots, H_h\}$ we call a region $R$ an \textbf{$\HH$-region} if it is the intersection of finitely many halfspaces, such that each of them is a translate of one of the halfspaces in $\HH$.
\end{definition}
Note that every such region $R$ can be expressed as an intersection of at most $h$ halfplanes (at most one translate of each $H_i$).

Throughout this section we assume, without loss of generality, that any given point set $S$ is in general position in the sense that there are no two points in $S$ that are contained in $\partial H_i$ for some $H_i \in \HH$, where $\partial H_i$ denotes the hyperplane that bounds the halfspace $H_i$.
Indeed, otherwise after a small perturbation of the points of $S$

for every subset $S' \subseteq S$ that is the intersection of $S$ and some $\HH$-region, the perturbed subset $S'$ is still the intersection of (the perturbed) $S$ and some (possibly different) $\HH$-region.

\begin{comment}
Since we consider only sets of points in general position we have the following lemma that will be useful later.

\begin{lem}\label{lem:shrink}
Let $R$ be an $\HH$-region with respect to a set of halfspaces $\HH$ and let $S$ be a set of points, such that $|S \cap R| = k$.
Then for every integer $0 \leq i \leq k$, there is an $\HH$-region $R_i \subseteq R$ that contains exactly $i$ points from $S \cap R$.
\end{lem}

\begin{proof}
Let $H$ be one of the halfspaces in $\HH$ and let $H'$ a translate of $H$ that contains $R$. Thus $|H' \cap (R \cap S)| = k$. Since $S$ is in general position, for every $0 \leq i \leq k$ it is possible to continuously translate $H'$ (such that it is still a translate of $H$) until $|H' \cap (R \cap S)| = i$.
\end{proof}

We recall the statement of Theorem~\ref{thm:region}.

\begin{repeatthm}[Theorem~\ref{thm:region}]
	For every dimension $d$
	and integers $t\ge 2$, $k \ge 1,h\ge 1$ there exists an integer $m=m(t,k,h)$ with the following property: given a finite family of $h$ halfspaces $\HH$ in $\mathbb{R}^d$, the $t$-tuples of every finite set of points $S$ in $\mathbb{R}^d$ can be $k$-colored such that every $\HH$-region that contains at least $m$ points from $S$ contains a $t$-tuple of points of each of the $k$ colors.
\end{repeatthm}

We postpone the proof of this theorem for a bit later.
\end{comment}

As mentioned in the Introduction, the requirement that $t \geq 2$ in Theorem~\ref{thm:region} is essential.
Indeed, Chen et al.~\cite{chenpach} proved that there is no absolute constant $m$ with the property that every set of points $S$ in the plane can be $2$-colored such that every axis-parallel rectangle that contains at least $m$ points from $S$ contains points of both colors.
Note that axis-parallel rectangles can be defined as the $\HH$-regions of four halfplanes.
Several other constructions about polychromatic colorings/cover-decomposition can also be realized as the $\HH$-regions of four halfplanes; see \cite{PTT05,P10}.
If there are only three halfspaces in $\HH\subset \mathbb{R}^3$ that are in general position, then after an affine transformation the problem becomes equivalent to coloring points with respect to octants (non-general position and different dimension can only make the problem easier).
For this case, it was shown in \cite{KP11} that $m(1,k,3)$ exists for every $k$ (which implies the same for  $m(1,k,2)$ and  $m(1,k,1)$ although these can be shown directly as well).

\begin{comment}
\begin{remark} The same proof works for higher dimensional halfspaces as well (unlike for polychromatic colorings, where $d$-dimensional halfspaces do not admit a polychromatic coloring, except for $d\le 2$).
\end{remark}
\end{comment}

Note that a homothet of a convex polytope $P$ is a $\HH$-region when $\HH$ is the family of all the supporting halfspaces of $P$.
Thus Theorem \ref{thm:region} implies:

\begin{theorem}\label{thm:homoth}
	For every dimension $d$,
	integers $t \geq 2$, $k \ge 1$ and a convex polytope $P$ in $\mathbb{R}^d$ there exists an integer $m=m(t,k,P)$ with the following property: the $t$-tuples of every finite point set $S$ in $\mathbb{R}^d$ can be $k$-colored such that every homothet of $P$ that contains at least $m$ points from $S$ contains a $t$-tuple of points of each of the $k$ colors.
\end{theorem}

As mentioned above, it is impossible to $2$-color points (that is, the case $t=1$) with respect to $\HH$-regions
in the plane such that every region that contains a constant number of points (for some absolute constant)
contains a point of each color.
However, for homothets of a convex polygon it might be possible.
The following is an equivalent restatement (by the self-coverability of convex polygons \cite{KP13}) of a conjecture that first appeared in \cite{AKV15}.

\begin{conjecture}\label{conj:poly}
	For every convex polygon $C$ and a positive integer $k$ there exists an integer $m=m(k,C)$ with the following property: the points of every finite point set $S$ in the plane can be $k$-colored such that every homothet of $C$ that contains at least $m$ points from $S$ contains a point of each of the $k$ colors.
\end{conjecture}

We note that Theorem \ref{thm:homoth} for $d=2$ would be implied by Conjecture \ref{conj:poly} using Theorem~\ref{thm:t-ind} (see below), however, Conjecture~\ref{conj:poly} was verified only for triangles~\cite{K13} and parallelograms~\cite{AKV15}.
Recently, a relaxation of this conjecture was proved in \cite{KP16}, namely, that it is possible to $3$-color the points such that each homothet with enough points contains points of at least two colors.

The conjecture fails in $d\ge 3$ for every polytope \cite{P10}.

We have seen that for general hypergraphs we could not show that polychromatic colorability of $t$-tuples implies the same for $t'$-tuples, $t'>t$. On the other hand we give a simple argument proving this for $\HH$-regions. This argument can also be adopted to work for most geometric families.

\begin{theorem}\label{thm:t-ind}
	Given a family of $h$ halfspaces $\HH$  in $\mathbb{R}^d$ and a positive integer $k$, suppose that for some positive integer $t$ there exists an integer $m=m(t,k,\HH)$ with the following property: the $t$-tuples of every finite point set $S$ in the plane can be $k$-colored such that every $\HH$-region that contains at least $m$ points from $S$ contains a $t$-tuple of each of the $k$ colors. Then the same property holds when exchanging $t$ with an integer $t' > t$ and $m$ with $m'=m+t'-t$.
\end{theorem}

\begin{proof}
	Let $H$ be a halfspace in $\HH$ and let $H'$ be a translate of $H$  that contains all the points in $S$.
	We fix an order of the points in $S$ in decreasing order of their distance from $\partial H'$ (recall that the points are in general position and therefore no two points can be at the same distance).
	Consider a coloring of the $t$-tuples having the property assumed by the theorem and
	let $T = \{p_1,p_2,\ldots,p_t,\ldots,p_{t'}\}$ be a $t'$-tuple of points, where the points are listed according to the determined order
	(that is, $p_1$ is the farthest from $\partial H'$ and so on).
	Set the color of $T$ to be the color of the $t$-tuple  $\{p_1,p_2,\ldots,p_t\}$.

	Let $m=m(t,k,\HH)$ and $m'=m+t'-t$ and suppose that $R$ is an $\HH$-region that contains at least $m'$ points from $S$, denote them by $p_1, p_2, \ldots, p_l$ according to their order.
	Since $S$ is in general position, it is possible to continuously translate $H'$ such that it is still a translate of $H$, and obtain a translate $H''$ of $H$ such that $H'' \cap (R \cap S) = \{p_1,p_2,\ldots,p_{l-(t'-t)}\}$.
	Note that $H'' \cap R$ is an $\HH$-region that contains at least $m$ points and therefore for each of the $k$ colors it contains a $t$-tuple of that color.
	Let $\{q_1,q_2,\ldots,q_t\}$ be such a $t$-tuple. Then $\{q_1,q_2,\ldots,q_t,p_{l-(t'-t)+1},\ldots,p_l\}$ is a $t'$-tuple of the same color that is contained in $R$. Therefore, $R$ contains a $t'$-tuple of each of the $k$ colors.\qedwhite
\end{proof}

\paragraph{Remark.}
Note that in the above proof we have only used that the points of $S$ can be ordered as $s_1,\ldots,s_{|S|}$ such that if $\{s_{i_1},\ldots,s_{i_m}\}= S\cap F$ for some $F\in \F$, then also $\{s_{i_1},\ldots,s_{i_{m-1}}\}= S\cap F'$ for some $F'\in \F$.
This implies that similar arguments work not only for $\HH$-regions but for other families as well, especially if we do not insist on $m' = m + t'-t$.

In order to prove Theorem \ref{thm:region}, we reduce the problem of coloring with respect to $\HH$-regions to coloring with respect to axis-parallel boxes (which are possibly higher dimensional). Note that axis-parallel boxes are also $\HH$-regions.

For a point $\mathbf{p} \in \mathbb{R}^d$ we denote by $(\mathbf{p})_i$ the $i$th coordinate of $\mathbf{p}$.
An \emph{axis-parallel} $d$-dimensional (closed) halfspace is a halfspace of the form $\{\mathbf{p} \mid (\mathbf{p})_i \leq \beta\}$ or $\{\mathbf{p} \mid (\mathbf{p})_i \geq \beta\}$ for some $1 \leq i \leq d$ and a number $\beta$.
A $d$-dimensional \emph{box} is the intersection of $d$-dimensional axis-parallel
halfspaces.
Theorem \ref{thm:region} follows from the next result.

\begin{theorem}\label{thm:box}
	For every integer $t\ge 2$ and positive integers $d,k$ there exists an integer $m=m(t,k,d) \le k^{2^{d-1}}+t-1$ with the following property: the $t$-tuples of every finite point set $S$ in the $d$-dimensional space can be $k$-colored such that every axis-parallel box that contains at least $m_k$ points contains $t$-tuples of points colored with each of the $k$ colors.
\end{theorem}

Before proving Theorem \ref{thm:box} we show how Theorem~\ref{thm:box} implies Theorem \ref{thm:region}.

\begin{proof}[Proof of Theorem \ref{thm:region} using Theorem \ref{thm:box}]
	Let $\HH=\{H_1,\dots, H_h\}$ be a set of halfspaces in $\mathbb{R}^d$ such that $H_i= \{\mathbf{x}:\mathbf{A}_i \cdot \mathbf{x} \leq 0\}$, where $\mathbf{x} = (x_1,x_2,\ldots,x_d)$ and $\mathbf{A}_i = (\alpha_{i,1}, \alpha_{i,2}, \ldots \alpha_{i,d})$ for $i=1,\ldots,h$.

	Let $f : \mathbb{R}^d \rightarrow \mathbb{R}^h$ be a mapping such that
	$f(\mathbf{x}) = (\mathbf{A}_1 \cdot \mathbf{x}, \ldots, \mathbf{A}_h \cdot \mathbf{x})$.
	Suppose that $\mathbf{p}$ is a point in $\mathbb{R}^d$ and $H= \mathbf{A}_i \cdot \mathbf{x} \leq \beta$ is the translate of some halfspace $H_i \in \HH$.
	Then clearly $\mathbf{p} \in H$ if and only if $(f(\mathbf{p}))_i \leq \beta$.

	Let $S$ be a set of points in $\mathbb{R}^d$ and let $R$ be an $\HH$-region that is the intersection of halfspaces $H_{i_1},\ldots, H_{i_l}$ such that $i_j \in \{1,2,..,h\}$ and
	$H_{i_j} = \mathbf{A}_{i_j} \cdot \mathbf{x} \leq \beta_j$, for $j=1,\ldots,l$.
	It follows that the points of $S$ that belong to $R$
	are exactly the points whose images under $f$ belong to the intersection
	of the set of $h$-dimensional axis-parallel halfspaces $(\mathbf{x})_{i_j} \leq \beta_j$, for $j=1,\ldots,l$.

	Since the intersection of $h$-dimensional axis-parallel halfspaces is a $h$-dimen\-sion\-al axis-parallel box, this completes the reduction from coloring with respect to $d$-dimensional $\HH$-regions to coloring with respect to $h$-dimensional axis-parallel boxes. From Theorem \ref{thm:box} we get that $m(t,k,h)=k^{2^{h-1}}+t-1$ is a suitable choice.\qedwhite
\end{proof}

It remains to prove Theorem~\ref{thm:box}.
The following result of Loh~\cite{poshenloh} will be useful. It is a simple application of a classic result known as the Gallai-Hasse-Roy-Vitaver theorem, but can also be proved by a simple application of the pigeonhole principle.
Recall that a \emph{tournament} is a complete oriented graph (between every pair of vertices there is exactly one directed edge).

\begin{theorem}\cite{poshenloh}\label{thm:poshenloh}
	For all positive integers $c$ and $n$, every $c$-coloring of the edges of every $n$-vertex
	tournament contains a monochromatic path with at least $n^{1/c}$ vertices.
\end{theorem}

The following notation will also be used in the proof of Theorem~\ref{thm:box}
and later on.
For two points $\p,\q \in \Rd$, we denote by $box(\p,\q)$ the smallest axis-parallel box that contains $\p$ and $\q$.
The \emph{directed type} of a vector is the sequence of signs of its coordinates.
For example, the directed type of $\vec{v} = (2,1,-3)$ is $(+,+,-)$.

\begin{proof}[Proof of Theorem \ref{thm:box}]

	It follows from Theorem \ref{thm:t-ind} that it is enough to consider the case $t=2$. That is, given a set of points $S$ in $\Rd$, we wish to color the edges of the complete graph on $S$, such that every box that contains enough points from $S$, contains an edge of each of the $k$ colors.

	Every pair of points $\p$ and $\q$ yields two vectors $\p \rightarrow \q$ and $\q \rightarrow \p$ with opposite directed types.
	Among these two vectors pick the one whose first sign is a $+$,
	and assign its direction and type to the edge $\{\p,\q\}$.
	Denote by $G$ the tournament we obtain by orienting every edge this way (that is, for every edge $\{\p,\q\}$, we direct it from $\p$ to $\q$ if and only if $(\mathbf{p})_1<(\mathbf{q})_1$.)

	Suppose that $\{\p,\q\}$ is a pair such that $(\p,\q)$ is an edge (with this direction) in $G$.
	Then the color of this pair and also of the edge $(\p,\q)$, is the minimum of $k$ and the length of the longest path from $\p$ to $\q$ in $G$ such that all the edges along this path have the same type as $(\p,\q)$ (we call such a path a \emph{monotone} path).

	Suppose that $\{\p,\q\}$ gets color $i$ and consider a monotone path of length $i$ from $\p$ to $\q$ in $G$ (assuming that $(\p,\q$) is the edge in $G$). Then for every $1\le j\le i$, if $\r$ is the point at distance $j$ from $\p$ on this path, then the edge $\{\p,\r\}$ must get color $j$. Observe also that all of these edges are in  $box(\p,\q)$. This implies that if a box contains an edge with color $i$, then it contains an edge with color $j$ for every $1\le j\le i$.

	Thus, it remains to prove that if a box contains at least $k^{2^{d-1}}+1$ points, then it contains an edge of color $k$.
	Since there are $2^{d-1}$ different types of directed edges and hence edge colors in $G$, it follows from Theorem \ref{thm:poshenloh} that $G$ contains a monochromatic directed path on $k+1$ vertices. This is by definition a monotone path of length $k$ between its two endpoints, thus the edge between these two endpoints must get color $k$, as required. \qedwhite

\end{proof}

In general the integer $m$ that we get from the proof of Theorem \ref{thm:box} is surely not the best possible. It follows from Theorem \ref{thm:t-ind} that an upper bound for $t=2$ yields a very similar upper bound for any larger $t$. Therefore, we may focus on coloring pairs of points. For the most natural case of axis-parallel rectangles in the plane and coloring pairs of points with two colors (that is, $k=t=d=2$) we determine the optimal upper bound:

\begin{theorem}\label{thm:rectangles}
	The pairs of every finite point set $S$ in the plane can be $2$-colored such that every axis-parallel rectangle that contains at least $3$ points contains pairs of points colored with both colors.
\end{theorem}

\begin{proof}
	As in the proof of Theorem~\ref{thm:box}, for every pair of points $\p$ and $\q$, among the two vectors $\p \rightarrow \q$ and $\q \rightarrow \p$ we pick the one whose first sign is a $+$,
	and assign its type to the edge $\{\p,\q\}$. Thus, in the plane there are two types of edges: those with the sign sequence $(+,+)$ (i.e., the points are in NE/SW position) and those with the sign sequence $(+,-)$ (i.e., the points are in SE/NW position).
	We color the pairs of points as follows: color a pair $\{\p,\q\}$ red (resp., blue) if (1)~$\p$ and $\q$ are in NE/SW (resp., SE/NW) position and $|box(\p,\q) \cap S|=2$; or (2)~$\p$ and $\q$ are in SE/NW (resp., NE/SW) position and $|box(\p,\q) \cap S|>2$.

	It is enough to consider an axis-parallel rectangle $R$ such that $|R \cap S|=3$.
	Let $\x,\y,\z$ be the points from $S$ in $R$, ordered by their $x$-coordinates.
	If $\y \in box(\x,\z)$, then the edges $\{\x,\z\}$ and $\{\x,\y\}$ are of different colors.
	Otherwise, if $\y \notin box(\x,\z)$, then the edges $\{\x,\y\}$ and $\{\y,\z\}$ are of different colors. This concludes the proof of the theorem.\qedwhite
	\begin{comment}
	We may assume by symmetry and without loss of generality that $z$ is
	Consider an axis-parallel rectangle $R$ that contains at least $3$ points from $S$. First observe that for every pair of points $p$ and $q$ and every other point $r \in box(p,q)$, $r$ and $q$ are at the same direction from $p$. Thus, there must be a point $r \in box(p,q)$ with $|box(p,r)|=2$.
	It follows that if there are pairs in $R$ in both directions, then there are pairs in $R$ in both directions and such that their bounding boxes do not contain other points from $S$. This implies that $R$ contains both red and blue edges.

	Otherwise, suppose that all the pairs in $R$ are in the same relative position, without loss of generality, in NE/SW position. As before, there must be an edge $\{p,q\}$ such that $|box(p,q)|=2$, colored red. Finally,
	taking any three such points their $x$- and $y$-coordinates are in the same order, taking the two non-middle points we get an edge whose bounding box contains the third point, that is $|box(p,q)|\ge 3$ (and they are in NE/SW direction), colored blue, concluding the proof.
	\end{comment}
\end{proof}

Clearly, the value $3$ in Theorem~\ref{thm:rectangles} is optimal, since if a rectangle contains only $2$ points, then it contains only one pair of points, so it is impossible that it contains pairs of both colors.

\section{A common generalization}\label{sec:unify}

One can define a very general notion that contains all the problems considered (including the ones mentioned in the Discussion), namely, \emph{coloring the hyperedges of a hypergraph with respect to another hypergraph and a given relation}.
That is, given a vertex set $V$, two hypergraphs $\HH_1$ and $\HH_2$ on this vertex set, and a relation $R$ (e.g., intersection, containment, reverse containment),
we define the hypergraph $\HH(\HH_1,\HH_2,R)$ as follows. Its vertex set is the hyperedge set of $\HH_1$ and for every hyperedge $H_2$ in $\HH_2$ it has a hyperedge which contains exactly those hyperedges of $\HH_1$ which are in relation $R$ with $H_2$.
Now a (proper) coloring of the hyperedges of $\HH_1$ with respect to $\HH_2$ and $R$ means to color the vertices of $\HH(\HH_1,\HH_2,R)$ (that is, the hyperedges of $\HH_1$) such that every (large enough) hyperedge of $\HH(\HH_1,\HH_2,R)$ (defined by some $H_2\in \HH_2$) is not monochromatic.

\smallskip
We conclude by saying how all the previous problems are special cases of this very general definition.
For geometric problems the vertex set is always a finite point set $S$ and we are given a family of regions $\F$. We say that a hyperedge is defined by some region if it is the intersection of the region with $S$.

For the point coloring problem $\HH_1$ consists of the one-element hyperedges while $\HH_2$ consists of the hyperedges defined by the regions, while $R$ is the containment relation. For the dual problem of coloring regions, $\HH_2$ consists of the one-element hyperedges while $\HH_1$ consists of the hyperedges defined by the regions, while $R$ is the reverse containment relation. For the intersection hypergraph coloring problem $\HH_1=\HH_2$ consists of the hyperedges defined by the regions and $R$ is the intersection relation.

Considering the problem of coloring all $t$-tuples with respect to some regions, $\HH_1$ consists of all $t$-tuples, $\HH_2$ consists of the hyperedges defined by the regions (and $R$ is the containment relation). For $t$-tuples that are themselves hyperedges $\HH_2$ consists of the hyperedges defined by the regions and $\HH_1$ consists of the hyperedges of $\HH_2$ of size $t$ (and $R$ is the containment relation).
Note that the respective hypergraph coloring problems are also special cases, where instead of hyperedges defined by some region we have hyperedges of some given hypergraph $\HH$.

\section{Discussion}

We have introduced the notion of coloring $t$-tuples of vertices of a (geometric) hypergraph such that every hyperedge with enough vertices contains $t$-tuples of different colors (or all colors). This generalizes the well-studied problem of coloring the vertices.
An interesting variant that we focused on is coloring of Delaunay-edges. Perhaps the most interesting problem that we leave open is whether there is a constant $k$ such that it is possible to $k$-color the edges of the Delaunay-graph of a finite point set in the plane with respect to axis-parallel rectangles such that every rectangle that contains $m=m(k)$ points from the point set contains points of different colors.

For coloring with respect to pseudo-disk we have shown that four colors suffice. It would be interesting to determine whether three or two colors are enough.
It would also be interesting to establish more connections between vertex-coloring and edge-coloring, and, in general, to show that a coloring for $t$-tuple implies a coloring for $t'$-tuples, for $t'>t$, as we have shown for coloring of all $t$-tuples.


TITLE: Numerically Solving a Poisson Equation with Neumann Boundary Conditions
QUESTION [4 upvotes]: The Problem
Suppose I have an equation of the form $\nabla^2 \phi(x) = f(x)$ on the interval $A \le x \le B$, where $f(x)$ is known and $\phi(x)$ is unknown. I have Neumann-type boundary conditions: $\frac{\partial \phi}{\partial x}\big|_{x=A} = g_A$ and $\frac{\partial \phi}{\partial x}\big|_{x=B} = g_B$, where $g_A$ and $g_B$ are known.
The compatibility constraint (derived via the divergence theorem) requires that $\int_A^B f(x) dx = g_B-g_A$. Let's assume for this problem that this is satisfied exactly such that a solution is possible.
Ultimately, I don't care about solving for $\phi$, but rather $\vec{E} = -\vec{\nabla} \phi$, but I want to use $\phi$ as the electrostatic potential because it enforces $\vec{\nabla} \times \vec{E} = 0$.
We know and expect that there is not a unique solution, but a family of solutions exist where $\phi(x) = \Phi(x) + C$, where C is any number. In other words, $\phi(x)$ is unique up to an additive constant. I don't care what this constant $C$ is, but it would be nice to be able to constrain it, and I think it is required for a numerical solution to be possible.
Finite Difference Approach
I could set up a 2nd-order finite difference approach over $N_x$ points as follows, where $f_i \equiv f(x_i)$ and $\phi_i \equiv \phi(x_i)$:
$x_i = a + \left(\frac{b-a}{N_x-1}\right) (i-1) = a + \delta x (i-1) \qquad \text{for $i=1, 2, ...,N_x$}$,
where $\delta x \equiv \frac{b-a}{N_x-1}$.
The governing equations become $\frac{\phi_{i+1} - 2\phi_{i} + \phi_{i-1}}{\delta x^2} = f_i$.
The two boundary conditions become $\frac{\phi_2 - \phi_{0}}{\delta x} = g_A$ and $\frac{\phi_{N_x+1} - \phi_{N_x-1}}{\delta x} = g_B$.
This brings us to my issue. The PDE does not have a unique solution!
I can use ghost points ($x_0$ and $x_{N_x+1}$) and combine each boundary condition with the governing equation at each boundary. Doing so gives me $N_x$ equations and satisfies the boundary conditions. I can create a $N_x \times N_x$ matrix to solve this problem, but it is singular because $\phi(x)$ is not unique. I can add a uniqueness constraint to the matrix ($\phi_C = C$) to make a $(N_x+1) \times N_x$ matrix, but I'm afraid this will lead to a minimum-length solution.
Concrete Example
For $N_x=7$, I have the following system of equations:
$
\begin{align}
\phi_{2} - 2\phi_{1} + \phi_{0} \;=&\; \delta x^2 \; f_{1} \quad \text{and} \quad \phi_{2} - \phi_{0} \;=\; \delta x\; g_A \rightarrow 2 \phi_{2} - 2 \phi_{1} = \delta x g_A + \delta x^2 \; f_{1} \\
\phi_{3} - 2\phi_{2} + \phi_{1} \;=&\; \delta x^2 \; f_{2} \\
\phi_{4} - 2\phi_{3} + \phi_{2} \;=&\; \delta x^2 \; f_{3} \\
\phi_{5} - 2\phi_{4} + \phi_{3} \;=&\; \delta x^2 \; f_{4} \\
\phi_{6} - 2\phi_{5} + \phi_{4} \;=&\; \delta x^2 \; f_{5} \\
\phi_{7} - 2\phi_{6} + \phi_{5} \;=&\; \delta x^2 \; f_{6} \\
\phi_{8} - 2\phi_{7} + \phi_{6} \;=&\; \delta x^2 \; f_{7} = \quad \text{and} \quad \phi_{8} - \phi_{6} \;=\; \delta x\; g_B \rightarrow 2 \phi_{6} - 2 \phi_{7} = -\delta x \; g_B + \delta x^2 \; f_{7} \\
\end{align}
$
$
\begin{bmatrix}
    -2 & 2 & 0 & 0 & 0 & 0 & 0 \\
    1 & -2 & 1 & 0 & 0 & 0 & 0 \\
    0 & 1 & -2 & 1 & 0 & 0 & 0 \\
    0 & 0 & 1 & -2 & 1 & 0 & 0 \\
    0 & 0 & 0 & 1 & -2 & 1 & 0 \\
    0 & 0 & 0 & 0 & 1 & -2 & 1 \\
    0 & 0 & 0 & 0 & 0 & 2 & -2
\end{bmatrix}
\begin{bmatrix}
    \phi_{1} \\
    \phi_{2} \\
    \phi_{3} \\
    \phi_{4} \\
    \phi_{5} \\
    \phi_{6} \\
    \phi_{7}
\end{bmatrix}
=
\begin{bmatrix}
    \delta x^2 \; f_{1} + \delta x \; g_A \\
    \delta x^2 \; f_{2} \\
    \delta x^2 \; f_{3} \\
    \delta x^2 \; f_{4} \\
    \delta x^2 \; f_{5} \\
    \delta x^2 \; f_{6} \\
    \delta x^2 \; f_{7} - \delta x; g_B
\end{bmatrix}
$
The problem with the above matrix equation is that it is singular. This is to be expected because $\phi$ is non-unique and is only defined up to a scalar constant.
We could specify this constant by setting the value of $\phi$ at any given point. In the above example, we could try for a unique solution by adding the constraint $\phi_4 = C$ (where $C$ is a given finite number):
$
\begin{bmatrix}
    -2 & 2 & 0 & 0 & 0 & 0 & 0 \\
    1 & -2 & 1 & 0 & 0 & 0 & 0 \\
    0 & 1 & -2 & 1 & 0 & 0 & 0 \\
    0 & 0 & 1 & -2 & 1 & 0 & 0 \\
    0 & 0 & 0 & 1 & -2 & 1 & 0 \\
    0 & 0 & 0 & 0 & 1 & -2 & 1 \\
    0 & 0 & 0 & 0 & 0 & 2 & -2 \\
    0 & 0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
    \phi_{1} \\
    \phi_{2} \\
    \phi_{3} \\
    \phi_{4} \\
    \phi_{5} \\
    \phi_{6} \\
    \phi_{7}
\end{bmatrix}
=
\begin{bmatrix}
    \delta x^2 \; f_{1} + \delta x \; g_A \\
    \delta x^2 \; f_{2} \\
    \delta x^2 \; f_{3} \\
    \delta x^2 \; f_{4} \\
    \delta x^2 \; f_{5} \\
    \delta x^2 \; f_{6} \\
    \delta x^2 \; f_{7} - \delta x \; g_B \\
    C
\end{bmatrix}
$
The problem with this approach is that it is no longer a square matrix and looks like it's an over-determined system. I'm concerned that matrix-solving algorithms for non-square matrices would treat this as a least-squares problem. This isn't an over-determined system, however: the rank of the matrix equals the number of unknowns, even though the matrix isn't square.
Alternatively, I could remove one of the equations to make the matrix square.
If I were to take out the uniqueness constraint ($\phi_4 = C$), then the matrix is square but singular. (MATLAB can solve this anyway, and it gets an answer with the least error, but I don't know how it does it, and I'm concerned about it not specifying $C$.)
If I were to remove one of the governing equations ($\frac{\phi_{i+1} - 2\phi_{i} + \phi_{i-1}}{\delta x^2} = f_i$), then the system does not account for the curvature at $x=x_i$, and the solution is inaccurate.
My Question
Is there a good algorithm for solving this type of problem, where I need more constraints than the number of unknowns, but the problem is not overdetermined?
In particular:

Is there an algorithm that can solve the underdetermined case where $\phi_i = C$ is not included? (Is it absolutely necessary to include this constraint, or an equivalent one?)
Is there a system of equation that is solved reliably, with minimal numerical error? I've tried rearranging the above equations and using different matrix solvers, but most of the matrices I've used give condition numbers that scale with $N_x^2$, which is concerning for the problem sizes I'm using for my research.)

REPLY [6 votes]: A standard way how to make the solution unique is to look for the zero-mean solution
$$
\int_A^B\phi(x)\,\mathrm{dx}=0.
$$
Let $Mu=f$ be the linear system corresponding to your finite difference approximation (with uniform discretization, constant vectors form nullspace of $M$) and $e=[1,\ldots,1]^T$. Since $M$ is symmetric and semi-definite, any solution of $Mu=f$ also minimizes $\frac{1}{2}u^TMu-u^Tf$. Imposing the zero-mean condition gives the constrained minimization problem
$$
\min_u \frac{1}{2}u^TMu-u^Tf\quad\text{such that}\quad e^Tu=0
$$
which by introducing a Lagrange multiplier $c$ leads to a system
$$
\pmatrix{M&e\\e^T&0}\pmatrix{u\\c}=\pmatrix{f\\0}.
$$


TITLE: Extending a local distance preserving map $\gamma:[0,L[\rightarrow X$ to $[0,L]$
QUESTION [1 upvotes]: Let $L$ be a positive real, $(X,d)$ a complete metric space, and $\gamma:[0,L[\rightarrow X$ be a local distance preserving map(where $[0,L[$ is equipped with the Euclidean metric). Must $\gamma$ be extendable to a local distance preserving map from $[0,L]$ to $X$ ? Can at least one extend gamma continuously to $[0,L]$ ?
Thank you,

REPLY [0 votes]: Here is a sketch of the construction of a counter-exmaple. Consider the map $\gamma : [0, 1) \to \Bbb{C}$ defined by
$$ \gamma(t) = \frac{\exp(2\pi i \cdot 2^{k+1} t) - 1}{2\pi \cdot 2^{k+1}} \qquad \text{for } t \in [1 - 2^{-k}, 1 - 2^{-k-1}). $$
Its image $X = \gamma([0, 1))$ looks like the following figure:
$\hspace{12em}$
Equip $X$ with the intrinsic metric $d$. Then it is possible to check that $\gamma : I \to X$ is a local distance-preserving map. Intuitively, this is because $\gamma$ is distance-preserving on each circular arc.
Now, since $\gamma(1 - 2^{-k}) = 0$ for each $k$, the path $\gamma$ extends to a continuous function $\tilde{\gamma} : [0, 1] \to X$ with $\tilde{\gamma}(1) = 0$. However, this also shows that $\tilde{\gamma}$ cannot be distance-preserving near $1$.


TITLE: Is $1-\cos nt \leq n(1-\cos^nt)$?
QUESTION [6 upvotes]: In an exercise about characteristic functions of probability measures, once is asked to show that
$$
\begin{align}
1-\operatorname{Re}(\widehat{\mu}(nt))\leq n\Big(1-\big(\operatorname{Re}(\widehat{\mu}(t))\big)^n\Big)\tag{0}\label{zero}
\end{align}
$$
where $\widehat{\mu}(t)=\int e^{itx}\,\mu(dx)$, and $\mu$ is a Probability measure on $(\mathbb{R},\mathscr{B}(\mathbb{R}))$.
Since $\Big(\int \cos(tx)\,\mu(dx)\Big)^n\leq \int\cos^n(tx)\,\mu(x)$,
inequality $\eqref{zero}$  will follow immediately if the following inequality holds
$$
\begin{align}
1-\cos (n\alpha) \leq n\big(1-\cos^n(\alpha)\big),\quad\forall \alpha\in[0,2\pi]\tag{1}\label{one}
\end{align}
$$

I tried induction (for n=1,2 we have equality, for n=3, $\eqref{one}$ holds) however, there does not seem the be a clear inductive proof.

I tried to use mean value theorem, but again, the proof eludes me.

I have check numerically (just plotting the functions on the left and right hands sides) and it seems that the statement holds.
Does anybody have a hint or know of a proof (or counter example) for $\eqref{one}$?.

REPLY [3 votes]: Separate Case: $\boldsymbol{n=0}$
Note that
$$
1-\cos(nt)\le n\!\left(1-\cos^n(t)\right)\tag1
$$
is trivially true for $n=0$.

Prove a Stronger Statement for $\boldsymbol{n\ge1}$
To prove $(1)$ for $n\ge1$, we will prove the stronger statement
$$
\left|\,n\cos^n(t)-\cos(nt)\,\right|\le n-1\tag2
$$
We have the two identities
$$
(n+1)\cos^{n+1}(t)=n\cos^n(t)\cos(t)+\cos^n(t)\cos(t)\tag3
$$
and
$$
\cos((n+1)t)=\cos(nt)\cos(t)-\sin(nt)\sin(t)\tag4
$$

Induction on $\boldsymbol{n}$
Trivially, $(2)$ is true for $n=1$. Assume $(2)$ is true for some particular $n$, then
$$
\begin{align}
&\left|\,(n+1)\cos^{n+1}(t)-\cos((n+1)t)\,\right|\tag5\\[9pt]
&=\left|\,\color{#C00}{\left(n\cos^n(t)-\cos(nt)\right)}\cos(t)+\color{#090}{\cos^n(t)}\cos(t)+\sin(nt)\sin(t)\,\right|\tag6\\[3pt]
&\le\color{#C00}{(n-1)}|\!\cos(t)|+\color{#090}{\frac{n-1+|\!\cos(nt)|}n}|\!\cos(t)|+|\!\sin(nt)|\,|\!\sin(t)|\tag7\\
&=\frac{n^2-1+|\!\cos(nt)|}n|\!\cos(t)|+|\!\sin(nt)|\,|\!\sin(t)|\tag8\\[6pt]
&\le n\tag9
\end{align}
$$
Explanation:
$(6)$: subtract $(4)$ from $(3)$
$(7)$: triangle inequality and the assumption
$(8)$: simplify
$(9)$: Cauchy-Schwarz and the inequality
$\phantom{\text{(9):}}$ $\begin{align} \scriptsize\left(\frac{n^2-1+|\!\cos(nt)|}n\right)^2+\sin^2(nt) &\scriptsize\,=n^2-\frac{n^2-1}{n^2}(1-|\!\cos(nt)|)^2\\ &\scriptsize\,\le n^2 \end{align}$
Inequality $(9)$ shows that $(2)$ is true for $n+1$, which completes the induction.


TITLE: Decompose $x$ into $F$ and $F^{\perp }$ in $l^2(\mathbb{N}, \mathbb{C})$
QUESTION [1 upvotes]: Let $l^2(\mathbb{N}, \mathbb{C})$. Consider
$F= \{x=(x_k)_{k\in \mathbb{N}}\in l^2(\mathbb{N}, \mathbb{C})|x_{2k}=x_{2k+1}\} $
Decompose $x$ into $F$ and $F^{\perp }$.
I proved $F$ is a closed subspace of $l^2(\mathbb{N}, \mathbb{C})$,
$F^{\perp }= \{y \in l^2(\mathbb{N}, \mathbb{C}) | \sum_{k\in \mathbb{N}}x_{2k}(y_{2k}+y_{2k+1})= 0, x=(x_k)_k \in F \}$
and I think I need to use the projection theorem in Hilbert space but I couldn't decompose $x$. Could you help me, please?

REPLY [2 votes]: Write any $(x_n)$ as the sum of $(x_1,\frac {x_2+x_3} 2, \frac {x_2+x_3} 2,\frac {x_4+x_5} 2,\frac {x_4+x_5} 2,\cdots )$ and $(0,\frac {x_2-x_3} 2, \frac {x_3-x_2} 2,\frac {x_4-x_5} 2,\frac {x_5-x_4} 2,\cdots )$. Verify that the first sequence is in $F$ and that the second one is orthogonal to $F$. This decomposition is the one we want.


TITLE: Question about Eulerian Circuits and Graph Connectedness
QUESTION [0 upvotes]: I read a theorem in a Graph Theory Introductory text. It says "If a pseudograph G has an Eulerian Circuit, then it is connected and every vertex of the graph G has even degree."
Is it necessary that if a graph G has an Eulerian Circuit, then it is connected? What if there are isolated vertices in the graph G? I would greatly appreciate it if you can please clarify this for me.

REPLY [0 votes]: To be an Eulerian Circuit, all vertices must have an even degree and the graph must act as a cycle. The graph must be connected as isolated vertices would have degrees of 0 so therefore it would not be an eulerian graph.


TITLE: How to determine the outward normal vector of a face of a hexahedron if the orientation (CW or CCW) of vertices of the face is unknown
QUESTION [3 upvotes]: Consider a single quadrilaterally-faced hexahedron. If given the co-ordinates of the vertices, $\mathbf{v}_i$, of a face in counter-clockwise orientation, I can compute the corresponding unit outward normal vector using a cross-product:
$\mathbf{n}=\frac{(\mathbf{v}_2-\mathbf{v}_1)\times(\mathbf{v}_4-\mathbf{v}_1)}{\parallel(\mathbf{v}_2-\mathbf{v}_1)\times(\mathbf{v}_4-\mathbf{v}_1)\parallel}$
However, consider now an arbitrarily shaped volume which is discretised into a large number of quadrilaterally-faced hexahedra. Consider in particular a face shared by two adjacent hexahedra. If now given the co-ordinates of the vertices of the face in a certain orientation, the orientation will be clockwise for one hexahedron and counter-clockwise for the other.
If I do not know the orientation beforehand, how can I ensure that the unit normal is pointing outwards (assuming you know the co-ordinates of all vertices of all faces of all hexehedra)?

REPLY [0 votes]: Your hexahedron is convex, so you can do the dot product of the normal vector that you found, and a vector from one of the vertices to some point inside the hexahedron. If the dot product is negative, then your normal vector points out.
If you already know a point inside the hexahedron, then you're in luck. Otherwise you would have to find this, which would pose challenges of its own.


TITLE: Bound variance of sum of indicators
QUESTION [1 upvotes]: Let $G=(V,E)$ be a graph such that $|V| = n$, $|E| = \Theta(n^{3/2})$ and the maximal degree is $O(n^{1/2})$. Define $V'$ to be a set of vertices, chosen by adding each vertex to $V'$ with probability $\frac{1}{\sqrt{n}}$. The goal is to prove that with probability at least $(1- \alpha)$ (for all positive $\alpha$), the graph induced by $V'$ has at least $(1-\alpha)\sqrt{n}$ edges for all $n$ large enough.
I tried to do the following:
Define for each edge an indicator $I_e$ which equals to 1 iff the edges $e$ is in $G'$, and $I = \sum_e I_e$. Clearly, $P(I_e = 1) = \frac{1}{n}$ and $E(I) = \Theta(\sqrt{n})$. Now, we can use Chebyshev inequality: $P(|I - \sqrt{n} | > \alpha \sqrt(n))< \frac{Var(I)}{\alpha^2 n}$. So, in order to complete the proof, I need to bound the variance. The thing is that "simple" bound doesn't work (the fraction doesn't go to 0 as $n$ grows). Any ideas?

REPLY [0 votes]: You have to use the condition that maximal degree is $O(n^{1/2})$. This means the total number of paths of length $2$ is $O(n^{2})$. This shows that $\mathrm{Var}(I) = O(\sqrt{n}).$
This is because
$$
\mathrm{Var}(I) = \sum_{\{u,v\} \in E,\{s,t\} \in E} \mathbb{E}(I_{u,v} I_{s,t})-\mathbb{E}(I_{u,v})\mathbb{E}(I_{s,t}).
$$
There are three cases --- (a) the two edges $\{u,v\}$ and $\{s,t\}$ are either disjoint, (b) or share one node, i.e., they form a path of length $2$, (c) or are the same. The disjoint pairs contribute $0$ to the sum. The $2$-path pairs contribute $O(\sqrt{n})$. And the identical pairs contribute $O(\mathbb{E}(I))$. So we are done!


TITLE: Momentum of a moving object in FRW metric according to an observer comoving with cosmic expansion
QUESTION [1 upvotes]: I would like to show that in an FRW metric the momentum of a freely falling object decays as the inverse of the scale factor. I know there are many proofs and arguments for this but I am trying to get this starting from geodesics and having some trouble.
General logic
My general approach is the following.
The object is moving along some path. I want to find the momentum of the object that would be measured by a coincident, locally inertial observer, i.e. a detector that is freely falling and locally cannot tell that spacetime is curved.
In the locally inertial frame where the observer is momentarily at rest the 4-velocity of the observer has components $u^\mu\equiv d\xi^\mu/d\sigma= (1,0,0,0)$, where $\xi^\mu$ are the coordinates of this local inertial (cartesian) frame and $\sigma$ is the observer's proper time (in this frame $d\sigma=d\xi^0$). In this same frame the object has 4-momentum $p^\mu \equiv md\xi^\mu/d\tau$, where $\tau$ is the object's proper time, and $m$ the rest mass.
Since special relativity holds in this frame the components of $p^\mu$ have the values $p^\mu=(E_\mathrm{obs},\mathbf{p}_\mathrm{obs})$, the energy and momentum that would be measured by the observer at rest in this frame. They obey $E_\mathrm{obs}^2-\mathbf{p}_\mathrm{obs}^2=m^2$. We can retrieve the energy $E$ by contracting $u^\mu$ with $p^\mu$:
$$
E_\mathrm{obs}=g_{\mu\nu}u^\mu p^\nu,
$$
where $g_{\mu\nu}=\text{diag}(1,-1,-1,-1)$ are the components of the metric in this locally inertial coordinate system.
The magnitude of the 3-momentum in this system is just
$$
|\mathbf{p}_\mathrm{obs}| = \sqrt{(g_{\mu\nu}u^\mu p^\nu)^2 - m^2}.
$$
The right hand side is invariant under general coordinate transformations. Therefore, I think we can calculate the RHS in any coordinate system we want and the value will be the magnitude of the 3-momentum as measured by the observer  corresponding to the path $u^\mu$ in a locally inertial frame.
Is this ok so far?
FRW metric
$x^\mu = (t, \mathbf{x})$ are the coordinates of the FRW metric, defined by:
$$
d\tau^2 = dt^2 - a(t)^2 \left(d\mathbf{x}^2 + K \frac{(\mathbf{x}\cdot d\mathbf{x})^2}{1-K\mathbf{x}^2} \right),
$$ where $K =0$, $+1$, or $−1$.
The geodesic paths can be found using the Euler-Lagrange equations (see this post). The resulting equations are
\begin{align}
0 &= \frac{d^2 t}{d\tau^2} + a\dot{a} \left(\mathbf{x}'^2 +\frac{K(\mathbf{x}\cdot \mathbf{x}')^2}{1-K \mathbf{x}^2}\right)\\
\mathbf{0} &= \frac{d}{d\tau} \left[ a^2\left(\mathbf{x}' + \frac{K(\mathbf{x} \cdot \mathbf{x}')\mathbf{x}}{1-K\mathbf{x}^2}\right) \right] - \frac{K (\mathbf{x} \cdot \mathbf{x}')}{1-K\mathbf{x}^2} a^2 \left(\mathbf{x}' + \frac{K(\mathbf{x} \cdot \mathbf{x}')\mathbf{x}}{1-K\mathbf{x}^2}\right),
\end{align}
where a prime means $d/d\tau$ and $\dot{a}=da/dt$ is a function of $t$.
The simple solutions to these equations are $t=\tau, \mathbf{x}=\text{const}$. These solutions correspond to the "comoving" observers that move along with the cosmic expansion. The world lines of these observers all have 4-velocity $u^\mu=(1,0,0,0)$ in this coordinate system. When the object is at some location $\mathbf{x}$ at time $t$ I want to get the momentum as measured in a locally inertial frame in which the comoving observer that sits at position $\mathbf{x}$ is momentarily at rest.
To get the equations of motion for an arbitrary freely falling object you have to integrate the above equations. I was able to do this only for the second equation but I think that's enough.
Define $\mathbf{f}$ by
$$
\mathbf{f} \equiv a^2\left(\mathbf{x}' + \frac{K(\mathbf{x} \cdot \mathbf{x}')\mathbf{x}}{1-K\mathbf{x}^2}\right),
$$
to write the second equation as
$$
\mathbf{0} = \frac{d \mathbf{f}}{d\tau} - \frac{K (\mathbf{x} \cdot \mathbf{x}')}{1-K\mathbf{x}^2} \mathbf{f}.
$$
Multiply through by the integrating factor $\sqrt{1-K\mathbf{x}^2}$ to get
\begin{align}
\mathbf{0} &= \sqrt{1-K\mathbf{x}^2}\frac{d \mathbf{f}}{d\tau} - \frac{K (\mathbf{x} \cdot \mathbf{x}')}{\sqrt{1-K\mathbf{x}^2}} \mathbf{f} \\
 &= \sqrt{1-K\mathbf{x}^2}\frac{d \mathbf{f}}{d\tau} + \mathbf{f} \frac{d}{d\tau}\sqrt{1-K\mathbf{x}^2} \\
&= \frac{d}{d\tau}\left(\mathbf{f} \sqrt{1-K\mathbf{x}^2}\right).
\end{align}
The solution is
\begin{align}
\frac{\mathbf{c}}{\sqrt{1-K\mathbf{x}^2}} = a^2\left(\mathbf{x}' + \frac{K(\mathbf{x} \cdot \mathbf{x}')\mathbf{x}}{1-K\mathbf{x}^2}\right),
\end{align}
for some constant 3-vector $\mathbf{c}$.
The term $(\mathbf{x}\cdot\mathbf{x}')$ can be isolated by dotting this equation with $\mathbf{x}$:
\begin{align}
\frac{\mathbf{c}\cdot\mathbf{x}}{\sqrt{1-K\mathbf{x}^2}} &= a^2\left((\mathbf{x} \cdot \mathbf{x}') + \frac{K(\mathbf{x} \cdot \mathbf{x}')\mathbf{x}^2}{1-K\mathbf{x}^2}\right)\\
&= a^2 (\mathbf{x} \cdot \mathbf{x}') \left(1+ \frac{K\mathbf{x}^2}{1-K\mathbf{x}^2}\right)\\
&= a^2 \frac{\mathbf{x} \cdot \mathbf{x}'}{1-K\mathbf{x}^2}.
\end{align}
Now $\mathbf{x}'$ can be written in terms of $\mathbf{x}$:
\begin{align}
a^2 \mathbf{x}' &= \frac{\mathbf{c}}{\sqrt{1-K\mathbf{x}^2}} - a^2 \frac{K(\mathbf{x} \cdot \mathbf{x}')\mathbf{x}}{1-K\mathbf{x}^2}\\
&= \frac{\mathbf{c}}{\sqrt{1-K\mathbf{x}^2}} -
\frac{K(\mathbf{c}\cdot\mathbf{x})\mathbf{x}}{\sqrt{1-K\mathbf{x}^2}}\\
&= \frac{\mathbf{c} - K(\mathbf{c}\cdot\mathbf{x})\mathbf{x}}{\sqrt{1-K\mathbf{x}^2}}.
\end{align}
Finally the spatial part of the object's 4-momentum is
\begin{align}
p^i = m\frac{d\mathbf{x}}{d\tau} = m \frac{\mathbf{c} - K(\mathbf{c}\cdot\mathbf{x})\mathbf{x}}{a^2\sqrt{1-K\mathbf{x}^2}}.
\end{align}
Now to try to use the $|\mathbf{p}_\mathrm{obs}| = \sqrt{(g_{\mu\nu}u^\mu p^\nu)^2 - m^2}$ formula I had earlier.
Since $u^\mu=(1,0,0,0)$, $g_{00}=1$, and $g_{0i}=0$ at $\mathbf{x}$, $|\mathbf{p}_\mathrm{obs}| = \sqrt{(p^0)^2 - m^2}$.
Writing out $g_{\mu\nu}p^\mu p^\nu = m^2$ gives
\begin{align}
m^2 &= (p^0)^2 - m^2 a^2\left(\mathbf{x}'^2 + K \frac{(\mathbf{x}\cdot \mathbf{x}')^2}{1-K\mathbf{x}^2} \right) \\
&= (p^0)^2 - m^2 (\mathbf{f} \cdot \mathbf{x}') \\
&= (p^0)^2 - m^2 \frac{\mathbf{c}}{\sqrt{1-K\mathbf{x}^2}} \cdot \frac{\mathbf{c} - K(\mathbf{c}\cdot\mathbf{x})\mathbf{x}}{a^2\sqrt{1-K\mathbf{x}^2}} \\
& = (p^0)^2 - m^2 \frac{\mathbf{c}^2 - K(\mathbf{c}\cdot\mathbf{x})^2}{a^2 (1-K\mathbf{x}^2)},
\end{align}
and I get
$$
|\mathbf{p}_\mathrm{obs}| = \sqrt{(p^0)^2 - m^2} = \frac{m}{a}\sqrt{\frac{\mathbf{c}^2 - K(\mathbf{c}\cdot\mathbf{x})^2}{1-K\mathbf{x}^2}}.
$$
But I don't think this is proportional to $1/a$ in general.
If the object passes through the origin then everything works as I expect. In this case $\mathbf{c}$ is parallel to $\mathbf{x}'$ when $\mathbf{x}=0$ and the equation of motion keeps it moving along a straight line parallel to this initial $\mathbf{x}'$ so $\mathbf{x}$ remains parallel to $\mathbf{c}$ and $(\mathbf{c} \cdot \mathbf{x})^2 = \mathbf{c}^2\mathbf{x}^2$ and the term in the square root is just a constant $|\mathbf{c}|$.
But for an object flying somewhere else, not passing through the origin I think the angle between $\mathbf{c}$ and $\mathbf{x}$ will change as it goes (and in particular it will not always be $0$) and so the momentum observed by a locally inertial observer will not simply scale as $1/a$.
I guess maybe the angle between $\mathbf{c}$ and $\mathbf{x}$ changes as $\mathbf{x}^2$ changes in just such a way as to keep the term in the square root constant but I don't see how to show that.
Or do I have the entire logic of the exercise wrong?

REPLY [1 votes]: It turns out that last factor in the square root is actually a constant -- so everything works nicely and momentum decays as $1/a$ for any object moving on a geodesic as it's supposed to.
I took the derivative of the term in the square root:
$$
\frac{\mathbf{c}^2-K(\mathbf{c}\cdot \mathbf{x})^2}{1-K\mathbf{x}^2} \equiv A.
$$
This introduces the terms $\mathbf{c}\cdot \mathbf{x}'$ and $\mathbf{x}\cdot \mathbf{x}'$, which we can get rid of using some of the formulas in the original post:
\begin{align}
\mathbf{c}\cdot \mathbf{x}' &= \frac{\mathbf{c}^2-K(\mathbf{c}\cdot \mathbf{x})^2}{a^2\sqrt{1-K\mathbf{x}^2}} = \frac{\sqrt{1-K\mathbf{x}^2}}{a^2}A \\
\mathbf{x}\cdot \mathbf{x}' &= \frac{1}{a^2}\sqrt{1-K\mathbf{x}^2}(\mathbf{c}\cdot \mathbf{x})
\end{align}
\begin{align}
\frac{dA}{d\tau} &=\frac{-2K (\mathbf{c}\cdot \mathbf{x})(\mathbf{c}\cdot \mathbf{x}')}{1-K\mathbf{x}^2} + \frac{\left(\mathbf{c}^2-K(\mathbf{c}\cdot \mathbf{x})^2\right)2K(\mathbf{x}\cdot \mathbf{x}')}{(1-K\mathbf{x}^2)^2}\\
&= \frac{-2K (\mathbf{c}\cdot \mathbf{x})}{1-K\mathbf{x}^2}\frac{\sqrt{1-K\mathbf{x}^2}}{a^2}A + \frac{A}{1-K\mathbf{x}^2} \frac{2K}{a^2}\sqrt{1-K\mathbf{x}^2}(\mathbf{c}\cdot \mathbf{x})\\
&= 0.
\end{align}
So
$$
|\mathbf{p}_\mathrm{obs}| = \frac{m}{a}\sqrt{A}= \frac{\text{const}}{a}.
$$