The maximum odd-cycle and path likelihood conjecture

Let m3m\geq 3, and let μ\mu be an edge probability mass. For a graph HH, write β(μ;H)\beta(\mu;H) for the total μ\mu-weight of copies of HH, and let CmC_m and Pm+1P_{m+1} denote the cycle on mm vertices and the path on m+1m+1 vertices, respectively.

Maximum likelihood conjecture. For every m3m\geq 3 and every edge probability mass μ\mu,

2mβ(μ;Cm)+β(μ;Pm+1)2mm1,2m\cdot\beta(\mu;C_m)+\beta(\mu;P_{m+1})\leq {2\over m^{m-1}},

with equality if and only if μ\mu is the uniform distribution on E(Cm)E(C_m).

The paper establishes a bound with constant 2.69472.6947 for m5m\geq 5, leaving the sharper constant 22 and its equality characterization as the main question. The conjecture is therefore open.

Sources & referencesView supporting material

Primary source

Emily Heath, Ryan R. Martin and Chris Wells, “The maximum number of odd cycles in a planar graph”, arXiv:2307.00116 (2023).

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.