Graphs Having Small Number of Sizes on Induced k‐Subgraphs

Source abstract

Let $\ell$ be any positive integer, let n be a sufficiently large number, and let G be a graph on n vertices. Define, for any k, $\nu_k(G)= | \{ |E(H)| : H$ is an induced subgraph of G on k vertices$\} |$. We show that if there exists a k, $2\ell \leq k \leq n-2\ell$, such that $\nu_k(G) \le \ell$, then G has a complete or an empty subgraph on at least $n-\ell+1$ vertices and a homogeneous set of size at least $n-2\ell+2$. These results are sharp.