Induced subgraphs with distinct sizes

Noga Alon, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)45-53
Number of pages9
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 2009


  • Induced subgraphs
  • Ramsey graphs
  • Random graph
  • Sizes of subgraphs

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Induced subgraphs with distinct sizes'. Together they form a unique fingerprint.

Cite this