The extremal-family conjecture for cliques in graphs with bounded minimum degree

Let nn and β\beta be such that the family of graphs G(n,β)\mathcal{G}(n,\beta) is defined, and let (n,β)(n,\beta) be feasible when G[V0]G[V_0] is triangle-free for GG(n,β)G\in\mathcal{G}(n,\beta). Write δ=(1β)n\delta=(1-\beta)n, let pp be the parameter appearing in the definition of G(n,β)\mathcal{G}(n,\beta), and let gr(β)g_r(\beta) denote the associated clique-density expression. The quantity kr(n,δ)k_r(n,\delta) is the minimum possible number of rr-cliques in an nn-vertex graph with minimum degree at least δ\delta. The extremal-family conjecture. Let nn and δ\delta be positive integers. Then

kr(n,δ)gr(β)nr,k_r(n,\delta)\ge g_r(\beta)n^r,

where δ=(1β)n\delta=(1-\beta)n and r3r\ge3. Moreover, for 3rp+1=β13\le r\le p+1=\lceil\beta^{-1}\rceil, equality holds if and only if (n,β)(n,\beta) is feasible and the extremal graphs are members of G(n,β)\mathcal{G}(n,\beta). This extends the known Turán-theoretic cases; the conjecture is true when p=1p=1 or r>p+1r>p+1, and also when β=1/(p+1)\beta=1/(p+1) with (p+1)n(p+1)\mid n, while the stated range in general remains open.

Sources & referencesView supporting material

Primary source

Allan Lo, “Cliques in graphs with bounded minimum degree”, arXiv:1009.5296 (2010).

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.