### Abstract

An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdo″s, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n^{5/2}) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n^{5/2}). We prove an Ω(n^{2.3693}) lower bound.

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

Pages (from-to) | 459-476 |

Number of pages | 18 |

Journal | Combinatorics Probability and Computing |

Volume | 18 |

Issue number | 4 |

DOIs | |

State | Published - Jul 1 2009 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Sizes of induced subgraphs of Ramsey graphs'. Together they form a unique fingerprint.

## Cite this

Alon, N., Balogh, J., Kostochka, A., & Samotij, W. (2009). Sizes of induced subgraphs of Ramsey graphs.

*Combinatorics Probability and Computing*,*18*(4), 459-476. https://doi.org/10.1017/S0963548309009869