The conjecture that all odd cycles are strongly common

Let WW be a graphon, meaning a symmetric measurable function W:[0,1]2[0,1]W:[0,1]^2\to[0,1], and let t(H,W)t(H,W) denote the homomorphism density of a graph HH in WW. A graph HH is strongly common if

t(H,W)+t(H,1W)t(K2,W)e(H)+t(K2,1W)e(H)t(H,W)+t(H,1-W)\geq t(K_2,W)^{e(H)}+t(K_2,1-W)^{e(H)}

for every graphon WW. Odd-cycle strong-commonness conjecture. Every odd cycle is strongly common. Strong commonness implies commonness, and the claim is motivated by the known cases of the triangle and the 55-cycle; the general assertion remains open.

Sources & referencesView supporting material

Primary source

Natalie Behague, Natasha Morrison and Jonathan A. Noel, “Off-Diagonal Commonality of Graphs via Entropy”, arXiv:2307.03788 (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.