Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider nerve $\mathcal N$ of a finite set of convex sets in $\mathbb R^n$. Helly theorem says that $\mathcal N$ is completely determined by its $n$-skeleton, say $\mathcal N_n$.

It seems that not all finite simplicial complexes with dimension $\le n$ can appear as $\mathcal N_n$. (For example take 2-dimenisonal simplicial complex which is homeomorphic to $\mathbb{R}\mathrm{P}^2$, it can not appear as $\mathcal N_3$ for finite set of convex sets in $\mathbb R^3$.)

Is it possible to describe all finite simplicial complexes which can appear as $\mathcal N_n$?

  • The question is inspired by a short discussion here.

  • I am sure a lot should be known, but a quick search gave me nothing.

share|improve this question
1  
From the point of view of purely combinatorial obstructions, you can look at: G. Kalai, Intersection patterns of convex sets, Israel J. Math. 48 (1984) 161–174. –  Thierry Zell Apr 14 '11 at 1:32
add comment

2 Answers

up vote 11 down vote accepted

Nerves of convex sets in general

There is quite a bit known about nerves of families of convex sets in $R^n$. Indeed Helly's theorem asserts that the $n$-skeleton determines the entire complex. In fact, considerably more is known beyond Helly's theorem. It follows, for example that all homology group of the nerve vanish in dimensions larger or equal to n. Morover, this property is inherited to induced subcomplexes and to links of the nerve. (Because those are also nerves of families of convex sets in the same Euclidian space.)

For a survey see this paper: Martin Tancer, Intersection patterns of convex sets via simplicial complexes, a survey.

However, only little is known about the skeletons of the nerves below dimension n.

Every n dimensional complex can be represented as a nerve of convex sets in $R^{2n+1}$. This was proved by Wegner in 67 and again by Perel'man in 85. (This was Perel'man's first paper.) It is interesting to understand systematically obstructions for nerves of convex sets in $R^n$ whose dimension is between n/2 and n. For n=1 much is known. There are substantial results in the plane but not so many in higher dimensions.

Dimension 1 - interval graphs

There is a lot known about interval graphs which is what you ask about for n=1. This is a very restricted and well understood class of graphs. It is a subclass of the class of chordal graphs with itself is a very special class of the class of perfect graphs.

Families of convex sets in the Dimension 2

An example of the kind asked in the question to the best of my memory is obtained as follows: Start with a non planar graph, and divide every edge by adding a vertex in it. Then this graph is not a nerve of conves sets in the plane.

Since the question was about representing n dimensional complexes as nerves of families of convex sets in $R^m$ where $m>n$ let me mention a few specific results in this direction where n=1 and m=2.

Theorem (D. Larman, J. Matousek, J. Pach, J. Torocsik): For a family of planar convex sets either there is a subfamily of $n^{1/5}$ sets which are pairwise intersecting or there is a subfamily of $n^{1/5}$ sets which are pairwise disjoint.

(D. Larman, J. Matousek, J. Pach, J. Torocsik, A Ramsey-type result for convex sets. Bull. London Math. Soc. 26 (1994), no. 2, 132–136.)

A result which also directly follows from this paper is:

For a family of planar convex sets either

there is a family of p sets which are pairwise disjoint or

there is a family of $c_p n$ sets which are pairwise intersecting.

(It is not known if it is possible to replace “pairwise disjoint” with “pairwise intersecting” in this last theorem. Fox and Pach have some results in this direction.)

And the following beautiful theorem:

Theorem (J. Fox, J. Pach and Cs. D. Toth):

Every family of plane convex sets contains two subfamilies of size $cn$ such that:

either each element of the first intersects every element in the second, or

no element in the first intersects any element of the other.

Rough expected picture

Morally, graphs that are nerves of convex sets in the plane are far in their behavior from random graphs and come close (in a sense) to perfect graphs. (This comment applies to other graphs and hypergraphs arising in geometry.) Such statements (towards perfectness in a weak sense) are known to hold for the $n$-dimensional skeletons of nerves of families of convex sets in $R^n$. We may expect that this phenomena will start occuring (in weakers forms) already for $n/2$-dimensional skeleta but there are very few known results beyond the plane.

share|improve this answer
    
I took the liberty of fleshing out the example about non-planar graphs in my own answer. Thanks for the link to Tancer's paper! –  Thierry Zell Apr 14 '11 at 1:24
add comment

I really wish I knew more about general nerve complexes, so I'm afraid I don't have much to bring to your question. But information on intersection graphs is a lot easier to figure out, so I thought I'd add some remarks to what Gil wrote:

Non-planar Graphs

First, I want to explain how his remark about non-planar graphs works: say you have an edge between two vertices $u$ and $v$ of a graph $G$. Split the edge with a new vertex $e$ to get the new graph $G^\star$. Now, suppose that $G^\star$ is the intersection graph of some arrangement of convex sets in the plane, with sets $U$, $V$ and $E$ that correspond to the vertices of the same name. Then since there are edges $(u,e)$ and $(v,e)$ in $G^\star$, you can pick points $a\in U\cap E$ and $b\in V\cap E$, and the segment $[a,b]$ is of course contained in $E$.

Do this for all vertices of $G^\star$ that arose from adges in $G$. This gives you a collection of edges that must be pairwise disjoint since none of the $e$ vertices are adjacent to each other, they're only adjacent to vertices in $V(G)$. Now, contract the convex sets of type $U$ that correspond to vertices in $V(G)$: this keeps the segments disjoint (except for endpoints) and gives a picture of $G$ on the plane. Thus the convex arrangement fr $G^\star$ exists only if $G$ is planar.

Boxes and Graphs

Also, I think it's important to stress how special interval graphs are. To me, one of the best way to see this is to consider the natural generalization: instead of intervals in $\mathbb{R}$, consider boxes: cartersian products of intervals in $\mathbb{R}^d$. Then, F. S. Roberts proved (in his PhD thesis I think) that any graph can be realized as the intersection graph of a collection of $d$-boxes, and we can even take $d\leq |V(G)|/2$. (The smallest dimension you can choose for a graph $G$ is called the boxicity of $G$.)

If you'd rather look at more general convex sets, then it's been known for even longer that you can realize a graph as the intersection pattern of convex sets of $\mathbb{R}^3$ (and thus showing some sort of counterpoint to Gil Kalai's answer in dimension 2). The obvious conclusion: nerve complexes carry a lot more information than graphs; nothing new or surprising there, but these examples can help you really appreciate that.

References

Roberts, F. S. (1969), "On the boxicity and cubicity of a graph", in Tutte, W. T., Recent Progress in Combinatorics, Academic Press, pp. 301–310,

share|improve this answer
add comment

Your Answer

 
discard

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

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