For any $n$-vertex graph $G$, we have the inequality $\lambda_i^{L_G}\geq D_i-i+2,$ where $L_G$ denotes the Laplacian of $G$ and $\lambda_i^{L_G}$ denotes the $i^\text{th}$ largest eigenvalue and $D_i$ is the $i^\text{th}$ largest degree of the vertices of $G$, provided $G$ is not the union of the complete graph $K_m$ and $n-m$ isolated vertices for any $m\leq n$. This theorem is due to Brouwer and Haemers (2008).

Consider a power-law partial correlation network (see Barigozzi et al. (2017) for the definition) and assume the conditions of Theorem 1. Let $\text{bad}$ be the event $G$ is the union of the complete graph $K_m$ and $n-m$ isolated vertices for some $m\leq n$. Why must we have $P(\text{bad})\leq\exp(-Cn^{\epsilon})$ for some positive constants $C$ and $\epsilon$? It is fine if you prove the bound only for all $n$ greater than some constant $N$. The authors of the paper do not justify this probability inequality in their proof (see bottom of $p.~14$), but I don't see how. They use this inequality along with $P(A\cup B)\geq P(A)+P(B)-1$ to prove another eigenvalue inequality (equation $(10)$ on $p.~15$) holds with high probability.

I have tried trying small cases, but I didn't get any results that apply to the general case (arbitrary $n$). I tried using Maclaurin's inequality for symmetric functions, but that didn't help. I have heard Janson's inequality is often useful in random graph problems, but I lack background in random graphs and do not know whether it can be applied here.

Brouwer, Andries E.; Haemers, Willem H., A lower bound for the Laplacian eigenvalues of a graph-proof of a conjecture by Guo, Linear Algebra Appl. 429, No. 8-9, 2131-2135 (2008). ZBL1144.05315.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.