Massimo Lauria: The Complexity of Proving that a Graph is Ramsey
Massimo Lauria, Theory Group, KTH CSC
Tid: Må 2013-09-30 kl 12.10 - 13.00
Plats: Room 4523, Lindstedtsvägen 5, 5th floor, KTH CSC
Lunch is served at 12:00 noon (register at doodle.com/226vivp4trzzy8v5 by Thursday Sep 26 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
Abstract
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 Ramsey graph must contain a large subgraph with some of the statistical properties of the random graph.
Joint work with Pavel Pudlák, Vojtěch Rödl and Neil Thapen. The paper appeared at ICALP 2013.