Largest sparse subgraphs of random graphs

Nikolaos Fountoulakis; RJ Kang; C McDiarmid

doi:10.1016/j.ejc.2013.06.012

Largest sparse subgraphs of random graphs

Nikolaos Fountoulakis, RJ Kang, C McDiarmid

Mathematics

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

5 Citations (Scopus)

230 Downloads (Pure)

Abstract

For the Erdős–Rényi random graph Gn,p, we give a precise asymptotic formula for the size αˆ_t(G_n,_p) of a largest vertex subset in G_n,_p that induces a subgraph with average degree at most t, provided that p=p(n) is not too small and t=t(n) is not too large. In the case of fixed t and p, we find that 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)	232–244
Journal	European Journal of Combinatorics
Volume	35
Early online date	3 Jul 2013
DOIs	https://doi.org/10.1016/j.ejc.2013.06.012
Publication status	Published - 1 Jan 2014
Event	Proccedings of the 6th European Conference on combinatorics, Graph Theory and Applications - Duration: 1 Jan 2011 → …

Access to Document

10.1016/j.ejc.2013.06.012

Fountoulakis_Largest_sparse_subgraphs_European_Journal_Combinatorics_2014
Eligibility for repository : checked 03/06/2014
Final published version, 410 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@article{043f0042bfb74b6d9c74c4be94520d83,

title = "Largest sparse subgraphs of random graphs",

abstract = "For the Erd{\H o}s–R{\'e}nyi random graph Gn,p, we give a precise asymptotic formula for the size αˆt(Gn,p) of a largest vertex subset in Gn,p that induces a subgraph with average degree at most t, provided that p=p(n) is not too small and t=t(n) is not too large. In the case of fixed t and p, we find that 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.",

author = "Nikolaos Fountoulakis and RJ Kang and C McDiarmid",

year = "2014",

month = jan,

day = "1",

doi = "10.1016/j.ejc.2013.06.012",

language = "English",

volume = "35",

pages = "232–244",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Elsevier",

note = "Proccedings of the 6th European Conference on combinatorics, Graph Theory and Applications ; Conference date: 01-01-2011",

}

TY - JOUR

T1 - Largest sparse subgraphs of random graphs

AU - Fountoulakis, Nikolaos

AU - Kang, RJ

AU - McDiarmid, C

PY - 2014/1/1

Y1 - 2014/1/1

N2 - For the Erdős–Rényi random graph Gn,p, we give a precise asymptotic formula for the size αˆt(Gn,p) of a largest vertex subset in Gn,p that induces a subgraph with average degree at most t, provided that p=p(n) is not too small and t=t(n) is not too large. In the case of fixed t and p, we find that 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 Erdős–Rényi random graph Gn,p, we give a precise asymptotic formula for the size αˆt(Gn,p) of a largest vertex subset in Gn,p that induces a subgraph with average degree at most t, provided that p=p(n) is not too small and t=t(n) is not too large. In the case of fixed t and p, we find that 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.

U2 - 10.1016/j.ejc.2013.06.012

DO - 10.1016/j.ejc.2013.06.012

M3 - Article

SN - 0195-6698

VL - 35

SP - 232

EP - 244

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

T2 - Proccedings of the 6th European Conference on combinatorics, Graph Theory and Applications

Y2 - 1 January 2011

ER -

Largest sparse subgraphs of random graphs

Abstract

Access to Document

Fingerprint

Cite this