The complexity of proving that a graph is Ramsey
2013 (English)In: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 2013, no PART 1, 684-695 p.Conference paper (Refereed)
We say that a graph with n vertices is c-Ramsey if it does not contain either a clique or an independent set of size c log n. We define a CNF formula which expresses this property for a graph G. We show a superpolynomial lower bound on the length of resolution proofs that G is c-Ramsey, for every graph G. Our proof makes use of the fact that every Ramsey graph must contain a large subgraph with some of the statistical properties of the random graph.
Place, publisher, year, edition, pages
Springer, 2013. no PART 1, 684-695 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7965 LNCS
CNF formulas, Independent set, Lower bounds, Random graphs, Resolution proofs, Statistical properties, Subgraphs, Automata theory, Graph theory
IdentifiersURN: urn:nbn:se:kth:diva-134079DOI: 10.1007/978-3-642-39206-1_58ISI: 000342686600058ScopusID: 2-s2.0-84880262321ISBN: 978-364239205-4OAI: oai:DiVA.org:kth-134079DiVA: diva2:664560
40th International Colloquium on Automata, Languages, and Programming, ICALP 2013; Riga; Latvia; 8 July 2013 through 12 July 2013
QC 201311152013-11-152013-11-152014-11-07Bibliographically approved