Non-Ramsey Graphs Are c log n-Universal

摘要

We prove that for any c_1 > 0 there exists c_2 > 0 such that the following statement is true: If G is a graph with n vertices and with the property that neither G nor its complement contains a complete graph K_l, where l = c_1 log n then G is c_2 log n-universal, i.e., G contains all subgraphs with c_2 log n vertices as induced subgraphs.