Uniform-mass conjecture for the path optimization parameter

For an integer m2m\geq 2, let CmC_m be the cycle on mm edges, let E(Cm)E(C_m) be its edge set, and let ρ(m)\rho(m) be the path optimization parameter defined in the paper. Uniform-mass conjecture for ρ(m)\rho(m). For all m2m\geq 2, ρ(m)\rho(m) is achieved by the uniform distribution on E(Cm)E(C_m). In particular,

ρ(m)=8mm.\rho(m)=8\cdot m^{-m}.

This would imply the stated asymptotic formula for copies of P2m+1P_{2m+1} in planar graphs, with an O(nm+4/5)O(n^{m+4/5}) error term. The paper proves only the cases m=2m=2 and m=3m=3, and notes that its methods are insufficient for the conjectured O(nm)O(n^m) error term.

Sources & referencesView supporting material

Primary source

Christopher Cox and Ryan R. Martin, “Counting paths, cycles and blow-ups in planar graphs”, arXiv:2101.05911 (2022).

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.