Lovász–Simonovits conjecture on minimum clique counts

For integers n,e,rn,e,r, let gr(n,e)g_r(n,e) be the minimum number of copies of KrK_r in an nn-vertex graph with ee edges. Let H(n,e)=H1(n,e)H2(n,e)\mathcal{H}(n,e)=\mathcal{H}_1(n,e)\cup\mathcal{H}_2(n,e) be the prescribed family of multipartite (n,e)(n,e)-graphs, and define

hr(n,e):=min{Kr(H):HH(n,e)}.h_r(n,e):=\min\{K_r(H):H\in\mathcal{H}(n,e)\}.

Lovász–Simonovits conjecture. For every integer r3r\geq 3, there exists n0=n0(r)>0n_0=n_0(r)>0 such that

gr(n,e)=hr(n,e)g_r(n,e)=h_r(n,e)

for all positive integers nn0n\geq n_0 and e(n2)e\leq \binom{n}{2}. This conjecture extends the Lovász–Simonovits theorem from a neighbourhood of the relevant Turán densities to the full range of edge counts. The source reports partial cases, including the theorem proved there for triangles away from the complete-graph density, but does not state a complete resolution.

Sources & referencesView supporting material

Primary source

Hong Liu, Oleg Pikhurko and Katherine Staden, “The exact minimum number of triangles in graphs of given order and size”, arXiv:1712.00633 (2020).

Additional references

2 papers in this index state this conjecture (2012–2017). The statement above is taken from the most recent of them; the others are arXiv:1204.2846.

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.