A note on estimating global subgraph counts by sampling
| Autor: | Janson, Svante, Kurauskas, Valentas |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 8 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|