Estimating global subgraph counts by sampling

DOI10.37236/11618zbMATH Open1520.60005arXiv2210.11336MaRDI QIDQ6162129FDOQ6162129

Authors: Svante Janson, Valentas Kurauskas

Publication date: 15 June 2023

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2210.11336

Recommendations

zbMATH Keywords

homomorphism combinatorial probability subgraph count

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05)

Cites Work

Cited In (4)

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)