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

CREATORJakob Hofstad
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34502
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2603.03076

Browse the full library · About the Tower of Babel