Estimating global subgraph counts by sampling

Abstract: 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

e x t r m {H o m}_{D} e l t a (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} g e D e l t a

, then

e x t r m {H o m}_{D} e l t a (H, G) l e s u m_{v i n G} d_{v}^{h - 1} m a t h b f 1_{d_{v} g e D e l t a}

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.

Review text

This paper studies estimation of global subgraph counts through sampling. Given two graphs \(H\) and \(G\), let \(\mathrm{Hom}(H,G)\) be the set of homomorphisms. If \(H\) is a rooted graph with root \(o\) and \(\Delta\ge0\), let \(\mathrm{hom}_{\Delta}(H,G)\) be the number of homomorphisms, say \(\varphi\), from \(H\) to \(G\) such that the degree of the vertex \(\varphi(o)\ge\Delta\). It is shown that for any connected rooted graph \(H\) on \(h\ge1\) vertices, any graph \(G\) and \(\Delta\ge0\), it holds that \(\mathrm{hom}_{\Delta}(H,G)\le\sum_{v\in G}d_v^{h-1}1_{d_v\ge\Delta}\), where \(d_v\) the degree of \(v\).

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Estimating global subgraph counts by sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6162129)