Ramsey's Theorem is a cornerstone of combinatorics and logic. In its simplest formulation it says that for every k>0 and s>0, there is a minimum number r(k,s) such that any simple graph with at least 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 show that any cutting plane proof of the upper bound “r(k,k)≤4k” requires high rank. In order to do that we show a protection lemma which could be of independent interest.

A rank lower bound for cutting Planes Proofs of Ramsey's Theorem / Lauria, Massimo. - In: ACM TRANSACTIONS ON COMPUTATION THEORY. - ISSN 1942-3454. - 8:4(2016), pp. 1-13. [10.1145/2903266]

A rank lower bound for cutting Planes Proofs of Ramsey's Theorem

Abstract

Ramsey's Theorem is a cornerstone of combinatorics and logic. In its simplest formulation it says that for every k>0 and s>0, there is a minimum number r(k,s) such that any simple graph with at least 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 show that any cutting plane proof of the upper bound “r(k,k)≤4k” requires high rank. In order to do that we show a protection lemma which could be of independent interest.
Scheda breve Scheda completa
2016
cutting planes; integer programming; proof complexity; Ramsey theory; rank; theoretical computer science; computational theory and mathematics
01 Pubblicazione su rivista::01a Articolo in rivista
A rank lower bound for cutting Planes Proofs of Ramsey's Theorem / Lauria, Massimo. - In: ACM TRANSACTIONS ON COMPUTATION THEORY. - ISSN 1942-3454. - 8:4(2016), pp. 1-13. [10.1145/2903266]
File allegati a questo prodotto
File
2016, Lauria_Ran-Lower-Bound_2016.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11573/957408`