Triangle extremality conjecture for the graph BT(3)\operatorname{BT}(3)

For k2k\geq 2, let BT~(k)\widetilde{\operatorname{BT}}(k) be obtained from T2(2k)T_2(2k) by deleting an edge and adjoining a new vertex to the two endpoints of that edge, and let

BT(k)=BT~(k)Ik+1.\operatorname{BT}(k)=\widetilde{\operatorname{BT}}(k)\vee I_{k+1}.

Let f3(Δ,ω)f_3(\Delta,\omega) be the supremum of the triangle density ρ3\rho_3 among graphs with maximum degree at most Δ\Delta and clique number at most ω\omega. Triangle extremality conjecture. For k=3k=3,

f3(2k+1,3)=ρ3(BT(k)).f_3(2k+1,3)=\rho_3(\operatorname{BT}(k)).

The preceding theorem proves that BT(k)\operatorname{BT}(k) beats the relevant Turán graph for k=2,3k=2,3; the conjecture asserts its optimality in the case k=3k=3, namely for parameters (Δ,ω)=(7,3)(\Delta,\omega)=(7,3).

Sources & referencesView supporting material

Primary source

R. Kirsch and A. J. Radcliffe, “Maximizing the density of K_t's in graphs of bounded degree and clique number”, arXiv:1712.07769 (2020).

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.