Carregant...
Carregant...

Vés al contingut (premeu Retorn)

A rank lower bound for cutting planes proofs of Ramsey's Theorem

Autor
Lauria, M.
Tipus d'activitat
Article en revista
Revista
ACM Transactions on Computation Theory
Data de publicació
2016-06
Volum
8
Número
4
Pàgina inicial
17
DOI
https://doi.org/10.1145/2903266 Obrir en finestra nova
Repositori
http://www.massimolauria.net/documents/ramsey-rank-cutplanes.pdf Obrir en finestra nova
URL
http://dl.acm.org/citation.cfm?doid=2956681.2903266 Obrir en finestra nova
Resum
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)...
Paraules clau
Proof Complexity, Cutting Planes, Ramsey Theory, Rank, Integer Programming
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants