Trace-moment comparison with Gaussian matrices

PDF p. 34: Proof of Proposition 6.3, trace comparison

Assume the Axiom of Choice for the adopted Gaussian-law construction. Let $n\ge 1$ and $\mathrm{\ell }\ge 1$ be integers, and let $0\le p\le 1$. Let $A$ be the adjacency matrix of the loop-free Erdős–Rényi graph $G(n,p)$, let $A^{\mathrm{\prime }}$ be an independent copy, and put $W=A-A^{\mathrm{\prime }}$ and $q=2p(1-p)$. Thus $W$ is symmetric, its diagonal is zero, and its entries above the diagonal are independent differences of independent Bernoulli$(p)$ variables. Let $G$ be the symmetric Gaussian comparator: its entries $G_{ij}$ for $i\le j$ are mutually independent standard real Gaussian variables, and $G_{ji}=G_{ij}$ for $i<j$.

For $u=(u_1,\dots ,u_{2\mathrm{\ell }})\in \{1,\dots ,n{\}}^{2\mathrm{\ell }}$ put $u_{2\mathrm{\ell }+1}=u_1$. Let ${\mathcal{C}}_{2\mathrm{\ell }}$ consist of those ordered tuples with $u_i\mathrm{\ne }{u}_{i+1}$ and with each unordered edge traversed an even number of times. For $u\in {\mathcal{C}}_{2\mathrm{\ell }}$, let $n_k(u)$ count its distinct unordered edges traversed exactly $k$ times, and put $r(u)={\sum }_{k\ge 1}{n}_k(u)$. Rotations and reversals are not identified unless they are equal as tuples. Write $\mathrm{Tr}M={\sum }_i{M}_{ii}$.

Then $1\le r(u)\le \mathrm{\ell }$ for every $u\in {\mathcal{C}}_{2\mathrm{\ell }}$, and

$\mathbb{E}\mathrm{Tr}{W}^{2\mathrm{\ell }}={\sum }_{u\in {\mathcal{C}}_{2\mathrm{\ell }}}{q}^{r(u)},q^{\mathrm{\ell }}\mathrm{\mid }{\mathcal{C}}_{2\mathrm{\ell }}\mathrm{\mid }\le \mathbb{E}\mathrm{Tr}{W}^{2\mathrm{\ell }}\le q\mathrm{\mid }{\mathcal{C}}_{2\mathrm{\ell }}\mathrm{\mid }\mathrm{.}$

Moreover, $\mathbb{E}\mathrm{Tr}{G}^{2\mathrm{\ell }}\ge \mathrm{\mid }{\mathcal{C}}_{2\mathrm{\ell }}\mathrm{\mid }$. Consequently $\mathbb{E}\mathrm{Tr}{W}^{2\mathrm{\ell }}\le q\mathbb{E}\mathrm{Tr}{G}^{2\mathrm{\ell }}$.

The article attributes the expansion and comparison to the passage cited above. Its displayed upper bound with $q^{\mathrm{\ell }}$ is reversed term by term: $r(u)\le \mathrm{\ell }$ and $0\le q\le 1$. The corrected upper bound here uses $q$; it does not imply the article's subsequent $q^{1\mathrm{/}2}$ norm estimate with the same power of $q$ after taking a $2\mathrm{\ell }$-th root.