Revision #1 Authors: Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

Accepted on: 16th March 2013 04:19

Downloads: 921

Keywords:

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.

Further information about funding in the acknowledgements.

TR13-038 Authors: Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

Publication: 15th March 2013 19:40

Downloads: 787

Keywords:

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.