Exact extremal-graph conjecture for the Lovász–Simonovits triangle problem

From papers

Let g3(n,e)g_3(n,e) be the minimum number of triangles in an (n,e)(n,e)-graph. Let H0(n,e)\mathcal{H}_0^*(n,e) and H2(n,e)\mathcal{H}_2^*(n,e) denote the subclasses of H0(n,e)\mathcal{H}_0(n,e) and H2(n,e)\mathcal{H}_2(n,e) attaining the prescribed minimum h(n,e)h^*(n,e). Exact extremal-graph conjecture. For all positive integers nn and e(n2)e\leq\binom{n}{2}, an (n,e)(n,e)-graph GG satisfies

K3(G)=g3(n,e)K_3(G)=g_3(n,e)

if and only if

GH0(n,e)H2(n,e).G\in\mathcal{H}_0^*(n,e)\cup\mathcal{H}_2^*(n,e).

This strengthens the triangle case of the Lovász–Simonovits conjecture by specifying every extremal graph, not only the minimum number of triangles. The source presents it as a belief and proves the equality of the minimum values asymptotically when the edge density is bounded away from 11, but does not establish the claimed classification for all n,en,e.

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

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

Solutions 0

No solutions have been posted yet.