Sandwiching random graphs: universality between random graph models |
| |
| Authors: | JH Kim |
| |
| Institution: | a Microsoft Research, Microsoft Corporation, Redmond, WA 98052, USA
b Department of Mathematics, University of California, San Diego, Gilman Drive 9500, La Jolla, CA 92093, USA |
| |
| Abstract: | The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n,p) and the random regular graph Gd(n). This connection appears to be very useful in deriving properties of one model from the other and explains why many graph invariants are universal. In particular, one obtains one-line proofs of several highly non-trivial and recent results on Gd(n). |
| |
| Keywords: | 05C80 60C05 74H50 |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
