Home » Discrete Geometry » Some musings around Borsuk’s conjecture

Some musings around Borsuk’s conjecture

Borsuk conjectured in 1933 that any bounded subset of n-dimensional Euclidean space can be partitioned into n+1 parts, all of smaller diameter. An equilateral simplex shows that that you need at least n+1 parts. The famous Borsuk-Ulam theorem can be formulated as saying that you also need at least n+1 parts for the Euclidean (n-1)-sphere. (Note that n+1 parts also suffice for the sphere.)

Borsuk’s conjecture is true in dimensions 2 and 3. In 1993 Kahn and Kalai proved that the conjecture is false if the dimension is sufficiently large. For a short explanation by Gil Kalai, click here. For a wonderful (very) short story on how their proof came about, click here. The lowest dimension for which it is currently known that the conjecture fails is n=298, due to Aicke Hinrichs and Christian Richter.

It is not so difficult to prove the 2-dimensional case. The 3-dimensional case, first proved by Eggleston, is somewhat messy. A short proof for finite sets in 3-space was found by Heppes and Revesz (1956). It goes as follows.

The number of diameter pairs in a set S of n points in 3-space is at most 2n-2. (A diameter pair of S is a pair of points in S whose distance equals the diameter of S.)

Therefore, the diameter graph of S has average degree at most 4-4/n. So we can always find a point incident to at most 3 diameters of S.

So we can greedily 4-colour the graph.

The colour classes give the partition!

Problem: Can this argument be modified easily to also work for infinite sets? For example, a solution to the following problem would imply Eggleston’s theorem:

Show that there exist \varepsilon>0 such that the graph G of almost-diameter pairs on any finite set S has chromatic number at most 4.

Here we define G of almost-diameter pairs to be the graph on S with edges all pairs of points at distance at least 1-\varepsilon times the diameter of S.

In general, it is not clear how to go from finite sets to general bounded sets. So it is “conceivable” for example that the conjecture holds for all finite sets in 4-dimensional space, but not for all bounded sets….

About these ads

2 thoughts on “Some musings around Borsuk’s conjecture

  1. Dear Konard,

    I think it is a very good question if the bounds for Borsuk’s problem are the same for finite sets and infinite sets. I vaguely remember (but I am not sure) that the proof for the finite case in space did lead to a simpler proof for the entire problem.

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