[Proof Complexity] New preprint "The Complexity of Proving that a Graph is Ramsey"
Massimo Lauria
lauria.massimo at gmail.com
Wed Mar 13 14:34:27 CET 2013
Dear colleagues,
I just uploaded on my webpage a preprint of a new proof complexity paper
by Pavel Pudlak, Vojtech Rodl, Neil Thapen and myself.
Please let us know your comments, observations and questions.
Best,
TITLE: The Complexity of Proving that a Graph is Ramsey
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.
LINK:
On my webpage (see "manuscript" section)
http://www.csc.kth.se/~lauria/writings.html
A direct link
http://www.csc.kth.se/~lauria/documents/ramsey-graphs-full.pdf
Soon the paper will appear on ECCC and ArXiv.
--
Massimo Lauria
KTH Royal Institute of Technology
School of Computer Science and Communication
Osquars Backe 2, SE-100 44 Stockholm, Sweden
+46 (0) 73 8008 125 (Cell.)
httlp://www.csc.kth.se/~lauria/
More information about the Proof-Complexity
mailing list