The prime-cycle clique extremal conjecture

About 4 years old · traced to

Let pp be a prime number, and let C≥pprime\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,C≥pprime)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 C≥pprime\mathcal C_{\geq p}^{\mathrm{prime}}. Prime-cycle clique extremal conjecture.

ex(n,Kr,C≥pprime)≤n−1p−2(p−1r).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 n−1n-1 is divisible by p−2p-2 and the extremal graph is a connected nn-vertex graph consisting of n−1p−2\frac{n-1}{p-2} maximal 22-connected blocks, each isomorphic to Kp−1K_{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.

References

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).

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.