Fetching the paper…

Reading the bibliography…

2014

On the Max-Cut of Sparse Random Graphs

Gamarnik, David, Li, Quan

Original
PDF
Post on X

Understand

We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erd\H{o}s-R\'{e}nyi graph on $n$ nodes and $\lfloor cn \rfloor$ edges.

It is shown in Coppersmith et al.
~\cite{Coppersmith2004} that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region $[c/2+0.37613\sqrt{c},c/2+0.58870\sqrt{c}]$ with high probability (w.h.p.) as $n$ increases, for all sufficiently large $c$.
In this paper we improve both upper and lower bounds by introducing a novel bounding technique.

On the Max-Cut of Sparse Random Graphs · Around

Built on

V Richter,
1958
Earlier work this paper cites.
Maurice Sion et al.,
Original
1958
Earlier work this paper cites.
Narasinga R Chaganty and J Sethuraman,
1985
Earlier work this paper cites.
A. Frieze,
1990
Earlier work this paper cites.
A. Dembo and O. Zeitouni,
1998
Earlier work this paper cites.
Olivier Dubois, Yacine Boufkhad, and Jacques Mandler,
2000
Earlier work this paper cites.
R Gardner,
2002
Earlier work this paper cites.
D. Coppersmith, D. Gamarnik, M. Hajiaghayi, and G. Sorkin,
2004
Earlier work this paper cites.
Dimitris Achlioptas, Assaf Naor, and Yuval Peres,
2005
Earlier work this paper cites.

Similar

Amin Coja-Oghlan, Cristopher Moore, and Vishal Sanwalani,
2006
Cited alongside, same era.
A. Bandyopadhyay and D. Gamarnik,
2008
Cited alongside, same era.
J. Díaz, L. Kirousis, D. Mitsche, and X. Pérez-Giménez,
2009
Cited alongside, same era.
A. Dembo and A. Montanari,
2010
Cited alongside, same era.
Rick Durrett,
2010
Cited alongside, same era.
R. Lyons and F. Nazarov,
2011
Cited alongside, same era.
Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, and Vlady Ravelomanana,
2012
Cited alongside, same era.

Then

A. Dembo, A. Montanari, and N. Sun,
2013
Later among the works it cites.
David Gamarnik and Madhu Sudan,
2014
Closest in time.
H. Hatami, L. Lovász, and B. Szegedy,
2014
Closest in time.
Russell Lyons,
Original
2014
Closest in time.
Mustazee Rahman and Balint Virag,
Original
2014
Closest in time.
Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág,
2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

M. Bayati, D. Gamarnik, and P. Tetali,

2013

Cited alongside, same era.

Amin Coja-Oghlan,

2013

Cited alongside, same era.

D. Aldous,

Cited in the paper.

A. Dembo, A. Montanari, and S. Sen,

2015

Closest in time.

J. Ding, A. Sly, and N. Sun,

2016

Closest in time.