Fetching the paper…
Reading the bibliography…
For Erd\H{o}s-R\'enyi random graphs with average degree $\gamma$, and uniformly random $\gamma$-regular graph on $n$ vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are $n\Big(\frac{\gamma}{4} + {{\sf P}}_* \sqrt{\frac{\gamma}{4}} + o(\sqrt{\gamma})\Big) + o(n)$ while the size of the minimum bisection is $n\Big(\frac{\gamma}{4}-{{\sf P}}_*\sqrt{\frac{\gamma}{4}} + o(\sqrt{\gamma})\Big) + o(n)$.
V. Chvátal, The tail of the hypergeometric distribution , Discrete Mathematics 25
1979
Earlier work this paper cites.
B. Bollobás, The isoperimetric number of random regular graphs , Eur. Jour. of Combinatorics 9
1984
Earlier work this paper cites.
M. Mézard, G. Parisi, and M. Virasoro, Spin glass theory and beyond: An introduction to the replica method and its applications , World Scientific Lecture Notes in Physics, vol. 9, World Scientific, 1986
1986
Earlier work this paper cites.
S. Poljak and Z. Tuza, Maximum cuts and largest bipartite subgraphs , DIMACS series in Discrete Mathematics and Theoretical Computer Science, vol. 20, pp. 181–244, American Mathematical Society, Providence, R.I., 1995
1995
Earlier work this paper cites.
N. Alon, On the edge expansion of graphs , Combinatorics, Probability and Computing 6
1997
Earlier work this paper cites.
J. Hastad, Some optimal inapproximability results , Symposium on the Theory of Computing, El Paso, TX, 1997, pp. 1–10
1997
Earlier work this paper cites.
N. C. Wormald, Models of random regular graphs , London Mathematical Society Lecture Note Series (1999), 239–298
1999
Earlier work this paper cites.
U. Feige and R. Krauthgamer, A polylogarithmic approximation of the minimum bisection , Foundations of Computer Science, Redondo Beach, CA, November 2000, pp. 105–115
2000
Earlier work this paper cites.
S. Janson, T. Luczak, and A. Rucinski, Random graphs , John Wiley and Sons., 2000
2000
Earlier work this paper cites.
M. Luczak and C. McDiarmid, Bisecting sparse random graphs , Rand. Struct. Alg. 18
2000
Earlier work this paper cites.
B. Bollobás, Random graphs , second ed., Cambridge studies in advanced mathematics., Cambridge University Press, 2001
2001
Earlier work this paper cites.
A. Crisanti and T. Rizzo, Analysis of the ∞ \infty -replica symmetry breaking solution of the Sherrington-Kirkpatrick model , Physical Review E 65
2002
Earlier work this paper cites.
J. Díaz, J. Petit, and M. J. Serna, A survey on graph layout problems , ACM Comput. Surveys 34
2002
Earlier work this paper cites.
F. Guerra and F.L. Toninelli, The thermodynamic limit in mean field spin glass models , Commun. Math. Phys. 230
2002
Earlier work this paper cites.
E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems , Rand. Struct. Alg. 20
2002
Cited alongside, same era.
S. Franz and M. Leone, Replica bounds for optimization problems and diluted spin systems , J. Stat. Phys. 111
2003
Cited alongside, same era.
J. Friedman, A proof of alon’s second eigenvalue conjecture , Proc. of the 35th Symp. on Theory of Computing, San Diego, 2003, pp. 720–724
2003
Cited alongside, same era.
F. Guerra, Broken replica symmetry bounds in the mean field spin glass model , Communications in mathematical physics 233
2003
Cited alongside, same era.
M. Talagrand, Spin glasses: A challenge for mathematicians: Cavity and mean field models , Springer,New York, 2003
2003
Cited alongside, same era.
A.G. Percus, G. Istrate, B. Gonçalves, R.Z. Sumi, and S. Boettcher, The peculiar phase structure of random graph bisection , Journal of Mathematical Physics 49
2008
Later among the works it cites.
G.W. Anderson, A. Guionnet, and O. Zeitouni, An introduction to random matrices , Cambridge studies in advanced mathematics., Cambridge University Press, 2009
2009
Later among the works it cites.
M. Mezard and A. Montanari, Information, physics, and computation , Oxford University Press, 2009
2009
Later among the works it cites.
2010
Later among the works it cites.
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications , Physical Review E 84
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
D. Coppersmith, D. Gamarnik, M. Hajiaghayi, and G. Sorkin, Random maxsat, random maxcut, and their phase transitions , Rand. Struct. Alg. 24
2004
Cited alongside, same era.
F. Guerra and F.L. Toninelli, The high temperature region of the Viana-Bray diluted spin glass models , J. Stat. Phys 115
2004
Cited alongside, same era.
S. Khot, Ruling out ptas for graph min-bisection, densest subgraph and bipartite clique , Foundations of Computer Science, Roma, Italy, October 2004, pp. 136–145
2004
Cited alongside, same era.
U. Feige and E. Ofek, Spectral techniques applied to sparse random graphs , Random Structures & Algorithms 27
2005
Cited alongside, same era.
J.H. Kim, Poisson cloning model for random graphs , International Congress of Mathematicians, vol. 3, Eur. Math. Soc., 2006, pp. 873–897
2006
Cited alongside, same era.
O. Khorunzhiy, W. Kirsch, and P. Müller, Lifshitz tails for spectra of Erdős–Rényi random graphs , The Annals of Applied Probability 16
2006
Cited alongside, same era.
M. Talagrand, The Parisi Formula , Ann. Math. 163
2006
Cited alongside, same era.
2011
Later among the works it cites.
H. Daudé, C. Martínez, V. Rasendrahasina, and V. Ravelomanana, The max-cut of sparse random graphs , Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 265–271
2012
Later among the works it cites.
M. Bayati, D. Gamarnik, and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs , Annals of Probability 41
2013
Later among the works it cites.
S. Boucheron, G. Lugosi, and P. Massart, Concentration inequalities: A nonasymptotic theory of independence , Oxford University Press, 2013
2013
Later among the works it cites.
2013
Later among the works it cites.
D. Panchenko, The Sherrington- Kirkpatrick Model , Springer Monographs in Mathematics, Springer, 2013
2013
Later among the works it cites.
A. Auffinger and W. K. Chen, The Parisi formula has a unique minimizer , Communications in Mathematical Physics (2014), 1–16
2014
Later among the works it cites.
D. Gamarnik and Q. Li, On the max-cut over sparse random graph , arXiv:1411.1698v1, November 2014
2014
Later among the works it cites.
L. Massoulié, Community detection thresholds and the weak Ramanujan property , Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, 2014, pp. 694–703
2014
Later among the works it cites.