论文标题
通过采样来估计全局子图计数的注释
A note on estimating global subgraph counts by sampling
论文作者
论文摘要
我们简单地证明了Sidorenko（1994）对同态数量不平等的概括。我们不平等的特殊情况说，如果$ d_v $表示图表$ g $中的顶点$ v $和$ \ textrm {hom}_Δ（h，g）$表示来自$ h $ g $ g $ g $ g $ g $ g $ h $ g $ h $ h $ g $ h $ h $ h $ h $ h $ h $ h $ h $ g $ h $ h $ h $ g $ h $ h $ h $ h $ h $ h $ h $ g $ h $ h $ h $ h $ h $ h $ h $ f os y n $ h $ δ$，然后$ \ textrm {hom}_Δ（h，g）\ le \ sum_ {v \ in G} d_v^{h-1} \ mathbf {1} _ {d_v \geδ} $ 我们使用这种不平等来研究估算$ g $ $ h $ g $ $ h $ g $的副本数量所需的最低样本量，并随机对$ g $采样。
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}_Δ(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 Δ$, then $ \textrm{Hom}_Δ(H,G) \le \sum_{v\in G} d_v^{h-1}\mathbf{1}_{d_v\ge Δ} $ 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.
