Theory of Combinatorial Algorithms, Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich

No Title

Coloring of Hamming Graphs and the 0/1-Borsuk Problem

Günter Ziegler, Technische Universität Berlin

The 0/1-Borsuk problem asks whether any set of 0/1-vectors in ${\mathbb R}^d$ can be partitioned into at most d+1 sets of smaller diameter. This is known to be false in high dimensions (in particular for d=560, due to Kahn & Kalai, Nilli, Raigorodskii, and Weißbach), and yields counterexamples to Borsuk's problem from 1933.

Here we ask whether there might be 0/1-counterexamples in low dimension as well. This leads us to a study of colorings of Hamming graphs and of more general Borsuk graphs, which uses some coding theory bounds, and also involves Hamming codes to get some explicit colorings. Putting things together, we derive that there is no counterexample to the 0/1-Borsuk conjecture in dimension $d\le8$ . In contrast, the general Borsuk conjecture is open even for d=4.

In our study we also find that $13\le\chi(H_{9,2})\le14$ . This disproves the conjecture that $\chi(H_{n,2})=2^{\lceil\log n\rceil}$ holds for all $n\ge2$ .

Back