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.

This entry was posted in Combinatorics, Geometry and tagged , . Bookmark the permalink.

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

  1. Ilan says:

    Interesting problem. I’m not sure I understand the end of the proof of the claim, though.

    You map the (m+1)th left half-edge coming from x to the other half-edge on the same edge? and you do the same with the (m+2)th left half-edge, (m+3)th… etc.? and all these half-edges are good for T? is this the mapping? Also, I think that in the second line of the proof of the claim it should be (k-m-1) instead of (k-m), and the r.h.s. of the equation in the beginning of the following line should be (k-1)n.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s