Skip to main content
2 of 2
added 463 characters in body
Jacob Fox
  • 686
  • 8
  • 8

This is an open problem. Vera Sós has asked at numerous conferences if Ramsey graphs (these are graphs on n vertices with the smallest possible homogeneous set size) are quasirandom, in that each ordered graph on k vertices appears with asymptotically the same frequency. A positive answer to Sós' question would give a positive answer to your question. Unfortunately, while there are numerous nice results and conjectures about the structure of Ramsey graphs, these problems are still open.

One such result of Prömel and Rödl shows that Ramsey graphs on $n$ vertices contain all graphs up to $c\log n$ size as induced subgraphs, for an appropriate constant $c$.

H. J. Prömel and V. Rödl, Non-Ramsey graphs are $c\log n$-universal. J. Combin. Theory Ser. A 88 (1999), 379–384.

Another short proof of this result is given in:

J. Fox and B. Sudakov, Induced Ramsey-type theorems. Adv. Math. 219 (2008), 1771–1800.

Jacob Fox
  • 686
  • 8
  • 8