patternMinor
Number of edges required to guarantee $K_3$ as subgraph
Viewed 0 times
numberedgesguaranteek_3subgraphrequired
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#22554, answer score: 4
Revisions (0)
No revisions yet.