MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

  1. there is an arrangement $\cal{A}$ of $\binom{n}{2}$ pseudolines through the $n$ points.
  2. there is an empty $k$-gon $K$, a region of the plane bounded by $k$ pseudolines containing no points in its interior.
  3. $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!

share|cite|improve this question
There must be some compatibility conditions between the usual geometry of the plane and the pseudolines. Otherwise, you can send any $n$ points and pseudolines through them to any other $n$ points and a combinatorially equivalent set of pseudolines, so there is nothing special about a given set of points, and you can choose the pseudolines so that the points are in convex position. This is not the case if you do something like say that the pseudolines have to be rotated graphs of functions. I don't know if that's a good condition but it's invariant under affine transformations. – Douglas Zare Aug 21 '14 at 23:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.