The complexity of proving that a graph is Ramsey

Abstract

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 resolution proofs that $G$ is $c$-Ramsey, for every graph $G$. Our proof makes use of the fact that every Ramsey graph must contain a large subgraph with some of the statistical properties of the random graph.

14 pages