Počet záznamů: 1
The complexity of proving that a graph is Ramsey
- 1.
SYSNO ASEP 0474390 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název The complexity of proving that a graph is Ramsey Tvůrce(i) Lauria, M. (SE)
Pudlák, Pavel (MU-W) RID, SAI
Rödl, V. (US)
Thapen, Neil (MU-W) RID, SAIZdroj.dok. Combinatorica. - : Springer - ISSN 0209-9683
Roč. 37, č. 2 (2017), s. 253-268Poč.str. 16 s. Jazyk dok. eng - angličtina Země vyd. HU - Maďarsko Klíč. slova complexity ; c-Ramsey graphs Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics 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 000399890000008 EID SCOPUS 85018519537 DOI 10.1007/s00493-015-3193-9 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 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2018
Počet záznamů: 1