2022/10/20 by Svante Janson, Janson, Svante, Valentas Kurauskas +1
Mathematics · #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2210.11336
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 dv denotes the degree of a vertex v in a graph G and \textrmHomΔ(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 dv ≥ Δ, then \textrmHomΔ(H,G) ≤ ∑v∈ G dvh-11dv≥ Δ 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.