Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR13-038 | 16th March 2013 04:19

#### The complexity of proving that a graph is Ramsey

Revision #1
Authors: Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen
Accepted on: 16th March 2013 04:19
Keywords:

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.

Changes to previous version:

Further information about funding in the acknowledgements.

### Paper:

TR13-038 | 13th March 2013 12:04

#### The complexity of proving that a graph is Ramsey

TR13-038
Authors: Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen
Publication: 15th March 2013 19:40