Skip to main content
added 427 characters in body
Source Link
alef
  • 46
  • 1
  • 2

For Random 3-regular graphs \lambda is asymptotically 1. I suspect that for Ramanujan graphs it will be 1 as well?

Regarding random graphs papers to look are papers citing Bollobas and de la Vega, Combinatorica 2 (1982), 125-134. http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf which does not contain it but a related result.

A reference which contains the claim is Remco van der Hofsted's book: see Theorem 10.15 and Theorm 10.16 (in the latest version on his webpage).

For Random 3-regular graphs \lambda is asymptotically 1. I suspect that for Ramanujan graphs it will be 1 as well?

For Random 3-regular graphs \lambda is asymptotically 1. I suspect that for Ramanujan graphs it will be 1 as well?

Regarding random graphs papers to look are papers citing Bollobas and de la Vega, Combinatorica 2 (1982), 125-134. http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf which does not contain it but a related result.

A reference which contains the claim is Remco van der Hofsted's book: see Theorem 10.15 and Theorm 10.16 (in the latest version on his webpage).

Source Link
alef
  • 46
  • 1
  • 2

For Random 3-regular graphs \lambda is asymptotically 1. I suspect that for Ramanujan graphs it will be 1 as well?