3
$\begingroup$

I find the theorem for largest eigenvalue of the adjacency matrix of ER random graph in here https://arxiv.org/pdf/math/0106066.pdf. The adjacency matrix is a symmetric random matrix s.t. diagonal values are all fixed as 0, and all entries above the diagonal are i.i.d. Bernoulli($p$) random variables, for some fixed $p\in[0,1]$.

enter image description here

For a weighted random graph, each edge in the adjacency matrix is represented by decimal in $[0,1]$ drawn from a uniform distribution over $[0,1]$ (or possibly other distribution over $[0,1]$). The adjacency matrix is a symmetric random matrix s.t. diagonal values are all zero, and every entry above the diagonal is drawn uniformly at random from $[0,1]$.

My question is,

Is there similar known result about the largest eigenvalue for weighted random graph?

$\endgroup$
3
$\begingroup$

The question is not completely clear. Do you fix a random $G(n,p)$ and then replace the $1$ in the adjacency matrix by a uniform random variable? Or is it as you write at the end, namely you just take a matrix with iid uniform entries (except for the symmetry constraint)?

If $p$ is of order one, or if the second interpretation is correct, then the top eigenvalue concentrates near $n EW$ where $W$ is the edge weight (so $EW=p/2$ in the first model and $EW=1/2$ in the second). See the answer to Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s

If you are dealing with the first model and $p=p(n)\to 0$ but $pn\to\infty$, the situation I believe is similar but requires more work to be proved.

$\endgroup$
1
$\begingroup$

When $p$ is reasonably large, you are basically looking at a random symmetric matrix, so any insight would come from the Tracy-Widom theory.

$\endgroup$
  • $\begingroup$ Not quite, there is a shift in mean. $\endgroup$ – ofer zeitouni Jan 16 '18 at 7:04
  • $\begingroup$ @oferzeitouni Yes, I know, which is why I phrased it in a more cautious way... $\endgroup$ – Igor Rivin Jan 16 '18 at 13:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.