Möbius matching moments have the predicted homogeneous factor
ProvedQuantumBipartiteTesting.Bipartiteness.matching_mobius_factorizationmobius-inversionpolynomial-methodquantum-query-complexity
Let be nonnegative integer counts on labeled components and finitely many colors, with total count . For a partition , put
Write and . For each partition , there is a real bivariate polynomial of total degree at most such that, whenever and ,
Here is the partition Möbius coefficient defined by signed refinement chains. This count-matrix identity supplies the cancellation needed to extract the cycle-rank power in graph topology moments, and also applies to other finite color sets.
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open QuantumBipartiteTesting.Bipartiteness Finset open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.matching_mobius_factorization {k colors : ℕ} (d : Fin k → Fin colors → ℕ) (q : ℕ)
(he : (∑ i, ∑ j, d i j) ≤ 2*q) (p : Partition k) :
∃ H : Bivariate, H.totalDegree ≤ DenominatorDegree q ∧
∀ M l : ℝ, l ≠ 0 → Eval (Denominator q) M l ≠ 0 →
(∑ r : Partition k, if Refines r p then (Mobius r p:ℝ) *
(∏ S ∈ Blocks r, ∏ j : Fin colors, MatchingMoment (∑ i ∈ S, d i j) M l) else 0) =
l^((∑ i, ∑ j, d i j)+k-(Blocks p).card) * Eval H M l / Eval (Denominator q) M l := by sorrySource
Ambainis–Childs–Liu, Quantum Property Testing for Bounded-Degree Graphs, https://arxiv.org/pdf/1012.3174, Proposition 6, printed pp.8–9 and Appendix C.5, pp.19–21. Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, Appendix A.2, equations (A.5)–(A.7), pp.30–31. This states the component-count form with an arbitrary finite color set.