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.
@article{10_37236_11618,
author = {Svante Janson and Valentas Kurauskas},
title = {Estimating global subgraph counts by sampling},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {2},
doi = {10.37236/11618},
zbl = {1520.60005},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11618/}
}
TY - JOUR
AU - Svante Janson
AU - Valentas Kurauskas
TI - Estimating global subgraph counts by sampling
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/11618/
DO - 10.37236/11618
ID - 10_37236_11618
ER -
%0 Journal Article
%A Svante Janson
%A Valentas Kurauskas
%T Estimating global subgraph counts by sampling
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11618/
%R 10.37236/11618
%F 10_37236_11618
Svante Janson; Valentas Kurauskas. Estimating global subgraph counts by sampling. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/11618
