[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.


TITLE: The Complexity of Proving that a Graph is Ramsey

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.

On my webpage (see "manuscript" section)

A direct link

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.)

More information about the Proof-Complexity mailing list