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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.