The complexity of proving that a graph is Ramsey

Number of the records: 1

1.

SYSNO ASEP	0474390
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	The complexity of proving that a graph is Ramsey
Author(s)	Lauria, M. (SE) Pudlák, Pavel (MU-W)_{RID, SAI} Rödl, V. (US) Thapen, Neil (MU-W)_{RID, SAI}
Source Title	Combinatorica. - : Springer - ISSN 0209-9683 Roč. 37, č. 2 (2017), s. 253-268
Number of pages	16 s.
Language	eng - English
Country	HU - Hungary
Keywords	complexity ; c-Ramsey graphs
Subject RIV	BA - General Mathematics
OECD category	Pure 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	000399890000008
EID SCOPUS	85018519537
DOI	10.1007/s00493-015-3193-9
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 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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2018

Number of the records: 1