Photo from archive.org
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… Click to show full 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 c-Ramsey graph must contain a large subgraph with some properties typical for random graphs.
Keywords:
ramsey;
graph;
complexity proving;
graph ramsey;
proving graph
Journal Title: Combinatorica
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Combinatorica
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!