Tag Archives: Borsuk’s conjecture

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.

Comments:

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.

MoserSpindle_700

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’.

Andriy Bondarenko Showed that Borsuk’s Conjecture is False for Dimensions Greater Than 65!

The news in brief

Andriy V. Bondarenko proved in his remarkable paper The Borsuk Conjecture for two-distance sets  that the Borsuk’s conjecture is false for all dimensions greater than 65. This is a substantial improvement of the earlier record (all dimensions above 298) by Aicke Hinrichs and Christian Richter.

Borsuk’s conjecture

Borsuk’s conjecture asserted that every set of diameter 1 in d-dimensional Euclidean space can be covered by d+1 sets of smaller diameter. (Here are links to a post describing the disproof by Kahn and me  and a post devoted to problems around Borsuk’s conjecture.)

Two questions posed by David Larman

David Larman posed in the ’70s two basic questions about Borsuk’s conjecture:

1) Does the conjecture hold for collections of 0-1 vectors (of constant weight)?

2) Does the conjecture hold for 2-distance sets? 2-distance sets are sets of points such that the pairwise distances between any two of them have only two values.

Reducing the dimensions for which Borsuk’s conjecture fails

In 1993 Jeff Kahn and I disproved Borsuk’s conjecture in dimension 1325 and all dimensions greater than 2014. Larman’s first conjecture played a special role in our work.   While being a special case of Borsuk’s conjecture, it looked much less correct.

The lowest dimension for a counterexample were gradually reduced to  946 by A. Nilli, 561 by A. Raigorodskii, 560 by  Weißbach, 323 by A. Hinrichs and 320 by I. Pikhurko. Currently the best known result is that Borsuk’s conjecture is false for n ≥ 298; The two last papers relies strongly on the Leech lattice.

Bondarenko proved that the Borsuk’s conjecture is false for all dimensions greater than 65.  For this he disproved Larman’s second conjecture.

Bondarenko’s abstract

In this paper we answer Larman’s question on Borsuk’s conjecture for two-distance sets. We found a two-distance set consisting of 416 points on the unit sphere in the dimension 65 which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk’s conjecture is known to be false. Other examples of two-distance sets with large Borsuk’s numbers will be given.

Two-distance sets

There was much interest in understanding sets of points in R^n  which have only two pairwise distances (or K pairwise distances). Larman, Rogers and Seidel proved that the maximum number can be at most (n+1)(n+4)/2 and Aart Blokhuis improved the bound to (n+1)(n+2)/2. The set of all 0-1 vectors of length n+1 with two ones gives an example with n(n+1)/2 vectors.

Equiangular lines

This is a good opportunity to mention another question related to two-distance sets. Suppose that you have a set of lines through the origin in R^n so that the angles between any two of them is the same. Such  a set is  called an equiangular set of lines. Given such a set of cardinality m, if we take on each line one unit vector, this gives us a 2-distance set. It is known that m ≤ n(n+1)/2 but for a long time it was unknown if a quadratic set of equiangular lines exists in high dimensions. An exciting breakthrough came in 2000 when Dom deCaen constructed a set of equiangular lines in R^n with 2/9(n+1)^2 lines for infinitely many values of n.

Strongly regular graphs

Strongly regular graphs are central in the new examples. A graph is strongly regular if every vertex has k neighbors, every adjacent pair of vertices have λ common neighbors and every non-adjacent pair of vertices have μ common neighbors. The study of strongly regular graphs (and other notions of strong regularity/symmetry) is a very important area in graph theory which involves deep algebra and geometry. Andriy’s construction is based on a known strongly regular graph G_2(4).

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.

Cocycles

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

Raigorodskii’s Theorem: Follow Up on Subsets of the Sphere without a Pair of Orthogonal Vectors

raigor

Andrei Raigorodskii

(This post follows an email by Aicke Hinrichs.)

In a previous post we discussed the following problem:

Problem: Let A be a measurable subset of the d-dimensional sphere S^d = \{x\in {\bf R}^{d+1}:\|x\|=1\}. Suppose that A does not contain two orthogonal vectors. How large can the d-dimensional volume of A be?

Setting the volume of the sphere to be 1, the Frankl-Wilson theorem gives a lower bound (for large d) of  1.203^{-d},
2) The double cap conjecture would give a lower bound (for large d) of 1.414^{-d}.

A result of A. M. Raigorodskii from 1999 gives a better bound of 1.225^{-d}. (This has led to an improvement concerning the dimensions where a counterexample for Borsuk’s conjecture exists; we will come back to that.) Raigorodskii’s method supports the hope that by considering clever configurations of points instead of just \pm 1-vectors and applying the polynomial method (the method of proof we described for the Frankl-Wilson theorem) we may get closer to and perhaps even prove the double-cap conjecture.

What Raigorodskii did was to prove a Frankl-Wilson type result for vectors with 0,\pm1 coordinates with a prescribed number of zeros. Here is the paper.

Now, how can we beat the 1.225^{-d} record???

A Little Story Regarding Borsuk’s Conjecture

Jeff Kahn

Jeff and I worked on the problem for several years. Once he visited me with his family for two weeks. Before the visit I emailed him and asked: What should we work on in your visit?

Jeff asnwered: We should settle  Borsuk’s problem!

I asked: What should we do in the second week?!

and Jeff asnwered: We should write the paper!

And so it was.

You can download our paper here. Here is the proof itself. Continue reading