Exact prescribed-pair probability for block-preserving perfect matchings
ProvedQuantumBipartiteTesting.Bipartiteness.uniform_block_matching_containsfinite-probabilityperfect-matchingquantum-query-complexity
Let and let be even. Partition labeled vertices into canonical blocks of size . For each block , prescribe a partial matching of disjoint, nonloop pairs in that block. If is uniform among fixed-point-free involutions preserving every block, then
This supplies the exact independent-block matching probability used in the hidden-block graph sampling law. Empty blocks and empty partial matchings follow the stated finite-sum conventions.
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open QuantumBipartiteTesting.Bipartiteness Finset open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.uniform_block_matching_contains (l s : ℕ) (hl : 0 < l) (hs : Even s)
(E : Fin l → Finset (Sym2 (Fin s)))
(hloop : ∀ j, ∀ p ∈ E j, ¬ p.IsDiag)
(hdisj : ∀ j, ∀ p ∈ E j, ∀ q ∈ E j, (∃ x, x ∈ p ∧ x ∈ q) → p = q) :
Average (Matchings (l*s) l) (fun h =>
if ∀ j a b, s(a,b) ∈ E j → h (finProdFinEquiv (j,a)) = finProdFinEquiv (j,b) then (1:ℝ) else 0) =
∏ j, ∏ a ∈ range (E j).card, ((s:ℝ)-2*a-1)⁻¹ := by sorrySource
Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, §2.5.1 hidden-block matching distribution and Appendix A.2, printed p.30, probability R_d and product (A.2).