Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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