| Title |
Estimating global subgraph counts by sampling / |
| Authors |
Janson, Svante ; Kurauskas, Valentas |
| DOI |
10.37236/11618 |
| Full Text |
|
| Is Part of |
Electronic journal of combinatorics.. Newark : Electronic journal of combinatorics. 2023, vol. 30, iss. 2, art. no. P2.24, p. [1-9].. ISSN 1077-8926 |
| Abstract [eng] |
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. |
| Published |
Newark : Electronic journal of combinatorics |
| Type |
Journal article |
| Language |
English |
| Publication date |
2023 |
| CC license |
|
