Erdős-Szekeres empty pseudoconvex $k$-gons

2012-02-15T01:56:39Z

I am wondering if the Erdős-Szekeres empty convex $k$-gon question has a different answer if convexity is replaced by a pseudoline-version of convexity.

The empty convex $k$-gon question is a variant on the Happy Ending Problem. The last remaining case, $k=6$, was settled about four years ago. It is now known that, although there arbitarily large point sets in the plane with no empty convex heptagon, every sufficiently large set contains an empty convex hexagon.

Here is my attempt to generalize this to pseudolines. An arrangement of pseudolines is a collection of curves each pair of which intersects in exactly one point, at which they cross. There are nonstretchable pseudoline arrangements, i.e., those not combinatorially equivalent to any straight-line arrangement. Here's one:

_{(Image by David Eppstein)}
In fact, there are many more pseudoline arrangements— $2^{\Omega(n^2)}$, than straight-line arrangements— $2^{O(n \log n)}$, for $n$ lines and simple arrangements.

All the above are facts. Caveat: my attempt at defining convexity in this context might not make sense. Given $n$ points in the plane, say that they contain an empty pseudoconvex $k$-gon if

there is an arrangement $\cal{A}$ of $\binom{n}{2}$ pseudolines through the $n$ points.
there is an empty $k$-gon $K$, a region of the plane bounded by $k$ pseudolines containing no points in its interior.
$K$ is convex in the sense that for any two additional points $a,b$ inside $K$, one can find a pseudoline through $a,b$ compatible with the arrangement $\cal{A}$, such that the pseudosegment $ab \subset K$.

Assuming this definition is not inconsistent, does the Erdős-Szekeres empty convex $k$-gon question have a different answer? For example, perhaps every sufficiently large point set always has a pseudoconvex heptagon?

Aside from this question, I would be interested in learning of convexity definitions analogous to what I tried to define above. Thanks for pointers/ideas!

Erdős-Szekeres empty pseudoconvex $k$-gons - MathOverflow

Erdős-Szekeres empty pseudoconvex $k$-gons