Change search
ReferencesLink to record
Permanent link

Direct link
The complexity of proving that a graph is Ramsey
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4003-3168
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)
Abstract [en]

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
Keyword [en]
CNF formulas, Independent set, Lower bounds, Random graphs, Resolution proofs, Statistical properties, Subgraphs, Automata theory, Graph theory
National Category
Computer Science
URN: urn:nbn:se:kth:diva-134079DOI: 10.1007/978-3-642-39206-1_58ISI: 000342686600058ScopusID: 2-s2.0-84880262321ISBN: 978-364239205-4OAI: diva2:664560
40th International Colloquium on Automata, Languages, and Programming, ICALP 2013; Riga; Latvia; 8 July 2013 through 12 July 2013

QC 20131115

Available from: 2013-11-15 Created: 2013-11-15 Last updated: 2014-11-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

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

Altmetric score

Total: 26 hits
ReferencesLink to record
Permanent link

Direct link