2
$\begingroup$

I would like to know when an ER graph is locally treeing like. In this post. I found this comment:

I think $N$ is $\log2|V|$, or something like that, in that paper. They consider binary vectors of length $N$. Furthermore, "most" sparse graphs have logarithmic diameter (say, random regular graphs of constant degree $d\geq3$, or the giant component of Erdos-Rényi random graphs with $p=\frac{c}{n}$ and $c>1$ a constant), rather than linear.

Where can I found this result about ER graphs?

$\endgroup$
3
  • $\begingroup$ Did you look into any book on random graphs? $\endgroup$
    – Boris Bukh
    Oct 13, 2016 at 14:18
  • 1
    $\begingroup$ @BorisBukh I'm reading: van der Hofstad. Random Graphs and Complex Networks, 2016. win.tue.nl/~rhofstad/NotesRGCN.html. And I haven't found it. $\endgroup$
    – fdesmond
    Oct 13, 2016 at 15:56
  • 4
    $\begingroup$ I was not familiar with the book, and I concede the point: that book does analyze the giant component in a way from which it is impossible to extract the bound on the diameter. (Since it analyzes the complement of the giant component). Have a look at Theorem 10.19 in Bollobas's book on random graphs. It should also be contained in Janson-Luczak-Rucinski, but I do not have it handy. $\endgroup$
    – Boris Bukh
    Oct 13, 2016 at 17:35

1 Answer 1

1
$\begingroup$

it has to do with the clustering coefficient.

See the bottom of page 5 here:

https://aaronclauset.github.io/courses/3352/csci3352_2021_L3.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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