Premium
A phase transition for avoiding a giant component
Author(s) -
Bohman Tom,
Kim Jeong Han
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20085
Subject(s) - combinatorics , constant (computer programming) , mathematics , graph , component (thermodynamics) , random graph , discrete mathematics , physics , computer science , quantum mechanics , programming language
Let c be a constant and ( e 1 , f 1 ),( e 2 , f 2 ),…,( e cn , f cn ) be a sequence of ordered pairs of edges from the complete graph K n chosen uniformly and independently at random. We prove that there exists a constant c 2 such that if c > c 2 , then whp every graph which contains at least one edge from each ordered pair ( e i , f i ) has a component of size Ω( n ), and, if c < c 2 , then whp there is a graph containing at least one edge from each pair that has no component with more than O ( n 1−ϵ vertices, where ϵ is a constant that depends on c 2 − c . The constant c 2 is roughly 0.97677. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006