uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Greedy Independent Set in a Random Graph with Given Degrees
London Sch Econ, Dept Math, London WC2A 2AE, England..
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
Queen Mary Univ London, Sch Math, London, England..
2017 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 51, no 4, p. 565-586Article in journal (Refereed) Published
Abstract [en]

We analyse the size of an independent set in a random graph on n vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as n (the jamming constant), expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges in probability to the jamming constant as n. The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model.

Place, publisher, year, edition, pages
2017. Vol. 51, no 4, p. 565-586
Keywords [en]
greedy independent set, jamming constant, configuration model
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-340673DOI: 10.1002/rsa.20716ISI: 000413405500001OAI: oai:DiVA.org:uu-340673DiVA, id: diva2:1180211
Funder
Knut and Alice Wallenberg FoundationAvailable from: 2018-02-05 Created: 2018-02-05 Last updated: 2018-02-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Janson, Svante

Search in DiVA

By author/editor
Janson, Svante
By organisation
Analysis and Probability Theory
In the same journal
Random structures & algorithms (Print)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf