Six lonely runners. (English) Zbl 1011.11048

Bohman, Tom; Holzman, Ron; Kleitman, Dan

Electron. J. Comb. 8, No. 2, Research Paper R3, 49 p. (2001); printed version J. Comb. 8, No. 2 (2001).

Consider the problem of lonely runners wherein \(n\) runners are running on a circular track of circumference 1. All the runners start at the same time and place. It is note a race; runner \(i\) runs at a constant speed \(\{v_it\}\) where \(\{x\}\) is the fractional part of \(x\). All the speeds are different. A runner is said to be lonely if the smallest distance along the track to another runner is at least \(1/n\). The question is whether every runner gets lonely? This question originally arose in the context of Diophantine approximations (Betke and Wills) and in the study of so-called view obstruction problems by Cusick. It is known that if there are less than or equal to five runners on the track then every runner gets lonely; see W. Bienia et al. [J. Comb. Theory, Ser. B 72, 1-9 (1998; Zbl 0910.05064)]. They have used this result to prove a theorem on flows in graphs related to Seymour’s six flow theorem. It was pointed out that a proof of the lonely runner conjecture for higher values of \(n\) would have analogous consequences regarding flows in regular matroids.
The problem has been reformulated by Wills and Cusick as: For any collection \(v_1,\dots, v_{n-1}\) in \(\mathbb{R}^+\) there exists \(t\) in \(\mathbb{R}^+\) such that \(\{v_it\}\in (1/n,n-1/n)\) for \(i=1,2,\dots, n-1\). In this paper, the conjecture is proved for \(n=6\). The proof for \(n\leq 5\) relies on number theoretic analysis of the speeds focusing on how the runners cover discrete sets of times, whereas the proof given here takes advantage of the fact that runners must cover intervals of times. A third formulation of the problem is given as a covering problem. The same method may be used to attack the problem for \(n>6\), but the amount of work involved makes this approach impractical.

Reviewer: Ranjeet Sehmi (Chandigarh)

MSC:

11J25	Diophantine inequalities
52A37	Other problems of combinatorial convexity
52C07	Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)

Keywords:

covering

Citations:

Zbl 0910.05064