Glasnik Matematicki, Vol. 46, No.1 (2011), 25-30.

THE LONELY RUNNER PROBLEM FOR MANY RUNNERS

Arturas Dubickas

Abstract.   The lonely runner conjecture asserts that for any positive integer n and any positive numbers v₁ < ... < v_n there exists a positive number t such that ||v_i t|| ≥ 1/(n+1) for every i=1, ...,n. We verify this conjecture for n ≥ 16342 under assumption that the speeds of the runners satisfy v_j+1/v_j ≥ 1+33 log n/n for j=1, ...,n-1.

2000 Mathematics Subject Classification.   11J13, 11J25, 11J71.

Key words and phrases.   Lonely runner conjecture, Diophantine approximation, Lovász local lemma.

DOI: 10.3336/gm.46.1.01

References:

1. N. Alon and J. Spencer, The probabilistic method, Wiley-Interscience, New York, 2000, 2nd ed.
   MathSciNet     CrossRef

2. J. Barajas and O. Serra, The lonely runner with seven runners, Electron. J. Combin. 15 (2008), R48, 18 pp.
   MathSciNet     CrossRef

3. J. Barajas and O. Serra, On the chromatic number of circulant graphs, Discrete Math. 309 (2009), 5687-5696.
   MathSciNet     CrossRef

4. U. Betke and J.M. Wills, Untere Schranken für zwei diophantische Approximations-Funktionen, Monatsh. Math. 76 (1972), 214-217.
   MathSciNet     CrossRef

5. W. Bienia, L. Goddyn, P. Gvozdjak, A. Sebő and M. Tarsi, Flows, view obstructions and the lonely runner, J. Combin. Theory Ser. B 72 (1998), 1-9.
   MathSciNet     CrossRef

6. T. Bohman, R. Holzman and D. Kleitman, Six lonely runners, Electron. J. Combin. 8(2) (2001), R3, 49 pp.
   MathSciNet     CrossRef

7. T. W. Cusick, View-obstruction problems in n-dimensional geometry, J. Combin. Theory Ser. A 16 (1974), 1-11.
   MathSciNet     CrossRef

8. T. W. Cusick and C. Pomerance, View-obstruction problems III, J. Number Theory 19 (1984), 131-139.
   MathSciNet     CrossRef

9. A. Dubickas, An approximation by lacunary sequence of vectors, Combin. Probab. Comput. 17 (2008), 339-345.
   MathSciNet     CrossRef

10. A. Dubickas, An approximation property of lacunary sequences, Israel J. Math. 170 (2009), 95-111.
    MathSciNet     CrossRef

11. P. Erdős and L. Lovász, Problems and results of 3-chromatic hypergraphs and some related questions, in: A. Hajnal et al., eds. Infinite and finite sets (dedic. to P. Erdős on his 60th birthday), Vol. II. North-Holland, Amsterdam, 1975, pp. 609-627.
    MathSciNet    

12. L. Goddyn and E. B. Wong, Tight instances of the lonely runner, Integers 6 (2006), #A38, 14 pp.
    MathSciNet    

13. D. D. F. Liu, From rainbow to the lonely runner: a survey on coloring parameters of distance graphs, Taiwanese J. Math. 12 (2008), 851-871.
    MathSciNet    

14. R. K. Pandey, A note on the lonely runner conjecture, J. Integer Seq. 12 (2009), Article 09.4.6, 4 pp.
    MathSciNet    

15. J. Renault, View-obstruction: a shorter proof for 6 lonely runners, Discrete Math. 287 (2004), 93-101.
    MathSciNet     CrossRef

16. I. Ruzsa, Zs. Tuza and M. Voigt, Distance graphs with finite chromatic number, J. Combin. Theory Ser. B 85 (2002), 181-187.
    MathSciNet     CrossRef

17. J. M. Wills, Zwei Sätze über inhomogene diophantische Approximation von Irrationalzahlen, Monatsh. Math. 71 (1967), 263-269.
    MathSciNet     CrossRef