Abstract
Let ℓ be any positive integer, let n be a sufficiently large number, and let G be a graph on n vertices. Define, for any k, vk(G) = |{E(H)| : H is an induced subgraph of G on k vertices}|. We show that if there exists a k, 2ℓ ≤ k ≤ n - 2ℓ, such that vk(G) ≤ ℓ, then G has a complete or an empty subgraph on at least n - ℓ + 1 vertices and a homogeneous set of size at least n - 2ℓ + 2. These results are sharp.
Original language | English (US) |
---|---|
Pages (from-to) | 264-272 |
Number of pages | 9 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 21 |
Issue number | 1 |
DOIs | |
State | Published - 2007 |
Keywords
- Homogeneous sets
- Induced subgraphs
- Reconstruction
ASJC Scopus subject areas
- Mathematics(all)