The prime-cycle clique extremal conjecture

From papers

Let pp be a prime number, and let Cpprime\mathcal C_{\geq p}^{\mathrm{prime}} be the family of all cycles of length at least pp. For integers nn and rr satisfying r<pr<p, let ex(n,Kr,Cpprime)ex(n,K_r,\mathcal C_{\geq p}^{\mathrm{prime}}) denote the maximum number of copies of KrK_r in an nn-vertex graph containing no member of Cpprime\mathcal C_{\geq p}^{\mathrm{prime}}. Prime-cycle clique extremal conjecture.

ex(n,Kr,Cpprime)n1p2(p1r).ex(n,K_r,\mathcal C_{\geq p}^{\mathrm{prime}})\leq \frac{n-1}{p-2}\binom{p-1}{r}.

Equality holds if and only if n1n-1 is divisible by p2p-2 and the extremal graph is a connected nn-vertex graph consisting of n1p2\frac{n-1}{p-2} maximal 22-connected blocks, each isomorphic to Kp1K_{p-1}. This proposes a prime-parameter analogue of the preceding clique bound for graphs with forbidden long cycles; no resolution is supplied in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Zequn Lv, Ervin Győri, Zhen He, Nika Salia, Chuanqi Xiao and Xiutao Zhu, “The maximum number of cliques in graphs with bounded odd circumference”, arXiv:2212.01989 (2022).

Solutions 0

No solutions have been posted yet.