Magányosfutó-sejtés

A magányosfutó-sejtés (lonely runner conjecture, LRC) J. M. Wills több mint ötvenéves, számelméleti, közelebbről a diofantikus approximációval kapcsolatos sejtése. Folyományai a matematika több területén előfordulnak, köztük találhatók takarási problémák,^[1] illetve a távolsággráfok és cirkuláns (irányítatlan, ciklikus csoportot tartalmazó, csúcstranzitív gráfok) kromatikus számának meghatározása is.^[2] A sejtés szemléletes nevét L. Goddyntól kapta 1998-ban.^[3]

Példa a magányosfutó-sejtésre 6 futóval

A sejtés

Vegyünk egységnyi hosszú körpályát, rajta k futóval. A t = 0 időpillanatban elindul az összes futó, azonos kiindulási pontból, állandó, de páronként különböző sebességgel. Egy futót t időpillanatban „magányosnak” tekintünk akkor, ha legalább 1 / k távolságra van az összes többi futótól az adott t pillanatban. A magányosfutó-sejtés azt állítja, hogy minden futó magányos valamilyen időpillanatban. A probléma egy célszerű átfogalmazása felteszi, hogy a futók sebessége egész szám, nincs közös prímosztójuk és a magányosnak választott futó sebessége zérus. A sejtés ekkor úgy szól, hogy bármely k − 1 darab, 1 legnagyobb közös osztójú pozitív egész szám által alkotott D halmazt tekintve,

${\displaystyle \exists t\in \mathbb {R} \quad \forall d\in D\quad ||td||\geq {\frac {1}{k}},}$

ahol ||x|| az x valós szám távolságát jelöli a legközelebbi egésztől. A sejtéssel ekvivalens feladatok között van az 1971-ben megfogalmazott takarási probléma (view obstruction problem^[4]) is.

Alacsony k értékekre a feladat viszonylag egyszerű, de a futók számának növekedésével rendkívül bonyolulttá válik.

Eddigi eredmények

k	bizonyítás éve	szerzője	jegyzet
1	-	-	triviális: t = 0; bármely t
2	-	-	triviális: t = 1 / (2 · (v1−v0))
3	-	-	Bármely bizonyítás k>3-ra bizonyítja a k=3 esetet is
4	1972	Betke és Wills;[5] Cusick[6]	-
5	1984	Cusick és Pomerance;[7] Bienia et al.[3]	-
6	2001	Bohman, Holzman, Kleitman;[8] Renault[9]	-
7	2008	Barajas és Serra[2]	-

Dubickas 2011-ben megmutatta,^[10] hogy elegendően nagy számú futó esetén, melyek sebességei ${\displaystyle v_{1}<v_{2}<\dots <v_{k}}$, a magányosfutó-sejtés igaz, amennyiben ${\displaystyle {\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {33\log(k)}{k}}}$.

Jegyzetek

1. T. W. Cusick (1973). „View-Obstruction problems”. Aequationes Math. 9 (2–3), 165–170. o. DOI:10.1007/BF01832623.
2. J. Barajas and O. Serra (2008). „The lonely runner with seven runners”. The Electronic Journal of Combinatorics 15, R48. o.
3. W. Bienia et al. (1998). „Flows, view obstructions, and the lonely runner problem”. Journal of combinatorial theory series B 72, 1–9. o. DOI:10.1006/jctb.1997.1770.
4. T.W. Cusick: View-obstruction problems in n-dimensional geometry
5. (1972) „Untere Schranken für zwei diophantische Approximations-Funktionen”. Monatshefte für Mathematik 76 (3), 214. o. DOI:10.1007/BF01322924.
6. T. W. Cusick (1974). „View-obstruction problems in n-dimensional geometry”. Journal of Combinatorial Theory, Series A 16 (1), 1–11. o. DOI:10.1016/0097-3165(74)90066-1.
7. (1984) „View-obstruction problems, III”. Journal of Number Theory 19 (2), 131–139. o. DOI:10.1016/0022-314X(84)90097-0.
9. (2004) „View-obstruction: A shorter proof for 6 lonely runners”. Discrete Mathematics 287, 93–101. o. DOI:10.1016/j.disc.2004.06.008.
10. (2011) „The lonely runner problem for many runners”. Glasnik Matematicki 46, 25–30. o. DOI:10.3336/gm.46.1.05.

További információk

• article in the Open Problem Garden
• Clayton Barnes II: The Lonely Runner Conjecture – A detailed survey of the Lonely Runner Conjecture and its connection between Diophantine approximation and View-obstruction problems
• Richard Green: The lonely runner conjecture

Kapcsolódó szócikkek

• A hosszútávfutó magányossága