Skip to main content
added 463 characters in body
Source Link
Jacob Fox
  • 686
  • 8
  • 8

This is an open problem. Vera SosSó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 Sos'Sós' question would give a positive answer to your question. Unfortunately, while we know somethere 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.

This is an open problem. Vera Sos 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 Sos' question would give a positive answer to your question. Unfortunately, while we know some results about the structure of Ramsey graphs, these problems are still open.

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.

Source Link
Jacob Fox
  • 686
  • 8
  • 8

This is an open problem. Vera Sos 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 Sos' question would give a positive answer to your question. Unfortunately, while we know some results about the structure of Ramsey graphs, these problems are still open.