Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

The complexity of proving that a graph is Ramsey

RSS-Feed




Revision #1
Authors: Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen
Accepted on: 16th March 2013 04:19
Downloads: 921
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
Downloads: 787
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.



ISSN 1433-8092 | Imprint