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

About these ads
This entry was posted in Combinatorics, Geometry, Open problems and tagged , , , , . Bookmark the permalink.

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

  1. Pingback: Some old and new problems in combinatorics and geometry | Combinatorics and more

  2. Pingback: Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture | Combinatorics and more

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