Conjecture on the maximum cut and bisection width in random regular graphs

Details Conjecture on the maximum cut and bisection width in random regular graphs Conjecture on the maximum cut and bisection width in random regular graphs

2009-12-24

arxiv.org/abs/0912.4861v1

J. Stat. Mech. (2010) P02020

Physics

Condensed Matter

Disordered Systems and Neural Networks

12 pages

Scientific paper

10.1088/1742-5468/2010/02/P02020

Asymptotic properties of random regular graphs are object of extensive study in mathematics. In this note we argue, based on theory of spin glasses, that in random regular graphs the maximum cut size asymptotically equals the number of edges in the graph minus the minimum bisection size. Maximum cut and minimal bisection are two famous NP-complete problems with no known general relation between them, hence our conjecture is a surprising property of random regular graphs. We further support the conjecture with numerical simulations. A rigorous proof of this relation is obviously a challenge.

Affiliated with

Also associated with

No associations

Rating

Conjecture on the maximum cut and bisection width in random regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Conjecture on the maximum cut and bisection width in random regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conjecture on the maximum cut and bisection width in random regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-555867