Embedding theorems for random graphs with specified degrees

Abstract

Given an $n\times n$ symmetric matrix $W\in [0,1{]}^{[n]\times [n]}$, let $\mathcal{G}(n,W)$ be the random graph obtained by independently including each edge $jk$ with probability $W_{jk}$. Given a degree sequence $\mathbf{d}=(d_1,\dots ,d_n)$, let $\mathcal{G}(n,\mathbf{d})$ denote a uniformly random graph with degree sequence $\mathbf{d}$. We couple $\mathcal{G}(n,W)$ and $\mathcal{G}(n,\mathbf{d})$ together so that a.a.s. $\mathcal{G}(n,W)$ is a subgraph of $\mathcal{G}(n,\mathbf{d})$, where $W$ is some function of $\mathbf{d}$. Let $\Delta (\mathbf{d})$ denote the maximum degree in $\mathbf{d}$. Our coupling result is optimal when $\Delta (\mathbf{d}{)}^2\ll \Vert \mathbf{d}{\Vert }_1$, i.e.\ $W_{ij}$ is asymptotic to $\mathbb{P}(ij\in \mathcal{G}(n,\mathbf{d}))$ for every $i,j\in [n]$. We also have coupling results for $\mathbf{d}$ that are not constrained by the condition $\Delta (\mathbf{d}{)}^2\ll \Vert \mathbf{d}{\Vert }_1$. For such $\mathbf{d}$ our coupling result is still close to optimal, in the sense that $W_{ij}$ is asymptotic to $\mathbb{P}(ij\in \mathcal{G}(n,\mathbf{d}))$ for most pairs $i,j\in [n]$.

References in corpus (2)

• Complex martingales and asymptotic enumeration
• Embedding the Erdős-Rényi Hypergraph into the Random Regular Hypergraph and Hamiltonicity