### Abstract

Let P(x,y,n) be a real polynomial and let {G_{n}} be a family of graphs, where the set of vertices of G_{n} is {1,2,…,n} and for 1 ≤ i < j ≤ n {i,j} is an edge of G_{n} iff P(i,j,n) > 0. Motivated by a question of Babai, we show that there is a positive constant c depending only on P such that either G_{n} or its complement G_{n} contains a complete subgraph on at least c2^{1/2√log n} vertices. Similarly, either G_{n} or G_{n} contains a complete bipartite subgraph with at least cn^{1/2} vertices in each color class. Similar results are proved for graphs defined by real polynomials in a more general way, showing that such graphs satisfy much stronger Ramsey bounds than do random graphs. This may partially explain the difficulties in finding an explicit construction for good Ramsey graphs.

Original language | English (US) |
---|---|

Pages (from-to) | 651-661 |

Number of pages | 11 |

Journal | Journal of Graph Theory |

Volume | 14 |

Issue number | 6 |

DOIs | |

State | Published - Dec 1990 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Geometry and Topology