3
$\begingroup$

Consider the following problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which are contained in two or more intervals coloured with the same colour, is minimal for given $k$. By colouring a set $S$ in $k$ colours I mean a map from $S$ to $\{1, 2,\ldots, k\}$.

I wonder, if there are any papers on this problem or related problems.

$\endgroup$
2
$\begingroup$

Let $I_1,\ldots,I_n$ be the intervals in $S$. For simplicity, we may assume that the intervals are open and that all $2n$ endpoints are distinct. The latter property can be ensured by changing the intervals slightly, which changes the value of the objective function by an arbitrarily small amount. Furthermore, we may assume that $k\geq 2$.

Let $x_1<x_2<\ldots<x_{2n}$ be the $2n$ endpoints of the intervals $I_1,\ldots,I_n$. For $i\in \{ 1,\ldots,2n-1\}$, let $J_i=(x_i,x_{i+1})$. By construction, all points in $J_i$ are contained in the same number $\omega_i$ of intervals in $S$. The interval $J_i$ is {\it bad} if $\omega_i>k$. Clearly, for every coloring $c:S\to \{ 1,2,\ldots,k\}$, the set of points that are contained in two or more intervals coloured with the same colour, contains every bad interval, that is, the total measure of the bad intervals is an obvious lower bound. Let $B$ be the union of all bad intervals.

We claim the existence of a coloring $c$ such that the set of points that are contained in two or more intervals coloured with the same colour, is exactly $B$, that is, the above lower bound actually gives the optimum value. We prove this claim by induction on the number of bad intervals.

Note that $\max\{ \omega_i:i\in \{ 1,\ldots,2n-1\}\}$ is the clique number $\omega(G)$ of the interval graph $G$ defined by the intervals in $S$. Therefore, if there are no bad intervals and $B$ is empty, then the perfection of interval graphs implies $\chi(G)\leq k$, which implies the existence of a coloring $c$ such that no point is contained in two or more intervals coloured with the same colour.

Now, let $B\not=\emptyset$. Let $J_i$ be the leftmost bad interval. Let $x=x_i$ be the left endpoint of $J_i$. Note that, since $k\geq 2$, we have $i\geq 2$. Clearly, $x$ is the left endpoint of some interval $I_r$ in $S$. Let $R\subseteq S$ be such that $R$ contains $I_r$ as well as every interval in $S$ that contains $x$. Let $y$ be the leftmost right endpoint of any interval in $R$. Note that $B\setminus (x,y)$ is a finite set, that is, a set of $0$ measure. Let $y$ be the right endpoint of the interval $I_s\in R$. If $r\not=s$, then let $S'$ arise from $S$ by replacing the two intervals $I_r$ and $I_s$ by their union $I'=I_r\cup I_s$. If $r=s$, then $R$ contains an interval $I_s$ that is distinct from $I_r$ such that $[x,y]\subset I_s$. Again, let $S'$ arise from $S$ by replacing the two intervals $I_r$ and $I_s$ by their union $I'=I_r\cup I_s$. By construction, the collection $S'$ of intervals leads to fewer bad intervals. Let $B'$ denote the union of the bad intervals associated with $S'$. Clearly, $B$ differs from $B'\cup (x,y)$ by a finite set. By induction, there is a coloring $c'$ of $S'$ with $k$ colors such that the set of points that are contained in two or more intervals in $S'$ coloured with the same colour by $c'$, is exactly $B'$. Let $c$ be the coloring of $S$ such that $c\mid_{S\setminus \{ I_r,I_s\}}=c'\mid_{S'\setminus \{ I'\}}$ and $c(I_r)=c(I_s)=c'(I')$. By construction, the set of points that are contained in two or more intervals in $S$ coloured with the same colour by $c$, is exactly $B$.

$\endgroup$
  • $\begingroup$ Thank you for the answer! I need to add that regarding my initial question about references, I am not aware of any papers about this problem or similar problems. $\endgroup$ – Andrew Ryzhikov Nov 7 '15 at 19:41
2
$\begingroup$

First of all, the problem can have no solution. Consider intervals $I_n=(0,n)$. No matter how you color them with $k$ colors there will be infinite families with same color and non-empty intersection. To make the problem meaningful, you must first specify whether your intervals are open or closed (or else), and second, impose some additional restrictions.

$\endgroup$
  • $\begingroup$ I am interested in this problem for finite set $S$, I have added it explicitly to the post. $\endgroup$ – Andrew Ryzhikov Jan 28 '14 at 15:15
  • $\begingroup$ Still the problem does not make much sense to me: what if all your intervals contain a common point? $\endgroup$ – Alexandre Eremenko Jan 29 '14 at 2:28
  • $\begingroup$ so what? Measure of a point is zero. If $S$ is a finite set, the optimization problem is bounded. $\endgroup$ – Andrew Ryzhikov Jan 29 '14 at 7:19
  • $\begingroup$ Example: for three intervals $[0, 3]$, $[1, 4]$, $[2, 5]$ and $k = 2$ we need to colour first and third interval in first colour and second interval in second colour, so the measure of the set of points, which are contained in two or more intervals coloured with the same colour, is $1$. $\endgroup$ – Andrew Ryzhikov Jan 29 '14 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.