Triangle-covering conjecture for graphs above the Mantel threshold

Let GG be an nn-vertex graph, let T(G)T(G) denote its number of triangles, and let τ(G)\tau_{\triangle}(G) be the minimum size of a vertex set meeting every triangle. For integers 0<t<s0<t<s and sufficiently large nn, consider the graph Kn/2,n/2s,tK_{\lceil n/2\rceil,\lfloor n/2\rfloor}^{s,t} obtained from the complete bipartite graph by adding s1s-1 pairwise disjoint edges in the first part and one edge in the second part, then deleting sts-t edges incident with one endpoint of that second-part edge. Triangle-covering conjecture. If GG has nn vertices and n24+t\left\lfloor\frac{n^2}{4}\right\rfloor+t edges, satisfies τ(G)s\tau_{\triangle}(G)\geq s, and nn(t,s)n\geq n(t,s) is large, then GG contains at least as many triangles as Kn/2,n/2s,tK_{\lceil n/2\rceil,\lfloor n/2\rfloor}^{s,t}, namely

(s1)n2+n22(st).(s-1)\left\lfloor\frac n2\right\rfloor+\left\lceil\frac n2\right\rceil-2(s-t).

The construction shows the proposed bound is attainable for sufficiently large nn; the lower-bound assertion itself is left as a conjecture.

Sources & referencesView supporting material

Primary source

Chuanqi Xiao and Gyula O. H. Katona, “The number of triangles is more when they have no common vertex”, arXiv:2003.04450 (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.