Optimal and Random Partitions of Random Graphs
Joseph L. Ganley · The Computer Journal · 1994
The behavior of random graphs with respect to graph partitioning is considered. It is shown that, for a random graph with n vertices and with expected degree exceeding a constant times ln n, the graph cannot be partitioned well, i.e. a random partition is likely to be almost as good as an optimal partition.