Changing a host graph at one vertex

If two host graphs on the same finite vertex set W agree on every pair of vertices avoiding a fixed vertex w, then their homomorphism densities of a pattern F differ by at most |V(F)| / |W|.

A vertex map V(F) → W whose range avoids w preserves adjacency into one host exactly when it preserves adjacency into the other, so only the maps whose range meets w can change status. A union bound over the vertex of F sent to w counts at most |V(F)| · |W| ^ (|V(F)| - 1) such maps among the |W| ^ |V(F)| in total.

This is the bounded-differences estimate for the ordinary homomorphism density: in a sampled graph where resampling one vertex only changes the pairs at that vertex, it bounds the effect of the resampling on the estimator.

Main results

• SimpleGraph.abs_homDensityFin_sub_le_of_adj_iff — the oscillation bound above.

References

• L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), §10.1.

theorem SimpleGraph.abs_homDensityFin_sub_le_of_adj_iff {V : Type u_1} {W : Type u_2} [Fintype V] [Fintype W] (F : SimpleGraph V) {G G' : SimpleGraph W} (w : W) (h : ∀ (a b : W), a ≠ w → b ≠ w → (G.Adj a b ↔ G'.Adj a b)) : |TauCeti.DenseGraphLimits.homDensityFin F G - TauCeti.DenseGraphLimits.homDensityFin F G'| ≤ ↑(Fintype.card V) / ↑(Fintype.card W)

Oscillation of the homomorphism density at one vertex. If two host graphs agree on every pair of vertices avoiding w, the homomorphism densities of F in them differ by at most |V(F)| / |W|: only the vertex maps meeting w can distinguish the two hosts.