Estimating global subgraph counts by sampling

DOI10.37236/11618MaRDI QIDQ6162129zbMATH OpenFDO

Authors Svante Janson, Valentas Kurauskas

Publication date 15 June 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

homomorphism combinatorial probability subgraph count

Mathematics Subject Classification ID

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

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.

Recommendations

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)