1
$\begingroup$

Consider all graphs with E many edges. The question is to find the maximum number of triangles such a graph can have. The answer is $O(E^{1.5})$ and the maximum occurs with it’s a clique.

Now my question is what happens if the size of maximum clique is fixed, i.e., I cannot have a clique of full size to maximize triangles. Then, under this constraint, how does the optimizer graph (one with maximum triangles) look like?

The claim I have is that the graph should be a union of multiple cliques of appropriate size. But I cannot prove that the maximizer is Union of cliques of appropriate sizes who are independent of each other.

$\endgroup$
  • $\begingroup$ What exactly is 'this'? What do you mean precisely by 'a uniform multiple clique of appropriate size'? Until you make this precise, there isn't much hope of proving this. $\endgroup$ – Servaes Feb 11 at 8:15
  • $\begingroup$ The graph is Union of multiple cliques of appropriate size which are independent to each other. I don’t know if there is a name for such graphs. Thanks I’m editing the question. $\endgroup$ – pulpfictional Feb 11 at 8:17
  • $\begingroup$ Your interpretation of the claim is obviously false. Consider the case of 12 edges, maximum clique size 3. A union of independent 3-cliques gets us four triangles. An octahedron gets us eight triangles. $\endgroup$ – jmerry Feb 11 at 8:36
  • 1
    $\begingroup$ In general, it seems reasonable that the $K_r$-free graph with $m$ edges and the most triangles will be approximately a complete balanced $(r-1)$-partite graph. $\endgroup$ – Misha Lavrov Feb 11 at 23:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.