Lonely runner conjecture: Difference between revisions

Revision as of 19:04, 22 May 2022

Revision as of 19:09, 22 May 2022

Line 16:

[[File:View-obstruction problem for squares.svg|thumb|alt=A series of red squares and a green line, with slope 2, narrowly hitting the squares.|Squares of side length 1/3 placed at every half-integer coordinate in the positive quadrant obstruct any ray from the origin in that direction. Any smaller side length will leave small gaps.]]

Suppose <math>C</math> is a ''{{mvar|n''}}-[[hypercube]] in <math>n</math>-dimensional space (<math>n\geq2</math>). Infinitely many copies of <math>C</math>, all scaled by some factor <math>\alpha</math>, are placed at points at nonnegative half-integer coordinates. A ray from the origin into the positive [[orthant]] (in other words, directed positively in every dimension) may either miss all of the copies of <math>C</math> or hit at least one copy. {{harvtxt|Cusick|1973}} made an independent formulation of the lonely runner conjecture in this context; the conjecture implies that there are gaps if and only if <math>\alpha<(n-1)/(n+1)</math>.{{Sfn|Cusick|1974|p=1}} For example, squares any smaller than <math>1/3</math> in side length will leave gaps, as shown.

In [[graph theory]], a distance graph <math>G</math> on the set of integers, and using some finite set <math>D</math> of positive integer distances, has an edge between <math>x,y\in\mathbb{Z}</math> if and only if <math>|x-y|\in D</math>. For example, if <math>D=\{2\}</math>, every consecutive pair of even integers, and of odd integers, is adjacent, all together forming two [[connected component (graph theory)|connected component]]s. A <math>{{mvar|k</math>}}-''regular coloring'' of the integers with step <math>\lambda\in\mathbb{R}</math> assigns to each integer <math>n</math> one of <math>k</math> colors based on the [[Modular arithmetic#Residue systems|residue]] of <math>\lfloor \lambda n\rfloor</math>modulo <math>k</math>. For example, if <math>\lambda=0.5</math>, the coloring repeats every <math>2k</math> integers and each pair of integers <math>2m, 2m+1</math> are the same color. The lonely runner conjecture implies that the minimum <math>k</math> for which <math>G</math> admits a proper <math>{{mvar|k</math>}}-regular coloring (i.e., each node is colored differently than its adjacencies) for ''some'' step value is at most <math>|D|+1</math>.{{sfn|Barajas|Serra|2009|p=5688}} For example, <math>(k,\lambda)=(2,0.5)</math> generates a proper coloring on the distance graph generated by <math>D</math>. (<math>k</math> is known as the ''regular chromatic number'' of <math>D</math>.)

Given a [[directed graph]] <math>G</math>, a [[nowhere-zero flow]] on <math>G</math> associates a positive value <math>f(e)</math> to each edge <math>e</math>, such that the flow outward from each node is equal to the flow inward. Suppose <math>f</math> is further restricted to positive integers. The lonely runner conjecture implies that, if <math>f</math> attains at most <math>k</math> different values, then <math>G</math> has a nowhere-zero flow with values only in <math>\{1,2,\ldots,k\}</math>. This result was proven for <math>k\geq 5</math> with separate methods, and because the smaller cases of the lonely runner conjecture are settled, the full theorem is proven.{{sfn|Bienia|Goddyn|Gvozdjak|Sebő|1998}}