Número de arestas necessárias para garantir

Estou tentando resolver um determinado problema: Encontre um algoritmo para determinar se um gráfico possui um clique do tamanho 3 em $O(n^{2.81})$passos. A dica dada é que$2.81 > \log 7$. Para resolver isso, criei uma conjectura: se$m > n^{\log 7}$ então o gráfico tem $K_3$como um subgráfico. Isso resolverá facilmente o problema se a conjectura for verdadeira.

Estou tentando argumentar por contradição: vamos $m > n^{\log 7}$ e suponha que não exista um $K_3$subgráfico. Então, para qualquer conjunto de três vértices, existem exatamente 7 opções de como conectá-los. No entanto, eu estou preso quanto ao progresso a partir daqui.

Alguém vê uma maneira de provar isso, ou se a conjectura é mesmo verdadeira. Também estou interessado em ver se a conjectura pode ser estendida, ou seja, se$m > n^{\log 2^k -1})$ existe um $K_k$ subgráfico?

Dica: a multiplicação da matriz é executada no tempo $O(n^{2.71})$. Uma matriz relevante é a matriz de adjacência do gráfico.

Na verdade, isso foi melhorado várias vezes no passado. Recentemente, Le Gall melhorou isso com o tempo$O(n^{2.3728639})$. Supõe-se que a multiplicação da matriz seja executada no tempo$O(n^{2+\epsilon})$ para cada $\epsilon > 0$.