Logarithmic-regime giant component

ID: logarithmic-regime-giant-component

Fix , , and with . A binomial random graph has one giant component of the displayed order and all other graph components are tree components of orders at most , with high probability. The expected value and variance of the isolated vertex count concentrate it around . A Cayley formula upper bound for connected sets excludes component sizes through a small fixed fraction of ; the empty-graph cut bound excludes the remaining sizes up to . An extra-edge count excludes cyclic small graph components. The expected value of the number of vertices in small nonisolated tree components is , where . The Markov inequality completes the count of vertices outside the unique large graph component.

New to topics? Read the docs here!