Proof By Lice!

From camels to lice. (A proof promised here.)

Theorem (Hopf and Pannwitz, 1934): Let X be a set of n points in the plane  in general position (no three points on a line) and consider n+1 line segments whose endpoints are in X.  Then there are two disjoint line segments.

Micha Perles’s proof by Lice:

Useful properties of lice: A louse lives on a head and wishes to lay an egg on a hair.

Think about the points in the plane as little heads, and think about each line segments between two points as a hair.

The proof goes as follows:

Step one: You take n lice from your own head and put them on the n points of $X$.

Step two: each louse examines the hairs coming from the head and lay eggs (on the hair near the head)

Step three (not strictly needed): You take back the n lice and put them back on your head.

To make it work we need a special type of lice: spoiled-left-wing-louse.

A spoiled-left-wing louse lays an egg on a hair if and only if the area near the head,  180 degrees to the right of this hair is free from other hairs.

lice1

Lemma: Every louse lays at most one egg.

Proof of lemma: As you see from the picture, if the louse lays an egg on one hair, this hair disturbs every other hair.

Proof of theorem continued: since there are n+1 line segments and only at most n eggs there is a hair X between heads A and B with no eggs.

We look at this hair and ask:

Why don’t we have an egg near head A: because there is a hair Y in the angle 180° to the right.

Why don’t we have an egg near head B: because there is a hair Z in the angle 180° to the right.

Y and Z must be disjoint. Q. E. D.

zig

Remarks: We actually get a ZIG formed by Y, X, and Z

If we use right-wing-spoiled lice we will get a ZAG.

zag

We can allow the points not to be in general position as long as one hair from a head does not contain another hair from the same head.

The topological version of this problem is the infamous Conway’s thrackle conjecture. See also Stephan Wehner page about it.

Advertisements
This entry was posted in Combinatorics, What is Mathematics and tagged . Bookmark the permalink.

6 Responses to Proof By Lice!

  1. One can ask the question in the dual plane (points become lines and lines become points) and so extend it to pseudo-lines. Thm 1.10 here: https://www.cs.bgu.ac.il/~shakhar/my_papers/pseudolines.ps
    extends those idea to pseudolines…

  2. shacharlovett says:

    are louse = lice?

  3. Pingback: Micha Perles’ Geometric Proof of the Erdos-Sos Conjecture for Caterpillars | Combinatorics and more

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s