Micha Perles’ Geometric Proof of the Erdos-Sos Conjecture for Caterpillars

A geometric graph is a set of points in the plane (vertices) and a set of line segments between certain pairs of points (edges). A geometric graph is simple if the intersection of  two edges is empty or a vertex of both. A geometric graph is convex if the vertices are in convex position. A geometric caterpillar is a geometric tree that looks like this. Theorem (Micha Asher Perles, mid 80s): Let T be a caterpillar with k edges. Every convex geometric graph with [n(k-1)/2]+1 edges  contains a simple copy of T. As a matter of fact, T can be embedded in G is an orientation preserving manner.

Proof: Let G be a convex geometric graph with n vertices and e edges. For every edge of G we will consider two half edges, where a half edge is a  small subinterval of the edge containing one of its vertices.  Thus G has 2e half edges.

Let T be a caterpillar with k edges.  Suppose that the left most non-leave, b,  of T has m+1 neighbors and let S be the geometric caterpillar obtained by removing from S the m left most neighbors of  a and the edges containing them. S has k-m edges. Let w denote the left most half edge of T.  An half edge u of G is good (for T) if we can embed T in an orientation preserving manner so that  w is mapped to u. Otherwise, u is bad.

the following is stronger than the Theorem.

Claim: There are at most (k-1)n bad half edges.

Proof by induction on T. For every vertex of G call its m left most half edges nasty. By induction G has at most (k-m)n bad (for S) half edges. Altogether there are at most (k-1m)n+mn=(k-1)m half edges which are either bad for S or nasty. We map every half edge y coming from a vertex x which is neither nasty nor bad for S to another half edge z as follows. First consider the half edge which is the (m+1)th to its left from x. (There is such a half edge because y was not nasty.)  The other half edge on the same edge. This half edge is good for T and therefore there are at most (k-1)n bad half edges for T. Sababa!

Remarks: See this post for a proof about geometric graphs by lice. The Erdos-Sos conjecture (whose solution for $n> n_0(k)$ was achieved by Ajtai, Komlos and Szemeredi) asserts that a graph with n vertices and more than [(k-1)n/2] edges contains every tree with k edges. (See, here and here). The case where $T$ is a path was proved by Erdos and Gallai.

1. Ilan says: