Degree 3 dilation conjecture for the infinite square lattice

Let Λ\Lambda be the infinite square lattice, and let δ0(Λ,3)\delta_0(\Lambda,3) denote its minimum stretch factor among degree-33 spanners. Degree 3 dilation conjecture.

δ0(Λ,3)=(3+22)51/2=2.6065\delta_0(\Lambda,3) =(3+2\sqrt2) \, 5^{-1/2} = 2.6065\ldots

The paper has established the matching upper bound and conjectures that it is optimal; whether the upper bound can be improved is therefore left open.

Sources & referencesView supporting material

Primary source

Adrian Dumitrescu and Anirban Ghosh, “Lattice spanners of low degree”, arXiv:1602.04381 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.