We show that for every 0 < ε < 1/2, there is an n 0 = n 0(ε) such that if n > n 0 then every n-vertex graph G of size at least ε( 2 n) and at most (1 - ε)( 2 n1) contains induced k-vertex subgraphs with at least 10 -7k different sizes, for every k ≤ εn/3. This is best possible, up to a constant factor. This is also a step toward a conjecture by Erdos, Faudree, and Sós on the number of distinct pairs (| V(H) |, |E(H) |) of induced subgraphs of Ramsey graphs.
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
- Induced subgraphs
- Ramsey graphs
- Random graph
- Sizes of subgraphs