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

Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so do all $n+2$.

This assertion is, logically speaking, a definite clause: All conditions are of the form "some subsets intersect", and so is the assertion. Generally, a definite clause about intersection of convex sets looks like this: Given some sets $S_1$, $S_2$, ..., $S_k$ and $T$ and a family $\left(F_a\right)_{a\in S_1\cup S_2\cup ...\cup S_k\cup T}$ of convex subsets of $\mathbb R^n$ indexed by the elements of $S_1\cup S_2\cup ...\cup S_k\cup T$, we claim that if every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $\bigcap\limits_{a\in S_i}F_a\neq\emptyset$, then $\bigcap\limits_{a\in T}F_a\neq\emptyset$.

Now it is an easy exercise to see that every tautological (= true for every choice of convex subsets) definite clause about intersection of convex sets is derivable using trivial properties of intersection (such as $A\cap A=A$, $A\cap B=B\cap A$ and $A\cap \left(B\cap C\right)=\left(A\cap B\right)\cap C$) and Helly's theorem only. (Note that we consider $n$ as given a priori and fixed during our proof, so we can't project on a subspace and use Helly for a smaller $n$, for example. We really only can manipulate intersections and use Helly for various intersection of convex subsets. I could write up what we can do as a natural deduction system, but it is pretty obvious.)

Now, what if we allow indefinite clauses? These are statements of the form: $S_1$, $S_2$, ..., $S_k$ and $T_1$, $T_2$, ..., $T_l$ and a family $\left(F_a\right)_{a\in S_1\cup S_2\cup ...\cup S_k\cup T_1\cup T_2\cup ...\cup T_l}$ of convex subsets of $\mathbb R^n$ indexed by the elements of $S_1\cup S_2\cup ...\cup S_k\cup T_1\cup T_2\cup ...\cup T_l$, we claim that if every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $\bigcap\limits_{a\in S_i}F_a\neq\emptyset$, then at least SOME $j\in\left\lbrace 1,2,...,l\right\rbrace$ satisfies $\bigcap\limits_{a\in T_j}F_a\neq\emptyset$.

What set of "axioms" (such as Helly's theorem) do we need in order to prove such indefinite clauses, if they are tautological? By "prove" I mean prove without using the convexity of the sets or that the sets are set at all (a pointfree approach, so to speak) - only using formal properties of $\cap$, logic (let's say constructive) and these axioms. Obviously Helly alone is not enough anymore; for example, for $n=1$ we have this here: If $A$, $B$, $C$, $D$ are four convex subsets of $\mathbb R^n$ such that $A\cap B$, $B\cap C$, $C\cap D$ and $D\cap A$ are nonempty, then at least one of the sets $A\cap C$ and $B\cap D$ are nonempty.

A connection to temporal logic is possible, but to be honest I have no idea about temporal logic; if somebody could point me to a reference that is of help here this might change...

share|improve this question
2  
You might want to look at the notion of "convexity space" (also known as closure system), which is an abstract of notion of convexity much like the topological space is an abstraction of the notion of a metric space. There is even a book on the topic by van der Val "Theory of convex structures". I do not know the answer to your question though. –  Boris Bukh Nov 10 '10 at 15:27
1  
In similar vein to Boris' comment: I seem to recall that there is some work of (Tobias?) Fritz on theories of convex sets (in a universal algebra/category theory sense) - but I may have misremembered or misinterpreted –  Yemon Choi Nov 10 '10 at 18:27
    
is your example ok? what if A, B, C, D are sides of a square? –  Fedor Petrov Nov 10 '10 at 19:53
    
I said $n=1$ ;) –  darij grinberg Nov 10 '10 at 23:35
1  
Now, Darij, how do you propose to derive the one-dimensional statement that if $A_1$ intersects $A_2$, $A_2$ intersects $A_3$, ... $A_m$ intersects $A_1$, then there is at least one more intersection from any correct Horn clouses of your type about at most $m-1$ sets each? I mean, neither of them will allow you to draw any non-trivial conclusion here. –  fedja Jan 7 '11 at 6:32
show 3 more comments

2 Answers

up vote 7 down vote accepted

This is an interesting question. (Even if there is no finite list of "axioms".)

For example the following is true: Suppose you have a (d+1)-dimensional polytope P. Associate a convex set in $R^d$ to every facet of P, and suppose that every non empty intersection among the facets implies a non empty intersection for the corresponding sets. Then there are some set of facets of the polytope with empty intersection so that the corresponding convex sets have non empty intersection. This is a large collection of statements of the kind you asked that already includes Helly's theorem.

Note that the nerve theorem gives you a lot of information on intersection patterns that cannot be realized. (Including the statement made above.)

A stronger statement for the case described above goes as follows: Suppose that 0 is in the interior of P. Then you can find two faces of F and G of P so that 0 is in their convex hull and the intersection of all sets corresponding to facets containing F and all sets corresponding to facets containing G is nonempty. This can be derived from the Borsuk-Ulam theorem.

Another well known result of the kind you ask about is the colorful Helly theorem (proved by Lovasz and a dual Caratheodory version was proved independently by Barany). It sais that if you have d+1 collections of convex sets in R^d, and if for every choice of one set from each collection there is a point common to all chosen sets then there is a collection all whose members have a point in common.

For n=1 there is a theorem by Lekkerkerker and Boland characterizing interval graphs. The characterization is based on two requirements: (1) there are no induced cycles of length >3. (This leaves us with chordal graphs.) (2) for every 3 vertices, one of the vertices is a neighbor of a vertex in every path between the other two. This gives an infinite set of "axioms" in the sense asked in the question. I suppose there is no finite list.

So overall there are many interesting theorems of the kind you described, and this is a rich area. But a complete description for dimension > 1 does not look realistic.

A more general question is to study the situation where you allow both operation: (1) taking the intersection (2) taking convex hull. This makes the problem even much more complicated and not much is known. An example of a recent result in this more general setting is the following theorem by Novick: Given 7.2k pairwise disjoint convex sets in the plane there is a set in the family that is disjoint to the convex hull of k other sets in the family.

share|improve this answer
    
Is "$(d+1)$-polytope in $\mathbb{R}^d$" a typo? –  Joseph O'Rourke Feb 12 '11 at 19:57
    
Thanks, Joe, fixed. –  Gil Kalai Feb 12 '11 at 20:08
    
"Then you can dind two faces of F and G of P so that 0 is in their convex hull and the intersection of all sets corresponding to faces containing F and all faces corresponding to faces containing G is nonempty." There seem to be several typos here. Other than that, nice list of theorems! –  darij grinberg Feb 12 '11 at 20:16
    
I no longer believe in the existence of a complete description anyway, though the $n=1$ case might have one. –  darij grinberg Feb 12 '11 at 20:16
    
Darij, I added something about n=1. –  Gil Kalai Feb 12 '11 at 23:10
show 1 more comment

I have a kind of heuristical reason why the case $n=2$ is hard, i. e. for $n=2$ there is no finite set of deduction rules from which we can derive every Horn clause about convex sets (without using any other properties of convex sets). This is not a proof, but it is convincing enough for me to stop considering the $n\geq 2$ case. As for $n=1$, I have no idea.

So here is the argument. For any graph $G$ with (finite) vertex set $V$ and edge set $E$, we can fix a total order on the set $V$, and consider the following Horn clause:

The planarity clause of the graph $G$: LET $P_{u,v}$ be a convex set for any two vertices $u$ and $v$ of $G$ satisfying $u < v$. IF $P_{u,v}\cap P_{t,r}\neq\emptyset$ whenever the sets $\left\lbrace u,v\right\rbrace$ and $\left\lbrace t,r\right\rbrace$ have a common element, THEN we have $P_{u,v}\cap P_{t,r}\neq\emptyset$ for at least one quadruple $\left(u,v,t,r\right)$ of vertices of $G$ such that the sets $\left\lbrace u,v\right\rbrace$ and $\left\lbrace t,r\right\rbrace$ have no common element.

We can easily find that the planarity clause of the graph $G$ is always satisfied if and only if the graph $G$ is not planar. (What we actually are using here is Fáry's theorem.) Now, Kuratowski's theorem shows us that we have non-planar graphs of arbitrarily large size that can only be proven planar by looking at ALL of their vertices together. For example, take $K_5$, and "blow it up" by replacing every edge by a sequence $\cdot - \cdot - \cdot - \cdot - ... - \cdot$ of little edges. Remove any of the edges and you get a planar graph, so if there was a finite family of rules from which all tautologies would follow, at least one of these rules would be talking about a big number of convex sets (namely, at least as many as you have edges in your blown up $K_5$). Contradiction.

As I said, I don't know whether this is really a sound argument, and even if it is, the case $n=1$ still remains open.

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.