ECCC-Report TR13-038https://eccc.weizmann.ac.il/report/2013/038Comments and Revisions published for TR13-038en-usSat, 16 Mar 2013 04:19:49 +0200
Revision 1
| The complexity of proving that a graph is Ramsey |
Massimo Lauria,
Pavel Pudlak,
Vojtech Rodl,
Neil Thapen
https://eccc.weizmann.ac.il/report/2013/038#revision1We 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.
Sat, 16 Mar 2013 04:19:49 +0200https://eccc.weizmann.ac.il/report/2013/038#revision1
Paper TR13-038
| The complexity of proving that a graph is Ramsey |
Massimo Lauria,
Pavel Pudlak,
Vojtech Rodl,
Neil Thapen
https://eccc.weizmann.ac.il/report/2013/038We 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.
Fri, 15 Mar 2013 19:40:09 +0200https://eccc.weizmann.ac.il/report/2013/038