This is a follow-up to Graphs with many triangles but few complete graphs on 4 vertices

I'm looking for an upper bound for the difference between the number of edges and the number of 4-cliques in a graph on $n$ vertices subject to the condition that every edge is contained in a 4-clique. The best construction I know gives

$$\text{#edges} - \text{#4-cliques} = \frac{(3+o(1))n^2}{16}\approx 0.1875n^2$$

(take a complete bipartite graph with equal parts and add a matching in each part) and my guess is that this is best possible. But annoyingly, I can only prove

$$\text{#edges} - \text{#4-cliques} \leqslant \left(\frac{2(39+\sqrt{21})}{375}+o(1)\right)n^2\approx 0.232441n^2,$$

and even this weak bound requires a bit of work (and the removal lemma). Note that the $3/16$-result would follow (at least asymptotically) if one could prove that the number of triangles in an extremal graph is $o(n^3)$, which was the motivation of my previous question.

  • Has this type of problem been considered somewhere in the literature?

  • Do I miss something obvious, either in terms of a better construction or a better upper bound?

  • Are there reasons indicating that improving the bound is hard (besides me spending quite some time on trying)?

  • $\begingroup$ Dear Kali, when you say "subject to the condition that every edge is contained in a 4-clique" do you mean that every edge is contained in precisely one 4-clique? $\endgroup$ – Gil Kalai Apr 8 '11 at 11:00
  • $\begingroup$ Dear Gil, I mean "at least one 4-clique". If every edge is in exactly one 4-clique, there can be only $o(n^2)$ edges, since the removal lemma tells us that we can destroy all 4-cliques by deleting $o(n^2)$ edges. So this cannot be optimal. In my example: For $n=4k$, let $V=A\cup B$ be the vertex set with $A=\{a_1,\ldots,a_{2k}\}$ and $B=\{b_1,\ldots,b_{2k}\}$. The edge set contains all pairs $a_ib_j$, plus edges $a_ia_{k+i}$ and $b_ib_{k+i}$ for $i=1,\ldots,k$. Here an edge between $A$ and $B$ is contained in exactly one 4-clique, while the edges inside $A$ and $B$ are in $n/4$ 4-cliques. $\endgroup$ – Thomas Kalinowski Apr 9 '11 at 10:12
  • $\begingroup$ To apply the removal lemma argument above we need that the total number of 4-cliques is $o(n^4)$. But since we want to maximize #edges minus #4-cliques we may even assume that there are only $O(n^2)$ 4-cliques. $\endgroup$ – Thomas Kalinowski Apr 9 '11 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.