A rank lower bound for cutting planes proofs of Ramsey Theorem
2012 (English)In: Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092, no 124Article in journal (Other academic) Published
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 bounds for the number r(k, k). In particular we focus on the propositional proof system cutting planes; we prove that the upper bound “r(k, k) 4k” requires cutting planes proof of high rank. In order to do that we show a protection lemma which could be of independent interest.
Place, publisher, year, edition, pages
2012. no 124
cutting planes, proof complexity, ramsey, rank
IdentifiersURN: urn:nbn:se:kth:diva-112883OAI: oai:DiVA.org:kth-112883DiVA: diva2:587526
QC 201205032013-01-142013-01-142013-05-03Bibliographically approved