Change search
ReferencesLink to record
Permanent link

Direct link
A rank lower bound for cutting planes proofs of Ramsey Theorem
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4003-3168
2012 (English)In: Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092, no 124Article in journal (Other academic) Published
Abstract [en]

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
Keyword [en]
cutting planes, proof complexity, ramsey, rank
National Category
Computer Science
URN: urn:nbn:se:kth:diva-112883OAI: diva2:587526

QC 20120503

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2013-05-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Search in DiVA

By author/editor
Lauria, Massimo
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 30 hits
ReferencesLink to record
Permanent link

Direct link