A phase transition for avoiding a giant component

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