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 Omega(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-epsilon)) vertices, where epsilon is a constant that depends on c(2) - c. The constant c(2) is roughly 0.97677. (c) 2005 Wiley Periodicals, Inc.