Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
I misread the question and deleted a stupid answer. –  Steve Huntsman Jun 21 '10 at 3:46
    
Are the arcs open or closed? –  Roland Bacher Jun 21 '10 at 8:11
2  
It does not matter whether they are opened or closed, the intersection patterns are the same, just think about it a bit - you can enlarge any point to an interval. –  domotorp Jun 21 '10 at 14:42
    
Suppose you start a (hypothetical) proof sketch as follows: "Suppose that there is a point on the circle which is covered by as few arcs as possible. Let's remove that point and consider the same configuration on a line, except that the few arcs have turned into pairs of rays. Then ..." Is it possible to finish this with something like Helly's theorem, as at least n+1 of the "arcs" will be connected? Gerhard "Ask Me About System Design" Paseman, 2010.06.21 –  Gerhard Paseman Jun 21 '10 at 18:49
2  
This is from Miklos Schweitzer 2000 (math.u-szeged.hu/~mmaroti/schweitzer/schweitzer-2000-eng.pdf). Do you know, who proposed it, what is his/her solution and are solutions of MS published anywhere? –  Fedor Petrov Jun 23 '10 at 16:06
show 5 more comments

3 Answers 3

up vote 12 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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)

share|improve this answer
    
It would be helpful if you indicate a correct link. If this is a book, please give its decription. –  Wadim Zudilin Jun 21 '10 at 10:32
    
Perhaps Lectures on Discrete Geometry? Don't know how to make a link in a comment, but it is available via Google Books. I also found a paper entitled, "On cliques of Helly Circular-arc Graphs," M.C.Lin et al, but did not determine if it helps with G.Z.'s question. –  Joseph O'Rourke Jun 21 '10 at 11:46
2  
The correct link is probably citeseerx.ist.psu.edu/viewdoc/… or citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.661, and the paper is Jiri Matousek, Piercing and Selection Theorems in Convexity (lecture Notes). –  Zsbán Ambrus Jun 21 '10 at 14:18
1  
It is not true that all reds or blues have a common intersection, eg. take n=3 and all three edges of a triangle to be both red and blue. –  domotorp Jun 21 '10 at 14:53
    
As I am reading linearly, I just noticed that the same example was given by Thorny for Leandro's answer. –  domotorp Jun 21 '10 at 14:55
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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