Timeline for Determine if a graph has a large clique
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2014 at 23:56 | comment | added | John | I asked for two reasons. First, if it did hold, then your graphs would look somewhat similar to the binomially random graph $G_{n,1/2}$. This could be useful since pseudorandomness can be a very powerful property and there's probably a heuristic out there that exploits it. Secondly, it would suggest your graphs are likely to have clique number less than 20 or so (since $2^{-20}\cdot 5000 \ll 1$), so it would probably be worth running tests for $k=20$ before running them for $k=50$. But if it doesn't hold then never mind. | |
| Mar 17, 2014 at 18:39 | comment | added | Jernej | I haven't tested this formally but given what I know about the graphs I am not sure this holds - do you have any kind of motivation for this? | |
| Mar 17, 2014 at 17:57 | comment | added | John | Silly question: is it true that if you have a set of $t$ vertices, their common neighbourhood has size roughly $2^{-t}\cdot 5000$? (For values of $t$ which are small enough that you can test this easily.) | |
| Mar 17, 2014 at 17:46 | comment | added | Jernej | Yes. The common neighbourhood of any pair of vertices is still too large though. | |
| Mar 17, 2014 at 17:20 | comment | added | John | I don't think that's a big problem, though? When I say that $G[N(v)]$ should have many vertices of low degree, I mean low degree in $N(v)$ rather than in $G$ itself. So the approach should only fail completely if every pair of vertices has a large common neighbourhood. | |
| Mar 17, 2014 at 16:19 | comment | added | Jernej | Dear John, the graph in question has no vertices of small degree (the minimum degree is about at least 1800 in all graphs in $\mathcal{C}$) | |
| Mar 17, 2014 at 13:18 | review | First posts | |||
| Mar 17, 2014 at 13:19 | |||||
| Mar 17, 2014 at 13:01 | history | answered | John | CC BY-SA 3.0 |