Number of the records: 1
The complexity of proving that a graph is Ramsey
- 1.0395529 - MÚ 2014 RIV DE eng C - Conference Paper (international conference)
Lauria, Massimo - Pudlák, Pavel - Thapen, Neil - Rödl, V.
The complexity of proving that a graph is Ramsey.
Automata, Languages, and Programming. Part I. Berlin: Springer, 2013 - (Fomin, F.; Freivalds, R.; Kwiatkowska, M.; Peleg, D.), s. 684-695. Lecture Notes in Computer Science, 7965. ISBN 978-3-642-39205-4.
[International Colloquium, ICALP 2013 /40./. Riga (LT), 08.07.2013-12.07.2013]
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : CNF formulas * independent set * lower bounds
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007%2F978-3-642-39206-1_58
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.
Permanent Link: http://hdl.handle.net/11104/0223541
File Download Size Commentary Version Access Pudlak.pdf 5 224.2 KB Publisher’s postprint require
Number of the records: 1