I believe the answer is "no"; the best known constructions only give no clique or independent set of size about 2^\sqrt{n} in a graph with n 2^n vertices. Bill Gasarch has a page on the subject here, although I don't know how frequently it updates.
|
2 | Duh, I meant 2^n vertices. | ||
|
|
||||
|
|
1 |
|
||
|
I believe the answer is "no"; the best known constructions only give no clique or independent set of size about 2^\sqrt{n} in a graph with n vertices. Bill Gasarch has a page on the subject here, although I don't know how frequently it updates. |
||||
