7
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Louis Mar 12 '14 at 21:27
  • $\begingroup$ @Louis The division should be floored or ceiled I guess $\endgroup$ – saadtaame Mar 12 '14 at 22:12
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Mar 12 '14 at 22:13
  • $\begingroup$ @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? $\endgroup$ – kbrose Mar 17 '14 at 21:25
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.