1
$\begingroup$

Typical magnitude of $i$th largest eigenvalue of an Erdos-Renyi random graph seems to decay at least exponentially with $i$. Is there an analytic expression for the constant in the exponent, or a nice bound from above in terms of $i$? Any literature pointers appreciated!

enter image description here

edit plot was generated with the following Mathematica command

With[{n = 4000},
  Most@Rest@
    Reverse@Sort@
      Abs@Eigenvalues@
        N@Normal@
          AdjacencyMatrix@
           RandomGraph@BernoulliGraphDistribution[n, 0.5]
  ] // ListLogPlot[#, Filling -> Axis, 
   AxesLabel -> {"rank", "log(abs(magnitude))"}, 
   PlotLabel -> "Erdős\[Dash]Rényi"] &
Improve this question
$\endgroup$
2
  • $\begingroup$ Could you explain what you are plotting? $\endgroup$
    – Joseph O'Rourke
    Commented Jun 28, 2021 at 23:38
  • 1
    $\begingroup$ @JosephO'Rourke added the command used to make the plot. Basically plotting magnitude of i'th largest eigenvalue of random graph as a function of i, on log scale $\endgroup$
    – Yaroslav Bulatov
    Commented Jun 28, 2021 at 23:41

1 Answer 1

Reset to default
0
$\begingroup$

This shape is just the CDF of Wigner's semicircle law

enter image description here

notebook

Answered in https://math.stackexchange.com/a/4187243/998

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .