Lonely runner conjecture: Difference between revisions

Revision as of 07:32, 25 May 2022

Revision as of 16:35, 26 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 {{mvar|n}}-dimensional space (<math>n\geq2</math>) of side length <math>s</math>. Place a centered copy of <math>C</math> at every point with positive [[half-integer]] coordinates. A ray from the origin, intonot thelying positive [[orthant]] (in otherone words,of directedthe positivelycoordinate in every dimension)hyperplanes, may either miss all of the copies of <math>C</math>, in which case there is a (infinitesimal) gap, 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>s<(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</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 {{mvar|k}}-''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. Taking <math>k=|D|+1</math>, the lonely runner conjecture implies <math>G</math> admits a proper {{mvar|k}}-regular coloring (i.e., each node is colored differently than its adjacencies) for some step value.{{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 the example <math>D=\{2\}</math>. (<math>k</math> is known as the ''regular chromatic number'' of <math>D</math>.)