Induced subgraphs with distinct sizes

Noga Alon, A. V. Kostochka

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

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
Volume34
Issue number1
DOIs
StatePublished - Jan 1 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

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

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

Cite this