Covering a circle with red and blue arcs

Question

We have a circle and two families of $n$ red arcs and $n$ blue arcs, positioned on the circle so that every two arcs of different colors intersect. Can one show that there is a point in the perimeter which is part of at least $n$ arcs?

(The statement sounds very simple. It makes me think the answer should be very simple too, but I've been struggling with this one for a bit and got nowhere.)

After reading Suresh's answer below, I can't help but think that there must be some colorful Helly theorem on manifolds, of which the question above is a special case. At the moment I don't even have a meaningful formulation of what this theorem could be, has it been treated before?

Answer 1

This is the second half of a proof started by Peter Shor.

I assume that the set of arcs is already in a position as in Peter's answer: the red arcs $(L_1,R_i)$ are cyclically ordered and all blue arcs are of the form $(R_i,L_{i-1})$. For convenience, I also assume that no two of red arcs coincide (and hence their $2n$ endpoints are distinct). This is easy to achieve by perturbation. Let $S$ denote the set of the red endpoints and $r:S\to\mathbb N$ denote the covering multiplicity by red arcs: $r(p)$ is the number of red arcs containing $p$.

Fix the red arcs. Then a configuration is determined by a vector of $n$ multiplicities $T=(t_1,\dots,t_n)$ where $t_i$ is how many copies of a blue arc $(R_i,L_{i-1})$ we have. For such $T$ and each $p\in S$, let $b_T(p)$ be the number of blue arcs (in the configuration defined by $T$) containing $p$. Note that $b_T$ is linear in $T$. By Peter's observation, we have $b_{T_0}(p)=n-r(p)$ for all $p\in S$ where $T_0$ is the standard vector: $T_0=(1,\dots,1)$.

We have $\sum t_i=n$ for every admissible vector $T$. I claim that none of the resulting functions $b_T:S\to\mathbb R_+$ strictly majorizes any other. The result follows from this claim applied to $T=T_0$. To prove the claim, it suffices to find a collection $w:S\to\mathbb R_+$ of nonnegative weights such that, for every (potentially) blue arc, the sum of weights of points covered by this arc equals 1. Indeed, if such weights are found, we have $\sum_{p\in S} w(p) b_T(p)=n$ for any $T$, and the claim follows.

To construct $w$, consider the standard covering map $f:\mathbb R\to S^1$. On the line, we have a discrete set $\tilde S=f^{-1}(S)$ and a collection of segments corresponding to pre-images of the potentially blue arcs (both structures are $2\pi$-periodic). The endpoints of the segments are in $\tilde S$, and the segments are ordered from left to right (none of them is contained in another). Let us first solve the weight problem on the line. Begin with one of the segments and mark is right endpoint. Then take the first segment contained in the open half-line after the marked point, and mark its right end. Repeat for the new marked point, and so on. Then every segment to the right of the first one contains exactly one marked point. Let the marked points have weight 1 and all other points have weight 0. We have solved the weigh problem on a half-line.

Observe that the set of marked points is eventually $2\pi k$-periodic for some integer $k$. This follows from the deterministic nature of the construction: once some $x$ and some $x+2\pi k$ are both marked, the pattern will repeat itself. Hence there is a $2\pi k$-periodic weight function on the whole line. We can make it $2\pi$-periodic by averaging over $2\pi m$-translations, $0\le m<k$. Once it is $2\pi$-periodic, it projects back to the circle.

Answer 2

Here's the start of a proof.

We will say that two arcs overlap twice if their union covers the entire circle. First, note that you can assume that there are no two red arcs that overlap twice.

Proof: Suppose that there were two blue arcs that overlap twice and two red arcs that overlap twice. Then, we could delete all four of these arcs and find a point covered by $n-2$ of the remaining arcs. Two of the deleted arcs also cover this point, and we're done. By symmetry, we can assume that there are no two red arcs that overlap twice.

Now, note that we can assume that no red arc is contained in another. If there were, we could shrink the larger one so that they overlap, but neither is contained in the other.

These two observations mean that we can order the red arcs clockwise around the circle. Let the red arcs be $(L_i, R_i)$, with $L_i$ being the left (anticlockwise) endpoints and $R_i$ be the right (clockwise) endpoints. Then $L_i$ and $R_i$ are also ordered clockwise around the circle.

Now, we can assume that the only blue arcs we have are $( R_i, L_{i-1} )$, since it's easy to see that any legal blue arc covers one of these. If we have exactly one of these for each $i$, the theorem is true because, except for the endpoints of the arcs, every point is covered exactly $n-1$ times, and all the endpoints of the arcs are covered n times.

The only thing remaining is to prove that if we have multiple copies of some $( R_i, L_{i-1} )$, and none of others, the theorem still holds. Looking at examples this seems to be true, but I haven't found a proof.

Added: Sergei Ivanov has a very nice argument that completes the proof; see his answer.

Answer 3

The result you're trying to prove is a "circular" version of the colored Helly theorem for the line (see the first exercise on page 3 of these notes by Matousek). Although I haven't verified it, it seems like the proof technique used for this theorem might work on the circle as well (since it's a double counting trick, and the core lemma regarding the existence of a single point associated with each intersection of a subset of intervals is true on the circle as well)