Talk:Giant component

Latest comment: 1 year ago by Vaughan Pratt in topic Definition is wrong

I know there are several proofs for sufficent conditions for a giant component, but can't find them offhand. They'd be useful to put here (actually what I came looking for!) Meekohi 20:46, 4 August 2005 (UTC)Reply

In the theory of random graphs, a giant component is one that contains a positive proportion of the vertices. Here we assume that the number of vertices n is going to infinity. The proportion is independent of n and need not exceed 1/2.

Definition is wrong

edit

The current definition of "a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices" is obviously wrong, since any component of a graph contains a finite fraction of the entire graph's vertices, even if that component is just a single vertex. Unfortunately I don't know enough about graph theory to know what the correct definition would be. KingSupernova (talk) 07:48, 11 March 2022 (UTC)Reply

"Finite" refers to the fraction in the limit as n tends to infinity. For p ≤ 1/n this limit is zero. For p > (1+ϵ)/n for any fixed ϵ > 0, the limit is greater than zero, i.e. "finite".
The article could be clearer on this concept. Vaughan Pratt (talk) 20:17, 1 March 2023 (UTC)Reply