ECCC-Report TR12-124https://eccc.weizmann.ac.il/report/2012/124Comments and Revisions published for TR12-124en-usSat, 29 Sep 2012 03:17:32 +0200
Paper TR12-124
| A rank lower bound for cutting planes proofs of Ramsey Theorem |
Massimo Lauria
https://eccc.weizmann.ac.il/report/2012/124Ramsey 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)\leq 4^{k}$ requires cutting planes proof
of high rank. In order to do that we show a protection lemma which
could be of independent interest.
Sat, 29 Sep 2012 03:17:32 +0200https://eccc.weizmann.ac.il/report/2012/124