A tree of convex sets?
This was suggested by a problem on FreeNode's #math a little while ago...
Construct a directed graph $\Gamma$ with vertex set the set of compact convex sets in $\mathbb R^2$, and an arrow $A\to B$ if $A$ and $B$ are disjoint and there is a point $a$ in $A$ and a $t>0$ such that $a+(t,0)$ is in $B$.
I guess there are no oriented cycles in $\Gamma$, so it is a directed acyclic graph. Can you give a non-ugly proof?
Later: Rahul's example below shows that this is too much to hope for. In fact, what I really wanted is to know if the subgraph spanned by every finite set of disjoint convex sets has no cycles.
Solution 1:
Am I misunderstanding the conditions of the problem or is this a counterexample?
Later: I think the answer to your updated question is yes -- or rather, no, any subgraph induced by disjoint convex sets has no cycles. (However, that would make it a directed acyclic graph or DAG, and not a tree, unless that's computer science terminology.) I have a sketch of what I think should be a valid proof, but filling in the details is a little ugly. Unfortunately, I think there is no completely non-ugly proof, for two reasons:
The power of convexity is a little lost because separating hyperplanes are of no help here. If $A \rightarrow B \rightarrow C$, there is not necessarily a hyperplane separating $C$ from $A \cup B$.
The proposition is not valid in more than 2 dimensions, so any proof must fundamentally depend on the 2D nature of the problem.
That said, here's the fairly ugly proof I got. Suppose for the sake of contradiction that there is a cycle of disjoint compact convex sets, $A_1 \rightarrow A_2 \rightarrow \cdots \rightarrow A_n \rightarrow A_1$. Each set $A_i$ contains a pair of points $p_i$ and $q_i$ such that $q_{i-1} \rightarrow p_i$ and $q_i \rightarrow p_{i+1}$ (where $i+1$ and $i-1$ are modulo $n$, of course). Therefore, it suffices to prove the impossibility of a cycle on the line segments $p_1 q_1 \rightarrow p_2 q_2 \rightarrow \cdots \rightarrow p_n q_n \rightarrow p_1 q_1$.
Consider the rightmost "fringe" of the first $i$ segments, as a function of $y$; that is, let $f_{i}(y) = \sup \\{x : (x,y) \in p_1 q_1 \cup p_2 q_2 \cup \cdots \cup p_i q_i\\}$. While $f_i$ is not continuous, I think you can prove by induction that if $p_1 q_1 \rightarrow p_2 q_2 \rightarrow \cdots \rightarrow p_i q_i \rightarrow p_{i+1} q_{i+1}$, then the discontinuities of $f_i$ are not "visible" to $p_{i+1}$. What I mean is that $f_i$ jumps leftwards rather than rightwards as you move in $y$ away from $p_{i+1}$, so there is no way for $q_{i+1}$ to sneak in to the left of $f_i$ without the segment $p_{i+1}q_{i+1}$ intersecting $f_i$ somewhere. Therefore, every $p_{i+1}$ and $q_{i+1}$ is to the right of $f_i$. In particular, $q_n$ is to the right of $f_{n-1}$. But $p_1$ is on or to the left of $f_{n-1}$, so $q_n \rightarrow p_1$ is impossible.
Solution 2:
Here is a simple proof that the directed graph induced by disjoint convex sets is acyclic.
Suppose there is a counter-example, then there must be one with the smallest number of convex sets involved. Suppose such a counter example is given by the convex sets $C_1,C_2,\dots,C_n$. Then the directed cycle must contain all the $C_i$'s by the minimality assumption (otherwise just throw the ones not in the cycle away to get a smaller counter-example). WLOG, assume the graph contains $C_1\to C_2\to \cdots \to C_n\to C_1$.
Lemma: There are no other edges in this graph.
Proof: If we had $A_k\to A_r$ with $k\neq r-1 \pmod{n}$, then $A_k\to A_r\to A_{r+1}\to \cdots \to A_k$ would be a shorter cycle which contradicts our minimality assumption.
So far we haven't used that these are convex sets. Now the trick is that if there is no $A_k$ which intersects the convex hull of $A_r \cup A_{r+1}$ then substituting $A_r$ and $A_{r+1}$ with their convex hull gives a smaller collection of convex sets with a cycle.
Now by applying the lemma it follows that to show that no such $A_k$ can exist, it is enough to prove that if $A_k$ intersects the convex hull of $A_r \cup A_{r+1}$ then either $A_r \to A_k$ or $A_k \to A_{r+1}$, but this is obvious if you draw the picture, so I'll leave it as an exercise :)
Since there are no two convex sets $A\to B \to A$, we are done.