Adversarial checks of the Möbius calculus and the dissociation bridge #
The random graph L_f attached to a graph parameter f rests on three facts about the Möbius
masses f† — nonnegativity, total mass one, and consistency along label injections — and on the
bridge isDissociated_iff_upperMass_mul between dissociation and multiplicativity of upper
masses. The examples here compute the Möbius masses explicitly for a family of parameters, use
them to exhibit a parameter that is not reflection positive although it satisfies the other
structural conditions, and exhibit an exchangeable law that is not dissociated.
The edge-power parameters. For a real c, the parameter F ↦ c ^ e(F) is isomorphism
invariant, multiplicative and normalized; for c ∈ [0, 1] it is the homomorphism density of the
constant graphon c. Its Möbius transform is computed in closed form by the binomial theorem,
f†(F) = c ^ e(F) * (1 - c) ^ (C(n, 2) - e(F)): these are the binomial masses of the Erdős–Rényi
graph G(n, c). On Fin 2 with c = 2 they are -1 at the
edgeless graph and 2 at the edge. So the masses still sum to one and still restrict
consistently to Fin 1 — the identities graphParamMobius_sum_eq_one and
graphParamMobius_sum_comap, which do not assume reflection positivity — but they are not
nonnegative, and posSemidef_connectionMatrix_fullyLabeled_iff then shows that this parameter
is not reflection positive. Reflection positivity is therefore independent of the other three
structural conditions (exists_not_isReflectionPositive).
A law that is not dissociated. The exchangeable graph law which, at every level, is the
complete or the edgeless graph with probability 1 / 2 each is not dissociated: its edges in two
disjoint windows are perfectly correlated. Both sides of the bridge are computed directly: the two
windows of Fin (2 + 2) are never the edgeless graph and the edge, which has probability 1 / 4
under the product law; and the pattern of two disjoint edges has upper mass 1 / 2, not
1 / 2 * 1 / 2.
Main results #
TauCeti.DenseGraphLimits.exists_not_isReflectionPositive— an isomorphism-invariant, multiplicative, normalized graph parameter need not be reflection positive.
References #
- L. Lovász, B. Szegedy, Limits of dense graph sequences, JCTB 96 (2006), 933–957, Section 2.
- P. Diaconis, S. Janson, Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7) 28 (2008), 33–61, Section 5.
The edge-power parameters #
Reflection positivity is independent of the other structural conditions. The parameter
F ↦ 2 ^ e(F) is isomorphism invariant, multiplicative and normalized, but its Möbius mass at the
edgeless graph on Fin 2 is -1, so its connection matrix on the fully labeled graphs on Fin 2
is not positive semidefinite.