# Number of edges required to guarantee $K_3$ as subgraph

I am trying to solve a given problem: Find an algorithm to determine if a graph has a clique of size 3 in $O(n^{2.81})$ steps. The hint given is that $2.81 > \log 7$. In order to solve this I came up with a conjecture: if $m > n^{\log 7}$ then the graph has $K_3$ as a subgraph. This will easily solve the problem if the conjecture is true.

I am trying to argue by contradiction: Let $m > n^{\log 7}$ and assume there does not exist a $K_3$ subgraph. Then for any set of three vertices there are exactly 7 choices for how to connect them. However, I am stuck as to how to progress from here.

Does anyone see a way to prove this, or if the conjecture is even true. I'm also interested to see if the conjecture can be extended, i.e. if $m > n^{\log 2^k -1})$ does there exist a $K_k$ subgraph?

• You need $n^2/4 + 1$ edges to guarantee a triangle (see en.wikipedia.org/wiki/Turán's_theorem). Try to use matrix multiplication instead. Mar 12, 2014 at 21:27
• @Louis The division should be floored or ceiled I guess
– mrk
Mar 12, 2014 at 22:12
• What is $m$? The number of edges? If $n$ is the number of vertices, you can't have a graph with $n^{\log 7}$ edges, since that exceeds the maximum possible number of edges, which is $\binom{n}{2}$. Even putting that aside, your conjecture wouldn't be enough. Sure, $\lfloor n^2/4\rfloor+1$ edges guarantees a triangle (Mantel's theorem, generalized by Turán) but a triangle plus a million isolated vertices contains a triangle and it has waaaay fewer than 250,000,000,001 edges. Mar 12, 2014 at 22:13
• @DavidRicherby Your first point is quite correct. I incorrectly thought that if I could assume the number of vertices iwas less than $n^\log 7$ then I could merely run through all edges and reach the conclusion necessary. This is, now that I think about it for more than a few seconds, quite ludicrous. However, your second point misses the point of what I was trying to accomplish with the conjecture. Your example does indeed have far more vertices than edges, but I thought would not have to worry about vertices if I could assume the number of edges was comparatively small, does this make sense? Mar 17, 2014 at 21:25

Hint: Matrix multiplication runs in time $O(n^{2.71})$. A relevant matrix is the adjacency matrix of the graph.
Actually, this has been improved several times in the past very. Recently, Le Gall improved this to time $O(n^{2.3728639})$. It is conjectured that matrix multiplication runs in time $O(n^{2+\epsilon})$ for every $\epsilon > 0$.