Two-Point Concentration of the Independence Number of the Random Graph
In: Forum of Mathematics, Sigma, Jg. 12 (2024)
Online
academicJournal
Zugriff:
We show that the independence number of $ G_{n,p}$ is concentrated on two values if $ n^{-2/3+ \epsilon } < p \le 1$ . This result is roughly best possible as an argument of Sah and Sawhney shows that the independence number is not, in general, concentrated on two values for $ p = o ( (\log (n)/n)^{2/3} )$ . The extent of concentration of the independence number of $ G_{n,p}$ for $ \omega (1/n) < p \le n^{-2/3}$ remains an interesting open question.
Titel: |
Two-Point Concentration of the Independence Number of the Random Graph
|
---|---|
Autor/in / Beteiligte Person: | Bohman, Tom ; Hofstad, Jakob |
Link: | |
Zeitschrift: | Forum of Mathematics, Sigma, Jg. 12 (2024) |
Veröffentlichung: | Cambridge University Press, 2024 |
Medientyp: | academicJournal |
ISSN: | 2050-5094 (print) |
DOI: | 10.1017/fms.2024.6 |
Schlagwort: |
|
Sonstiges: |
|