Number of the records: 1
The complexity of proving that a graph is Ramsey
- 1.
SYSNO ASEP 0395529 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title The complexity of proving that a graph is Ramsey Author(s) Lauria, Massimo (MU-W) SAI
Pudlák, Pavel (MU-W) RID, SAI
Thapen, Neil (MU-W) RID, SAI
Rödl, V. (US)Source Title Automata, Languages, and Programming. Part I. - Berlin : Springer, 2013 / Fomin F.V. ; Freivalds R. ; Kwiatkowska M. ; Peleg D. - ISBN 978-3-642-39205-4 Pages s. 684-695 Number of pages 12 s. Publication form Print - P Action International Colloquium, ICALP 2013 /40./ Event date 08.07.2013-12.07.2013 VEvent location Riga Country LT - Lithuania Event type WRD Language eng - English Country DE - Germany Keywords CNF formulas ; independent set ; lower bounds Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) Institutional support MU-W - RVO:67985840 UT WOS 000342686600058 EID SCOPUS 84880262321 DOI 10.1007/978-3-642-39206-1_58 Annotation 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 logn. 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2014
Number of the records: 1