In 1982, B. Bollobas and Vega in the paper gave the configurational model to generate $r$-regular random graphs. They gave the following theorem (Theorem 1 in the paper).

Theorem: Let $r\geq 3$ and $\epsilon> 0$ be fixed and define $d=d(n)$ as the least integer satisfying $$(r-1)^{d-1}\geq (2+\epsilon)rn \ \text{log} \ n.$$ Then almost every $r$-regular graphs of order $n$ has diameter at most $d$.

I have following two questions

Question 1. Does this theorem implies that the diameter of $r$-regular random graphs is of order $\text{log} (n \text{log} n),$ that is, $d(n)=O(\text{log} (n \text{log} n))$?

Question 2. If Question 1 is true, will all the $r$-regular random graphs (not necessary generated using the configuration model) has the diameter of order $\text{log} (n \text{log} n).$

  • $\begingroup$ I think random regular graphs are expanded, so should have diameter O(log(n)). But I don’t know if there is a model for regular random graphs in which they are not expanders. $\endgroup$ – Ian Agol Jul 10 at 23:26
  • $\begingroup$ Yes Friedman proved that all the large enough random regular graphs tend to be Ramanujan graphs, which are the best possible expanders. So maybe these expanders does not satisfy the above theorem. $\endgroup$ – Ranveer Singh Jul 11 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.