Graphs with many triangles but few complete graphs on 4 vertices

Question

Let $G$ be a graph on $n$ vertices with $an^2$ edges containing at most $an^2/2$ copies of $K_4$. If there are cubically many triangles, say $cn^3$, then there is at least one edge that is not contained in any $K_4$.

Note that it is necessary to require that the number of $K_4$'s is significantly smaller than the number of edges. Otherwise we could take a complete tripartite graph and add an edge in each of the three colour classes.

So far my proof attempts using averaging arguments failed. Maybe there are counterexamples? If so, does it help to assume in addition that $a$ is bigger than $1/4$?

Background/Motivation

If the statement is true it implies that asymptotically $5n^2/16$ is the smallest size of an antichain in $2^{[n]}$ that is maximal among the antichains containing only 2-sets and 4-sets: basically, the $K_4$'s and the nonedges in the graph are the 4-sets and the 2-sets in the antichain.

Answer 1

Your statement may be true for large enough values of $c$, but it is not true for all constants $c>0$.

Specifically, for small enough values of $c$, form a counterexample $G$ consisting of the disjoint union of two subgraphs:

• $K_{n\sqrt 2,n\sqrt 2,n\sqrt 2}$ together with one extra edge in each component of the tripartition as in your example

• $K_{n\sqrt{12},n\sqrt{12}}$ together with a perfect matching in each component of its bipartition.

(Obviously these numbers of vertices are not all going to be integers, so round them.)

Then there are approximately $18n^2$ edges ($6n^2$ in the first subgraph and $12n^2$ in the second), approximately $9n^2$ $K_4$'s ($6n^2$ in the first subgraph and $3n^2$ in the second), approximately $(3\sqrt 2 + 4\sqrt 3)n$ vertices, and approximately $(2\sqrt 2)n^3$ triangles (mostly in the first subgraph). So this example has only half as many $K_4$'s as edges, as you ask, and every edge belongs to at least one $K_4$, with $c\approx\frac{2\sqrt 2}{(3\sqrt 2 + 4\sqrt 3)^3}\approx 0.00203$.