Počet záznamů: 1  

The complexity of proving that a graph is Ramsey

  1. 1. 0474390 - MU-W 2018 RIV HU eng J - Článek v odborném periodiku
    Lauria, M. - Pudlák, Pavel - Rödl, V. - Thapen, Neil
    The complexity of proving that a graph is Ramsey.
    Combinatorica. Roč. 37, č. 2 (2017), s. 253-268. ISSN 0209-9683
    Grant CEP: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
    Institucionální podpora: RVO:67985840
    Klíčová slova: complexity * c-Ramsey graphs
    Kód oboru RIV: BA - Obecná matematika
    Obor OECD: Pure mathematics
    Impakt faktor: 1.406, rok: 2017
    http://link.springer.com/article/10.1007%2Fs00493-015-3193-9

    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 c-Ramsey graph must contain a large subgraph with some properties typical for random graphs.
    Trvalý link: http://hdl.handle.net/11104/0271451
    Název souboruStaženoVelikostKomentářVerzePřístup
    Pudlak1.pdf1433.6 KBVydavatelský postprintvyžádat