[Proof Complexity] New preprint "The Complexity of Proving that a Graph is Ramsey"

[Massimo Lauria]

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/