Category Archives: Convexity

From Oberwolfach: The Topological Tverberg Conjecture is False

The topological Tverberg conjecture (discussed in this post), a holy grail of topological combinatorics, was refuted! The three-page paper “Counterexamples to the topological Tverberg conjecture” by Florian Frick gives a brilliant proof that the conjecture is false.

The proof is based on two major ingredients. The first is a recent major theory by Issak Mabillard and Uli Wagner which extends fundamental theorems from classical obstruction theory for embeddability to an obstruction theory for r-fold intersection of disjoint faces in maps from simplicial complexes to Euclidean spaces. An extended abstract of this work is Eliminating Tverberg points, I. An analogue of the Whitney trick. The second is a result  by Murad Özaydin’s from his 1987 paper Equivariant maps for the symmetric group, which showed that for the non prime-power case the topological obstruction vanishes.

It was commonly believed that the topological Tverberg conjecture is correct. However, one of the motivations of Mabillard and Wagner for studying elimination of higher order intersection was that this may lead to counterexamples via Özaydin result. Isaak and Uli came close but there was a crucial assumption of large codimension in their theory, which seemed to avoid applying the new theory to this case.  It turned out that a simple combinatorial argument allows to overcome the codimension problem!

Florian’s  combinatorial argument which allows to use Özaydin’s result in Mabillard-Wagner’s theory  is a beautiful example of a powerful combinatorial method with other applications by Pavle Blagojević, Florian Frick and Günter Ziegler.


Both Uli and Florian talked about it here at Oberwolfach on Tuesday. I hope to share some more news items from Oberwolfach and from last week’s Midrasha in future posts.

Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture

Borsuk asked in 1933 if every bounded set K of diameter 1 in R^d can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. Many interesting open problems remain.  The first two posts in the series “Around Borsuk’s Conjecture” are here and here. See also these posts (I,II,III, IV), and the post “Surprises in mathematics and theory” on Lipton and Reagan’s blog GLL.

Can we save the conjecture? We can certainly try, and in this post I would like to examine the possibility that Borsuk’s conjecture is correct except from some “coincidental” sets. The question is how to properly define “coincidental.”

Let K be a set of points in R^d and let A be a set of pairs of points in K. We say that the pair (K, A) is general if for every continuous deformation of the distances on A there is a deformation K’ of K which realizes the deformed distances.

(This condition is related to the “strong Arnold property” (aka “transversality”) in the theory of Colin de Verdière invariants of graphs; see also this paper  by van der Holst, Lovasz and Schrijver.)

Conjecture 1: If D is the set of diameters in K and (K,D) is general then K can be partitioned into d+1 sets of smaller diameter.

We propose also (somewhat stronger) that this conjecture holds even when “continuous deformation” is replaced with “infinitesimal deformation”.

The finite case is of special interest:

A graph embedded in R^d is stress-free if we cannot assign non-trivial weights to the edges so that the weighted sum of the edges containing any  vertex v (regarded as vectors from v) is zero for every vertex v. (Here we embed the vertices and regard the edges as straight line segments. (Edges may intersect.) Such a graph is called a “geometric graph”.) When we restrict Conjecture 1 to finite configurations of points we get.

Conjecture 2: If G is a stress free geometric graph of diameters in R^d  then G is (d+1)-colorable.

A geometric graph of diameters is a geometric graph with all edges having the same length and all non edged having smaller lengths. The attempt for “saving” the Borsuk Conjecture presented here and Conjectures 1 and 2 first appeared in a 2002 collection of open problems dedicated to Daniel J. Kleitman, edited by Douglas West.

When we consider finite configurations of points  we can make a similar conjecture for the minimal distances:

Conjecture 3: If the geometric graph of pairs of vertices realizing the minimal distances of a point-configuration in R^d is stress-free, then it is (d+1)-colorable.

We can speculate that even the following stronger conjectures are true:

Conjecture 4: If G is a stress-free geometric graph in R^d so that all edges in G are longer than all non-edges of G, then G is (d+1)-colorable.

Conjecture 5: If G is a stress-free geometric graph in R^d so that all edges in G are shorter than all non-edges of G, then G is (d+1)-colorable.

We can even try to extend the condition further so edges in the geometric graph will be larger (or smaller) than non-edges only just “locally” for neighbors of each given vertex.


1) It is not true that every stress-free geometric graph in R^d is (d+1)-colorable, and not even that every stress-free unit-distance graph is (d+1)-colorable. Here is the (well-known) example referred to as the Moser Spindle. Finding conditions under which stress-free graphs in R^d are (d+1)-colorable is an interesting challenge.


2) Since a stress-free graph with n vertices has at most dn - {{d+1} \choose {2}} edges it must have a vertex of degree 2d-1 or less and hence it is 2d colorable. I expect this to be best possible but I am not sure about it. This shows that our “saved” version of Borsuk’s conjecture is of very different nature from the original one. For graphs of diameters in R^d the chromatic number can, by the work of Jeff and me be exponential in \sqrt d.

3) It would be interesting to show that conjecture 1 holds in the non-discrete case when  d+1 is replaced by 2d.

4) Coloring vertices of geometric graphs where the edged correspond to the minimal distance is related also the the well known Erdos-Faber-Lovasz conjecture.ERDSFA~1.

See also this 1994 article by Jeff Kahn on Hypergraphs matching, covering and coloring problems.

5) The most famous conjecture regarding coloring of graphs is, of course, the four-color conjecture asserting that every planar graph is 4-colorable that was proved by Appel and Haken in 1976.  Thinking about the four-color conjecture is always both fascinating and frustrating. An embedding for maximal planar graphs as vertices of a convex 3-dimensional polytope is stress-free (and so is, therefore, also a generic embedding), but we know that this property alone does not suffice for 4-colorability. Finding further conditions for  stress-free graphs in R^d that guarantee (d+1)-colorability can be relevant to the 4CT.

An old conjecture of mine asserts that

Conjecture 6: Let G be a graph obtained from the graph of a d-polytope P by triangulating each (non-triangular) face with non-intersecting diagonals. If G is stress-free (in which case the polytope P is called “elementary”) then G is (d+1)-colorable.

Closer to the conjectures of this post we can ask:

Conjecture 7: If G is a stress-free geometric graph in R^d so that for every edge  e of G  is tangent to the unit ball and every non edge of G intersect the interior of the unit ball, then G is (d+1)-colorable.

A question that I forgot to include in part I.

What is the minimum diameter d_n such that the unit ball in R^n can be covered by n+1 sets of smaller diameter? It is known that 2-C'\log n/n \le d_n\le 2-C/n for some constants C and C’.

Around Borsuk’s Conjecture 1: Some Problems

Greetings to all!

Karol Borsuk conjectured in 1933 that every bounded set in R^d can be covered by d+1 sets of smaller diameter. In a previous post I described the counterexample found by Jeff Kahn and me. I will devote a few posts to related questions that are still open. I will list and discuss such questions in the first and second  parts. In the third part I will describe an approach towards better examples which is related to interesting extremal combinatorics. (Of cocyclec. this post appeared already.) In the fourth part I will try to “save the conjecture”, namely to present a variation of the conjecture which might be true. Let f(d) be the smallest integer so that every set of diameter one in R^d can be covered by f(d) sets of smaller diamete

Continue reading

The Combinatorics of Cocycles and Borsuk’s Problem.


Definition:  A k-cocycle is a collection of (k+1)-subsets such that every (k+2)-set T contains an even number of sets in the collection.

Alternative definition: Start with a collection \cal G of k-sets and consider all (k+1)-sets that contain an odd number of members in \cal G.

It is easy to see that the two definitions are equivalent. (This equivalence expresses the fact that the k-cohomology of a simplex is zero.) Note that the symmetric difference of two cocycles is a cocycle. In other words, the set of k-cocycles form a subspace over Z/2Z, i.e., a linear binary code.

1-cocycles correspond to the set of edges of a complete bipartite graph. (Or, in other words, to cuts in the complete graphs.) The number of edges of a complete bipartite graph on n vertices is of the form k(n-k). There are 2^{n-1} 1-cocycles on n vertices altogether, and there are n \choose k cocycles with k(n-k) edges.

2-cocycles were studied under the name “two-graphs”. Their study was initiated by J. J. Seidel.

Let e(k,n) be the number of k-cocycles.

Lemma: Two collections of k-sets (in the second definition) generate the same k-cocycle if and only if  their symmetric difference is a (k-1)-cocycle.

It follows that e(k,n)= 2^{{n}\choose {k}}/e(k-1,n). So e(k,n)= 2^{{n-1} \choose {k}}.

A very basic question is:

Problem 1: For k odd what is the maximum number f(k,n) of (k+1)-sets  of a k-cocycle with n vertices?

When k is even, the set of all (k+1)-subsets of {1,2,…,n} is a cocycle.

Problem 2: What is the value of m such that the number ef(k,n,m) of k-cocycles with n vertices and m k-sets is maximum?

When k is even the complement of a cocycle is a cocycle and hence ef(k,n,m)=ef(k,n,{{n}\choose{k+1}}-m). It is likely that in this case ef(k,n,m) is a unimodal sequence (apart from zeroes), but I don’t know if this is known. When k is odd it is quite possible that (again, ignoring zero entries) ef(n,m) is unimodal attaining its maximum when m=1/2 {{n} \choose {k+1}}.

Borsuk’s conjecture, Larman’s conjecture and bipartite graphs

Karol Borsuk conjectured in 1933 that every bounded set in R^d can be covered by d+1 sets of smaller diameter. David Larman proposed a purely combinatorial special case (that looked much less correct than the full conjecture.)

Larman’s conjecture: Let \cal F be an $latex r$-intersecting  family of k-subsets of \{1,2,\dots, n\}, namely \cal F has the property that every two sets in the family have at least r elements in common. Then $\cal F$ can be divided into n (r+1)-intersecting families.

Larman’s conjecture is a special case of Borsuk’s conjecture: Just consider the set of characteristic vectors of the sets in the family (and note that they all belong to a hyperplane.) The case r=1 of Larman’s conjecture is open and very interesting.

A slightly more general case of Borsuk’s conjecture is for sets of 0-1 vectors (or equivalently \pm 1 vectors. Again you can consider the question in terms of covering a family of sets by subfamilies. Instead of intersection we should consider symmetric differences.

Borsuk 0-1 conjecture: Let \cal F be a family of subsets of \{1,2,\dots, n\}, and suppose that the symmetric difference between every two sets in \cal F has at most t elements. Then $\cal F$ can be divided into n+1  families such that the symmetric difference between any pair of sets in the same family is at most t-1.

Cuts and complete bipartite graphs

The construction of Jeff Kahn and myself can be described as follows:

Construction 1: The ground set is the set of edges of the complete graph on 4p vertices. The family \cal F consists of all subsets of edges which represent the edge sets of a complete bipartite graph with 2p vertices in every part. In this case, n={{4p} \choose {2}}, k=4p^2, and r=2p^2.

It turns out (as observed by A. Nilli) that there is no need to restrict ourselves to  balanced bipartite graphs. A very similar construction which performs even slightly better is:

Construction 2: The ground set is the set of edges of the complete graph on 4p vertices. The family \cal F consists of all subsets of edges which represent the edge set of a complete bipartite graph.

Let f(d) be the smallest integer such that every set of diameter 1 in R^d can be covered by f(d) sets of smaller diameter. Constructions 1 and 2 show that f(d) >exp (K\sqrt d). We would like to replace d^{1/2} by a larger exponent.

The proposed constructions.

To get better bounds for Borsuk’s problem we propose to replace complete bipartite graphs with higher odd-dimensional cocycles.

Construction A: Consider all (2k-1)-dimensional cocycles  of maximum size (or of another fixed size) on the ground set \{1,2,\dots,n\}.

Construction B: Consider all (2k-1)-dimensional cocycles on the ground set \{1,2,\dots,n\}.

A Frankl-Wilson/Frankl-Rodl type problem for cocycles

Conjecture: Let \alpha be a positive real number. There is \beta = \beta (k,\alpha)<1 with the following property. Suppose that

(*) The number of k-cocycles on n vertices with m edges is not zero

and that

(**) m>\alpha\cdot {{n}\choose {k+1}}, and m<(1-\alpha){{n}\choose {k+1}}. (The second inequality is not needed for odd-dimensional cocycles.)

Let \cal F be a family of k-cocycles such that no symmetric difference between two cocycles in \cal F has precisely m sets. Then

|{\cal F}| \le 2^{\beta {{n}\choose {k}}}.

If true even for 3-dimensional cocycles this conjecture will improve the asymptotic lower bounds for Borsuk’s problem.  For example,  if true for 3-cocycles it will imply that f(d) \ge exp (K d^{3/4}). The Frankl-Wilson and Frankl-Rodl theorems have a large number of other applications, and an extension to cocycles may also have other applications.

Crossing number of complete graphs, Turan’s (2k+1,2k) problems, and cocycles

The question on the maximum number of sets in a k-cocycle when k is odd is related to several other (notorious) open problems.

Continue reading

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. Continue reading