Nerves of Convex Sets – A Recent Result by Martin Tancer

Martin Tancer recently found a very beautiful proof that finite projective planes can’t be represented by convex sets in any fixed dimension. This was asked in the paper entitled “Transversal numbers for hypergraphs arising in geometry” by Noga Alon, Gil Kalai, Jiri Matousek and Roy Meshulam some years ago. I am thankfull to Jirka Matousek for telling me about this development.

Here’s a very rough sketch of the argument:  Suppose that (P,{\cal L}) is a finite projective plane with n points, and suppose that for every line L \in P  there is a convex set C_L in R^d such that a subcollection of the C_L has a common point iff the corresponding lines L have a common point in the projective plane. In particular, for every x\in P we have a point a_x in R^d witnessing the intersection of all C_L for which L contains x. (This is kind of “dual” representation compared to the usual notion, but a projective plane is self-dual so it doesn’t matter, and the proof is perhaps more intuitive in this setting.)

Look at the set A = \{a_x: x\in P\}. By a theorem of Janos Pach, there are disjoint subsets A_1,...,A_{d+1} contained in A, such that |A_i| > c|A| for some (enormously small) c=c(d)>0, and the convex hulls of all transversals to (A_1,...,A_{d+1}) have a common point. Let X_1,...,X_{d+1} be the corresponding subsets in the projective plane.

Now by a theorem due to Noga Alon, if  B\subset P is any sufficiently large subset of the projective plane, then only few lines may miss it (quantitatively, at most n^{3/2}/|B| of the lines avoid B). Hence, since each X_i occupies a fixed fraction of P, most of the lines intersect all the X_i simultaneously. But then all the convex sets C_L corresponding to these lines intersect, and they shouldn’t since in the projective plane only at most \sqrt n lines may have a common point. QED

This result shows that a simplicial complex can fail to be the nerve of a family of convex sets in R^d even if it is 2-collapsible. (See this post for the termonology.) This is quite a remarkable result.

About these ads
This entry was posted in Convexity. Bookmark the permalink.

2 Responses to Nerves of Convex Sets – A Recent Result by Martin Tancer

  1. jc says:

    Does X=P?

    GK: Yes, corrected! Thanks.

  2. I am not sure I fully understand the “environment” in which this interesting result lives.

    If one has a finite affine plane there is a well known construction (adding points corresponding to parallel classes one to each “old” line, and placing these new points on a new line) which yields a finite projective plane. If one starts with a finite projective plane and deletes a single line the result is a finite affine plane.

    If the finite affine plane has n points on a line, then the plane has n^2 points, n + 1 lines through a point and n^2 + n lines, while the “associated” projective plane has n+1 points on a line, n^2 + n + 1 points and lines, and n+1 lines through a point.

    There are also finite hyperbolic planes (various definitions) and finite inversive planes.

    Then, there is the issue of drawing such finite planes in, say, the Euclidean plane so that all the lines of the finite planes lie along straight lines in the Euclidean plane. It is well known that this can not be done even for the Fano plane, the finite projective plane with 3 points on a line, but it is possible for the affine plane with 2 points on a line.

    So my question is, whether or not it has been studied whether the analogue of the theorem reported here has been studied for other types of finte planes (or even spaces)?.

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