Cox and Martin's weighted optimization conjecture for even-length paths

Let UU be a finite set, and let μ\mu be a probability measure on the edges of the complete graph on UU, so that μ(uv)0\mu(uv)\ge 0 and

{u,v}(U2)μ(uv)=1.\sum_{\{u,v\}\in\binom{U}{2}}\mu(uv)=1.

For uUu\in U, define the weighted degree by

μ(u)=vU{u}μ(uv).\mu(u)=\sum_{v\in U\setminus\{u\}}\mu(uv).

For every integer 2\ell\ge 2, set

ρ(μ;)=(u1,,u)Uu1,,u pairwise distinctμ(u1)(i=11μ(uiui+1))μ(u),\rho(\mu;\ell)=\sum_{\substack{(u_1,\ldots,u_\ell)\in U^\ell\\ u_1,\ldots,u_\ell\ \operatorname{pairwise\ distinct}}}\mu(u_1)\left(\prod_{i=1}^{\ell-1}\mu(u_i u_{i+1})\right)\mu(u_\ell),

and define

ρ()=supU,μρ(μ;),\rho(\ell)=\sup_{U,\mu}\rho(\mu;\ell),

where the supremum is over all finite sets UU and all such probability measures. Cox and Martin's conjecture. For every integer 2\ell\ge 2,

ρ()=8.\rho(\ell)=\frac{8}{\ell^\ell}.

This weighted optimization parameter controls the leading term in the upper bound for the number of even-length paths in planar graphs. The source attributes the conjecture to Cox and Martin and does not provide evidence of its resolution, so its general status remains open.

Sources & referencesView supporting material

Primary source

Zhen Liu and Chuanshu Wu, “The maximum number of paths of even length in a planar graph”, arXiv:2607.27284 (2026).

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.