  We consider sequences of large sparse random graphs whose degree distribution
approaches a limit with finite mean. This model includes both the random
regular graphs and the Erd\"os-Renyi graphs of constant average degree. We
prove that the maximum bisection ratio of such a graph sequence converges
almost surely to a deterministic limit. We extend this result to so-called
2-spin spin glasses in the paramagnetic to ferromagnetic regime. Our work
generalizes the graph interpolation method to some non-additive graph
parameters.
