Amended Pikhurko–Razborov conjecture on extremal clique-minimizing graphs

Fix r4r\ge4. For positive integers n,en,e with e(n2)e\le\binom{n}{2}, let tr1(n)t_{r-1}(n) be the number of edges in the balanced complete (r1)(r-1)-partite graph, let gr(n,e)g_r(n,e) be the minimum number of copies of KrK_r in an (n,e)(n,e)-graph, and let H1(n,e)\mathcal{H}_1^{\ast}(n,e) and H2(n,e)\mathcal{H}_2^{\ast}(n,e) be the two explicitly defined graph families in the source. Amended Pikhurko–Razborov conjecture. For every sufficiently large integer nn and every integer ee satisfying tr1(n)<e(n2)t_{r-1}(n)<e\le\binom{n}{2},

G:G is an (n,e)-graph with N(Kr,G)=gr(n,e)=H1(n,e)H2(n,e).\\{G:G\text{ is an }(n,e)\text{-graph with }N(K_r,G)=g_r(n,e)\\}=\mathcal{H}_1^{\ast}(n,e)\cup\mathcal{H}_2^{\ast}(n,e).

This is proposed after the original Pikhurko–Razborov strengthening is disproved; the proposition immediately preceding it verifies the asserted clique count for graphs in the two candidate families and shows that the second family is genuinely larger for infinitely many parameter pairs.

Sources & referencesView supporting material

Primary source

Xizhi Liu and Oleg Pikhurko, “A note on extremal constructions for the Erdős–Rademacher problem”, arXiv:2311.18753 (2024).

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.