The maximum odd-cycle and path likelihood conjecture

At least 2 years old · documented by

Let m≥3m\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 m≥3m\geq 3 and every edge probability mass μ\mu,

2m⋅β(μ;Cm)+β(μ;Pm+1)≤2mm−1,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 m≥5m\geq 5, leaving the sharper constant 22 and its equality characterization as the main question. The conjecture is therefore open.

References

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.