Počet záznamů: 1
The complexity of proving that a graph is Ramsey
- 1.
SYSNO ASEP 0395529 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název The complexity of proving that a graph is Ramsey Tvůrce(i) Lauria, Massimo (MU-W) SAI
Pudlák, Pavel (MU-W) RID, SAI
Thapen, Neil (MU-W) RID, SAI
Rödl, V. (US)Zdroj.dok. Automata, Languages, and Programming. Part I. - Berlin : Springer, 2013 / Fomin F.V. ; Freivalds R. ; Kwiatkowska M. ; Peleg D. - ISBN 978-3-642-39205-4 Rozsah stran s. 684-695 Poč.str. 12 s. Forma vydání Tištěná - P Akce International Colloquium, ICALP 2013 /40./ Datum konání 08.07.2013-12.07.2013 Místo konání Riga Země LT - Litva Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova CNF formulas ; independent set ; lower bounds Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd GBP202/12/G061 GA ČR - Grantová agentura ČR Institucionální podpora MU-W - RVO:67985840 UT WOS 000342686600058 EID SCOPUS 84880262321 DOI 10.1007/978-3-642-39206-1_58 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2014
Počet záznamů: 1