A famous problem asks for the minimum number of crossings in any drawing of the complete graph K(n) in the plane. It conjectures that: 

Suppose the vertex set of K(n) is I(n) = {1,...,n}. A local neighborhood of a vertex k in a planar drawing determines a cyclic permutation of the edges incident with k by considering the clockwise ordering in which they occur. Equivalently (looking at the edges' opposite endpoints), it determines a local rotation rho(k): a cyclic permutation of I(n) - k. A (global) rotation is a collection of local rotations rho(k), one for each vertex k in I(n).

It is well known that the rotations of K(n) are in a bijective correspondence with the embeddings of K(n) on oriented surfaces. The rotation arising from a planar drawing also determines which edges cross. Namely, edges ab,cd cross in the drawing if and only if the induced local rotations on the vertices {a,b,c,d} give a nonplanar embedding of that induced K(4).

The stated conjecture on the crossing number of K(n) asserts that the mininum number (over all planar drawings) of induced nonplanar K(4)'s satisfies the given lower bound. We generalize this to all rotations.

Conjecture: In any rotation of K(n), the number of induced nonplanar K(4)'s is at least (1/4) [n/2] [(n-1)/2] [(n-2)/2] [(n-3)/2] where [m] is the integer part of m.

Not every rotation corresponds to a drawing (see the related problem ``Drawing rotations in the plane''), so this conjecture is strictly stronger than the one on the crossing number of K(n). However, this conjecture has the advantage of reducing a geometric problem to a purely combinatorial one.

The problem arose from my attempts to prove the lower bound on the crossing number. It is supported by computer calculations. Namely, I wrote a program which started with a rotation of K(n) and using a local optimization technique (hill-climbing), randomly swapped edges in a local rotation whenever that swap did not increase the number of induced nonplanar K(4)'s. The resulting locally minimal rotations tended to resemble the patterns apparent in an optimal drawing of K(n). For small n this minimum was the conjectured upper bound. For larger n it was usually slightly larger. 

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA