Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RAMSEY:
Reports tagged with ramsey:
TR10-153 | 7th October 2010
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

#### Paris-Harrington tautologies

Revisions: 2

We initiate the study of the proof complexity of propositional encoding of (weak cases of) concrete independence results. In particular we study the proof complexity of Paris-Harrington's Large Ramsey Theorem. We prove a conditional lower bound in Resolution and a quasipolynomial upper bound in bounded-depth Frege.

more >>>

TR12-124 | 29th September 2012
Massimo Lauria

#### A rank lower bound for cutting planes proofs of Ramsey Theorem

Ramsey Theorem is a cornerstone of combinatorics and logic. In its
simplest formulation it says that there is a function \$r\$ such that
any simple graph with \$r(k,s)\$ vertices contains either a clique of
size \$k\$ or an independent set of size \$s\$. We study the complexity
of proving upper ... more >>>

TR13-038 | 13th March 2013
Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

#### The complexity of proving that a graph is Ramsey

Revisions: 1

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

ISSN 1433-8092 | Imprint