Closeness of the two finite homomorphism densities

For a pattern graph F on k vertices and a host graph G on n vertices, the all-homomorphism density t(F, G) and the injective density t₀(F, G) satisfy

|homDensityFin F G - injHomDensity F G| ≤ (k.choose 2 : ℝ) / n.

The two densities count the same homomorphism events and differ only in how a vertex map V(F) → V(G) is drawn: with replacement (homDensityFin, denominator n ^ k) or without (injHomDensity, denominator (n)_k). Their gap is therefore bounded by the share of non-injective maps among all maps. A non-injective map repeats some value, so at most C(k,2) · n ^ (k - 1) of the n ^ k maps are non-injective, and dividing by n ^ k gives the bound. The same estimate is what pins the falling-factorial denominator of injHomDensity: it is the normalization that makes the injective density the unbiased estimator of the graphon homomorphism density under random sampling.

Main results

• homDensityFin_sub_injHomDensity_le — the closeness bound above, for an arbitrary finite host graph; the bound depends only on the cardinality of the host.

References

• L. Lovász, Large Networks and Graph Limits, §5.2.

theorem TauCeti.DenseGraphLimits.homDensityFin_sub_injHomDensity_le {V : Type u_1} {W : Type u_2} [Fintype V] [Fintype W] (F : SimpleGraph V) (G : SimpleGraph W) : |homDensityFin F G - injHomDensity F G| ≤ ↑((Fintype.card V).choose 2) / ↑(Fintype.card W)

The homomorphism density and the injective homomorphism density differ by at most C(k,2) / n, where k is the number of vertices of the pattern and n the number of vertices of the host, for every finite pattern and host graph.