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
    Commented Aug 7, 2020 at 2:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .