Estimating Global Subgraph Counts by Sampling

Abstract

We give a simple proof of a generalization of an inequality for homomorphism counts by Sidorenko (1994). A special case of our inequality says that if $d_v$ denotes the degree of a vertex $v$ in a graph $G$ and $\textrm{Hom}_\Delta(H,G)$ denotes the number of homomorphisms from a connected graph $H$ on $h$ vertices to $G$ which map a particular vertex of $H$ to a vertex $v$ in $G$ with $d_v \ge \Delta$, then $\textrm{Hom}_\Delta(H,G) \le \sum_{v\in G} d_v^{h-1}\mathbf{1}_{d_v\ge \Delta}$.

We use this inequality to study the minimum sample size needed to estimate the number of copies of $H$ in $G$ by sampling vertices of $G$ at random.