Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$$

(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)?

share|improve this question
    
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? –  Gil Kalai Apr 8 '11 at 11:00
    
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. –  Thomas Kalinowski Apr 9 '11 at 10:12
    
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. –  Thomas Kalinowski Apr 9 '11 at 10:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.