NEIGHBORLY TETRAHEDRA

3

In this article we present a solution to Bagemihl's conjecture, by proving the following.

Main Theorem: There exist no neighborly families in E-*, consisting of nine tetrahedra.

This result has been announced in [21]. For other results, dealing with neighborly families in

Ed, d 3, see [19, 20, 22]; for related results, see [14, 23, 6].

Our proof depends, in a very strong sense, on Baston's [2] result and technique. We

complement it with a few new ideas from Combinatorial geometry, graph theory and a number of

exhaustive searches by computer, done on our private Commodore 64.

The proof of the Main Theorem is presented in the first nine chapters. In chapter 1, assuming

that there exists a neighborly family F consisting of nine tetrahedra, we introduce its Baston matrix

B(F), the corresponding decomposition of K9 into complete bipartite graphs, the Diophantine

system of equations and its twenty four solutions. In Chapter 2 we give direct reasons showing

that ten of the solutions lead to contradictions. In Chapter 3 we introduce the notion of a type of a

tetrahedron in F, to be used later. In Chapter 4 we present a well-known lemma from Linear

Programming, which will be repeatedly used in showing that certain {0, ±l}-matrices cannot be

the Baston matrix B(f) of F. This leads to a few properties of the possible matrices, which are

translated into properties of the decomposition of K9. These properties will ease the task of search

by a computer. Chapters 5 - 9 treat separate cases of the computer search, where all the

corresponding decompositions of K9 are produced (up to combinatorial type), and each one of

them is shown to lead to a contradiction. In Chapter 10 we treat the problem of the maximum

number of combinatoriaily different neighborly families of eight tetrahedra in

E3,

and we close in

Chapter 11 by reproducing the proof, from [6], that there can be at most fourteen nearly-neighborly

tetrahedra in

E3.