Largest sparse subgraphs of random graphs

Nikolaos Fountoulakis; Ross J. Kang; Colin McDiarmid

doi:10.1016/j.endm.2011.09.057

Largest sparse subgraphs of random graphs

Nikolaos Fountoulakis^*, Ross J. Kang, Colin McDiarmid

^*Corresponding author for this work

Mathematics

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

Abstract

For the Erdos-Rényi random graph G_n,p, we consider the order of a largest vertex subset that induces a subgraph with average degree at most t. For the case when both p and t are fixed, this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.

Original language	English
Pages (from-to)	349-354
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	38
DOIs	https://doi.org/10.1016/j.endm.2011.09.057
Publication status	Published - 1 Dec 2011

Bibliographical note

Funding Information:
Acknowledgement. Part of this research was conducted while RJK was a NSERC Postdoctoral Fellow at McGill University; he is currently supported by the EPSRC, grant EP/G066604/1.

Keywords

Independence number
Large deviations
Random graphs
Sparse subgraphs
Two-point concentration

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2011.09.057

Cite this

@article{9c275fb31cb94c61a7d04510d1460b39,

title = "Largest sparse subgraphs of random graphs",

abstract = "For the Erdos-R{\'e}nyi random graph Gn,p, we consider the order of a largest vertex subset that induces a subgraph with average degree at most t. For the case when both p and t are fixed, this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.",

keywords = "Independence number, Large deviations, Random graphs, Sparse subgraphs, Two-point concentration",

author = "Nikolaos Fountoulakis and Kang, {Ross J.} and Colin McDiarmid",

note = "Funding Information: Acknowledgement. Part of this research was conducted while RJK was a NSERC Postdoctoral Fellow at McGill University; he is currently supported by the EPSRC, grant EP/G066604/1.",

year = "2011",

month = dec,

day = "1",

doi = "10.1016/j.endm.2011.09.057",

language = "English",

volume = "38",

pages = "349--354",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Largest sparse subgraphs of random graphs

AU - Fountoulakis, Nikolaos

AU - Kang, Ross J.

AU - McDiarmid, Colin

N1 - Funding Information: Acknowledgement. Part of this research was conducted while RJK was a NSERC Postdoctoral Fellow at McGill University; he is currently supported by the EPSRC, grant EP/G066604/1.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - For the Erdos-Rényi random graph Gn,p, we consider the order of a largest vertex subset that induces a subgraph with average degree at most t. For the case when both p and t are fixed, this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.

AB - For the Erdos-Rényi random graph Gn,p, we consider the order of a largest vertex subset that induces a subgraph with average degree at most t. For the case when both p and t are fixed, this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.

KW - Independence number

KW - Large deviations

KW - Random graphs

KW - Sparse subgraphs

KW - Two-point concentration

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

U2 - 10.1016/j.endm.2011.09.057

DO - 10.1016/j.endm.2011.09.057

M3 - Article

AN - SCOPUS:82955216125

SN - 1571-0653

VL - 38

SP - 349

EP - 354

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Largest sparse subgraphs of random graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this