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

THE LONELY RUNNER PROBLEM FOR MANY RUNNERS

Arturas Dubickas

Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius LT-03225, Lithuania
e-mail: arturas.dubickas@mif.vu.lt


Abstract.   The lonely runner conjecture asserts that for any positive integer n and any positive numbers v1 < ... < vn there exists a positive number t such that ||vi 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 vj+1/vj ≥ 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.


Full text (PDF) (access from subscribing institutions only)

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

Glasnik Matematicki Home Page