Induced subgraphs with distinct sizes

Noga Alon; A. V. Kostochka

doi:10.1002/rsa.20250

Induced subgraphs with distinct sizes

Noga Alon, A. V. Kostochka

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

We show that for every 0 < ε < 1/2, there is an n ₀ = n ₀(ε) such that if n > n ₀ then every n-vertex graph G of size at least ε( ₂ ⁿ) and at most (1 - ε)( ₂ ⁿ1) 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 language	English (US)
Pages (from-to)	45-53
Number of pages	9
Journal	Random Structures and Algorithms
Volume	34
Issue number	1
DOIs	https://doi.org/10.1002/rsa.20250
State	Published - Jan 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Keywords

Induced subgraphs
Ramsey graphs
Random graph
Sizes of subgraphs

Access to Document

10.1002/rsa.20250

Cite this

@article{893e179cce7a40c89ab242ddeb81d1d2,

title = "Induced subgraphs with distinct sizes",

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{\'o}s on the number of distinct pairs (| V(H) |, |E(H) |) of induced subgraphs of Ramsey graphs.",

keywords = "Induced subgraphs, Ramsey graphs, Random graph, Sizes of subgraphs",

author = "Noga Alon and Kostochka, {A. V.}",

year = "2009",

month = jan,

doi = "10.1002/rsa.20250",

language = "English (US)",

volume = "34",

pages = "45--53",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "1",

}

TY - JOUR

T1 - Induced subgraphs with distinct sizes

AU - Alon, Noga

AU - Kostochka, A. V.

PY - 2009/1

Y1 - 2009/1

N2 - 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.

AB - 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.

KW - Induced subgraphs

KW - Ramsey graphs

KW - Random graph

KW - Sizes of subgraphs

UR - http://www.scopus.com/inward/record.url?scp=60349112008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=60349112008&partnerID=8YFLogxK

U2 - 10.1002/rsa.20250

DO - 10.1002/rsa.20250

M3 - Article

AN - SCOPUS:60349112008

SN - 1042-9832

VL - 34

SP - 45

EP - 53

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

Induced subgraphs with distinct sizes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this