The C3ℓ+1C_{3\ell+1}-free clique extremal conjecture

At least 3 years old · documented by

Let k≥2k\geq 2 and let nn be sufficiently large. Let GG be an nn-vertex graph containing no cycle C3ℓ+1C_{3\ell+1} for any integer ℓ≥k\ell\geq k. For r≥2r\geq 2, write Nr(G)N_r(G) for the number of cliques of size rr in GG. Clique extremal conjecture.

Nr(G)≤n−13k−1(3kr).N_r(G)\leq \frac{n-1}{3k-1}\binom{3k}{r}.

Equality holds if and only if n−1n-1 is divisible by 3k−13k-1 and GG is a connected nn-vertex graph consisting of n−13k−1\frac{n-1}{3k-1} maximal 22-connected blocks, each isomorphic to K3kK_{3k}. This conjecture asks whether the sharp block-decomposition phenomenon proved in the paper for sufficiently restricted odd circumferences extends to the family of forbidden cycle lengths congruent to 11 modulo 33; its resolution is not supplied here.

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.