"The complexity of proving that a graph is Ramsey"@en . . "Riga" . . "Automata, Languages, and Programming. Part I" . . . "The complexity of proving that a graph is Ramsey" . "Pudl\u00E1k, Pavel" . . . "Lauria, M." . "2"^^ . "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."@en . "Thapen, Neil" . "4"^^ . . . . "66485" . . . "R\u00F6dl, V." . . "The complexity of proving that a graph is Ramsey" . "CNF formulas; independent set; lower bounds"@en . "Springer-Verlag" . . . "10.1007/978-3-642-39206-1_58" . "The complexity of proving that a graph is Ramsey"@en . "12"^^ . "2013-07-08+02:00"^^ . . "I, P(GBP202/12/G061), P(IAA100190902)" . "RIV/67985840:_____/13:00395529!RIV14-GA0-67985840" . "RIV/67985840:_____/13:00395529" . . "[259BDE06F045]" . "Berlin" . . "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." . "978-3-642-39205-4" . . . .