The annual sausage convention is nearing, and it's time to look at the coming attractions...
A "Ramsey theorem" says loosely that one can find a structured subset of any size in a larger set, as long as the set is large enough.
The usual example of this is that if you take 6 points, connect all pairs, and then color each edge with either red or blue, you will always get a monochromatic triangle.
Erdos and Szekeres proved one of the first "geometric" Ramsey theorems, that said:
Theorem. For any k, there exists an n = n(k) such that all planar point sets of size n(k) have a convex subset of size k.
This subset is independent, in that all points are on the convex hull of this set.
However, if you change the problem slightly, things start getting interesting. Suppose that instead of asking for a convex subset, you wanted an empty convex subset. In general, suppose you want a "k-hole": a hole bounded by k points. Then the above theorem breaks down. Specifically,
Theorem (Horton). There exist arbitrarily large finite point sets in the plane that do not contain a 7-hole.
But we also know:
Every sufficiently large point set in the plane contains a 5-hole.
Which leaves as a tantalizing open question: What about 6 ?
Pinchasi, Radoicic and Sharir have a paper that develops some key combinatorial equalities and inequalities around this question.
Update: k = 6 is resolved.
