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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Douglas Zare Aug 21 '14 at 23:24

(Long comment, not an answer to the question posed.)

One way to generalise "general position" configurations of lines in the plane is to assign an orientation "clockwise" or "anticlockwise" to each set of three points and require a small set of axioms to hold. These purely combinatorial objects were called CC systems by Don Knuth in his book "Axioms and Hulls". In the book he proves a correspondence with geometric configurations of pseudolines. There is also a combinatorial definition of "convex polygon" and "interior", so the problem can be stated in a purely combinatorial form. I suggest you check that out as it will probably match your intuition.

Note that the original happy ending problem for 17 points, proved by Peters and Szekeres by computer, also holds for CC systems using much the same computation.

  • $\begingroup$ Excellent! Thanks for that reference. I actually own the book, but it's been too long since I looked in it. $\endgroup$ – Joseph O'Rourke Mar 24 '17 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.