most recent 30 from http://mathoverflow.net 2013-05-24T14:05:26Z http://mathoverflow.net/feeds/question/54038 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54038/graphs-with-many-triangles-but-few-complete-graphs-on-4-vertices Thomas Kalinowski 2011-02-01T23:50:27Z 2011-02-02T01:55:30Z

<p>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$. </p> <p>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.</p> <p>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$?</p> <h2>Background/Motivation</h2> <p>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.</p>

http://mathoverflow.net/questions/54038/graphs-with-many-triangles-but-few-complete-graphs-on-4-vertices/54049#54049 David Eppstein 2011-02-02T01:49:45Z 2011-02-02T01:55:30Z

<p>Your statement may be true for large enough values of $c$, but it is not true for all constants $c>0$.</p> <p>Specifically, for small enough values of $c$, form a counterexample $G$ consisting of the disjoint union of two subgraphs:</p> <ul> <li><p>$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</p></li> <li><p>$K_{n\sqrt{12},n\sqrt{12}}$ together with a perfect matching in each component of its bipartition.</p></li> </ul> <p>(Obviously these numbers of vertices are not all going to be integers, so round them.)</p> <p>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$.</p>