Non-Ramsey Graphs Are c log n-Universal

✍ Scribed by Hans Jürgen Prömel; Vojtěch Rödl

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 98 KB
• Volume: 88
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1999.2972

✦ Synopsis

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.

1999 Academic Press

The symbol n Ä (k) 2 2 , defined by Erdo s and Rado [ER], means that if we color the edges of the complete graph K n by two colors there are always k vertices with all pairs colored by the same color. The symbol n Ä % (k) 2 2 denotes the negation of the statement above. We say that a graph G with n vertices establishes the relation nÄ % (k) 2 2 if neither G nor its complement