Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Vojtech Rodl:

TR13-038 | 13th March 2013
Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

The complexity of proving that a graph is Ramsey

Revisions: 1

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of ... more >>>

ISSN 1433-8092 | Imprint