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 clogn. 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.
The complexity of proving that a graph is Ramsey / Lauria, Massimo; Pudlák, Pavel; Rödl, Vojtěch; Thapen, Neil. - In: COMBINATORICA. - ISSN 0209-9683. - 37:2(2017), pp. 253-268. [10.1007/s00493-015-3193-9]
The complexity of proving that a graph is Ramsey
LAURIA, MASSIMO
;
2017
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 clogn. 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.| File | Dimensione | Formato | |
|---|---|---|---|
|
Lauria_Complexity-of-proving_2016.pdf
solo gestori archivio
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
398.18 kB
Formato
Adobe PDF
|
398.18 kB | Adobe PDF | Contatta l'autore |
|
Lauria_Complexity-of-proving_2017.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
423.46 kB
Formato
Adobe PDF
|
423.46 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
