Premium
Bisecting sparse random graphs
Author(s) -
Luczak Malwina J.,
McDiarmid Colin
Publication year - 2001
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/1098-2418(200101)18:1<31::aid-rsa3>3.0.co;2-1
Subject(s) - combinatorics , random graph , struct , mathematics , vertex (graph theory) , bisection , discrete mathematics , graph , set (abstract data type) , random regular graph , dense graph , computer science , line graph , 1 planar graph , geometry , programming language
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 / n with edge probability c / n . We show that, if c >ln 4, then the bisection width is Ω( n ) with high probability; while if c