Homomorphism densities of samples from an exchangeable graph law

The level-m marginal of an exchangeable graph law L is a random m-vertex graph. This file compares the mean homomorphism densities of such a sample with the upper masses of L. The injective density is exact: by consistency of L, each of the (m)_k vertex embeddings of a k-vertex pattern F sees the pattern with probability upperMass F, so E[t₀(F, G)] = upperMass F whenever k ≤ m. The ordinary density differs from it by at most C(k, 2) / m, the union bound on the proportion of non-injective vertex maps.

Main results

• TauCeti.DenseGraphLimits.ExchangeableGraphLaw.integral_injHomDensity_law — the injective homomorphism density of a sample from an exchangeable graph law is an unbiased estimator of the upper mass;
• TauCeti.DenseGraphLimits.ExchangeableGraphLaw.abs_integral_homDensityFin_law_sub_upperMass_le — the mean ordinary homomorphism density of a sample is within C(k, 2) / m of the upper mass.

References

• P. Diaconis, S. Janson, Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7) 28 (2008), 33--61, Section 5.
• C. Freer, cameronfreer/graphon at commit 6eccca5bbe5c9df46d7129bf59575b8b9b1d6699, Apache-2.0, Graphon/MixtureExistence.lean. The collision estimate follows its existence argument.

theorem TauCeti.DenseGraphLimits.ExchangeableGraphLaw.integral_injHomDensity_law (L : ExchangeableGraphLaw) {k m : ℕ} (F : SimpleGraph (Fin k)) (hkm : k ≤ m) : ∫ (G : SimpleGraph (Fin m)), injHomDensity F G ∂L.law m = L.upperMass F

Unbiasedness of the injective density. The injective homomorphism density of a pattern in a sample from an exchangeable graph law is an unbiased estimator of the pattern's upper mass, provided the sample has at least as many vertices as the pattern: by consistency of the law, each vertex embedding of the pattern sees it with probability equal to the upper mass.

theorem TauCeti.DenseGraphLimits.ExchangeableGraphLaw.abs_integral_homDensityFin_law_sub_upperMass_le (L : ExchangeableGraphLaw) {k m : ℕ} (F : SimpleGraph (Fin k)) (hm : 0 < m) : |∫ (G : SimpleGraph (Fin m)), homDensityFin F G ∂L.law m - L.upperMass F| ≤ ↑(k.choose 2) / ↑m

Near-unbiasedness of the ordinary density. The mean ordinary homomorphism density of a k-vertex pattern in an m-vertex sample from an exchangeable graph law is within C(k, 2) / m of the pattern's upper mass. The bound holds for every positive sample size, and is informative only when k ≤ m, since C(k, 2) / m ≥ 1 once k > m.