The asymptotic upper-bound conjecture for edge diameter

Let ht(Δ)h_t(\Delta) be the smallest integer such that every graph with ht(Δ)h_t(\Delta) edges and maximum degree at most Δ\Delta contains two edges whose distance is at least tt; equivalently, ht(Δ)1h_t(\Delta)-1 is the largest number of edges in a graph of maximum degree at most Δ\Delta whose line graph has diameter at most tt. The parameter tt is fixed.

Asymptotic upper-bound conjecture. For t2t\ne 2 and any ε>0\varepsilon>0,

ht(Δ)(1+ε)Δth_t(\Delta)\leq (1+\varepsilon)\Delta^t

for all sufficiently large Δ\Delta.

This is the complementary challenge to the asymptotic lower bound and would identify the asymptotic value of ht(Δ)h_t(\Delta) up to a factor tending to one. The paper states that the conjecture remains open for the relevant values of tt, while the case t=2t=2 is excluded because its known leading constant is 5/45/4 rather than 11.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos and Ross J. Kang, “Maximising line subgraphs of diameter at most t”, arXiv:2103.11898 (2021).

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.