Consider partitions of the vertex set of a graph G into two sets with sizes differing by at most 1: the bisection width of G is the minimum over all such partitions of the number of "cross edges" between the parts. We are interested in sparse random graphs G(n,c) with edge probability c. We show that, if c > 1n 4, then the bisection width is Omega (n) with high probability; while if c < 1n 4, then it is equal to 0 with high probability. There are corresponding threshold results for partitioning into any fixed number of parts. (C) 2001 John Wiley & Sons, Inc. [References: 16]
展开▼
