3
$\begingroup$

There are some properties that are easily studied for random d-regular graphs, but that are very hard to extend to random graphs with a given degree sequence (e.g. whether a graph is w.h.p. hamiltonian).

Does anyone have any other examples of papers/problems that successfully (and not trivially) extend properties from random regular graphs to random graphs with a given degree sequence?

(I hope this is not too open ended, I am finding it hard to search online the usual way because the key words are so generic).

$\endgroup$

1 Answer 1

1
$\begingroup$

Simple random walk (and non-backtracking walk) on random regular graphs exhibit the cutoff phenomenon [1]. The extension to graphs with degree sequences came later; see [2] for nonbacktracking walks and [3] for simple random walk where backtrackings cause additional difficulties.

In another direction, component structure at criticality was described in a well known paper by Aldous [4]. It was adapted to random regular graphs in [5], and extended to other degree sequences in [6] and [7].

References:

[1] Lubetzky and A. Sly, Cutoff phenomena for random walks on random regular graphs. Abstract Duke Mathematical Journal 153 (2010), no. 3, 475–510.

[2] Ben-Hamou, Anna, and Justin Salez. "Cutoff for nonbacktracking random walks on sparse random graphs." The Annals of Probability 45, no. 3 (2017): 1752-1770.

[3] N. Berestycki, E. Lubetzky, Y. Peres and A. Sly, Random walks on the random graph. Annals of Probability 46 (2018), no. 1, 456–490.

[4] Aldous D. (1997), Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25, 812–854.

[5] Nachmias, Asaf, and Yuval Peres. "Critical percolation on random regular graphs." Random Structures & Algorithms 36.2 (2010): 111-148.

[6] Bhamidi, Shankar, Remco Van Der Hofstad, and Johan van Leeuwaarden. "Scaling limits for critical inhomogeneous random graphs with finite third moments." Electronic Journal of Probability 15 (2010): 1682-1702.

[7] Riordan, O. "The phase transition in the configuration model." Combinatorics, Probability and Computing 21 (2012), 265--299 21, no. 1-2 (2011).

$\endgroup$
1
  • $\begingroup$ Thank you, this is very helpful! $\endgroup$
    – DJA
    Aug 7, 2020 at 2:46

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.