Concentration of the largest induced tree size of G n , p G_{n,p} around the standard expectation threshold
Jakob Hofstad · 2026
Read Concentration of the largest induced tree size of G n , p G_{n,p} around the standard expectation threshold by Jakob Hofstad (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03076.txt.
Description
Jakob Hofstad pins down the largest tree that hides inside a random graph. Each edge of the graph shows up with a set chance, picked on its own. The biggest tree that fits, using only edges that show up, tends to land on one of two next-door values.
Past work proved this tight result for fixed chances, and for chances that fade slowly. Hofstad extends it to all fading chances above a stated floor. Below that range, the picture flips. For chances in a lower band, the biggest tree provably does not settle at the value plain averages predict. The two results draw a sharp line where simple averages stop describing random graphs.
Catalog record
| CREATOR | Jakob Hofstad |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34502 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.03076