Matching flexibility and existing-solver certificate feasibility

This edition extends the table-law and accelerated-matching exclusions. The source FPRAS claims remain unverified independently. Bounded references and observed existing-solver integrations provide separate finite evidence.

Perfect-matching count schedules

In family 113's nonempty general routine, K is the least positive integer satisfying n^(n/2)*(1+1/n)^(-K)<=epsilon/32. It then sets p=2K+2, N=n+4p*binom(n,2), D0=10^8(n+1)^4, D=100N^2D0, sigma=min(1/(10^7D),epsilon/(1000K)) and S=ceil(10 sigma^-2(n+K+1)). At n=2, epsilon=1/10, delta=1/20, the exact calculation gives K=16, N=138, D=15425640000000000, 61 median trials and approximately 4.52*10^48 fresh sampler runs per stage. Each run still invokes the replicated-chain sampler.

This is the declared literal schedule, not a runtime benchmark or lower bound on every algorithm. Empty/infeasible returns occur before it, and useful special cases can be solved differently. The exact parameter record also includes four- and eight-vertex calculations. Source schedule/statistics.

The entropy companion's deterministic counter returns N/512^n<=A<=N. Its multiplicative width is exponential in vertex count, and its introduction explicitly describes a large polynomial degree rather than practical performance. Pointwise maximum-entropy bounds require feasible marginals in the matching polytope; degree equations alone are insufficient on general graphs. The sharp global face-dimension statement is outside the selected formal scope. Companion introduction.

Exact bounded flexibility reference

perfect_matching_reference.py implements conventional subset dynamic programming on a simple unweighted graph, capped at 24 vertices, 200,000 memo states and one million subset/branch work units. It counts labeled perfect pairings, maps supplied ranks to distinct matchings, and computes edge-containing counts by removing the edge's two endpoints. The surviving count after forbidding an edge is the total minus its containing count. A zero count has no uniform marginal law; the report leaves such fractions undefined.

Unknown count status is distinct from proved zero. Partial sensitivity retains a completed count and clearly marks incomplete edge results. The utility passed 93 finite checks against independent edge-subset enumeration and formulas. The two-triangle example has one perfect pairing and three forced edges. This reference supplies a small benchmark and fragility report, not the source FPRAS, an arbitrary-size sampler, plan-quality optimization or demand evidence.

Solver proposals with separately checked certificates

solve_and_audit_matching.py calls NetworkX with integer unit weights and maximum cardinality, then checks the returned edges and an attaining upper bound using the separate graph auditor. If the initial bound is loose, repeated vertex-deletion solves propose D and S=N(D) minus D; any supplied subset still yields a valid bound, and only attainment grants the certificate. A capped or loose proposal can remain unknown. Inputs above 256 vertices, weighted/extra objectives and malformed graphs are rejected. At most 257 solver calls are permitted; this is not a runtime deadline.

These are one-run local stage measurements with NetworkX 3.4.2, excluding module imports, file read, JSON serialization and write. They are not stable performance estimates or end-to-end deployment benchmarks. The public social graph's interaction weights and node attributes were explicitly discarded for the unweighted problem; it is not a customer allocation dataset. All three candidates attained independently checked bounds. Full saved integration, 72 additional checks, public graph documentation, solver documentation.

Environment and commercial consequence

The optional local SciPy runtime check failed because a compiled extension could not load (__DATA/__thread_bss zero-fill offset error). No global package repair was performed. The table-law comparison in the prior edition uses exact factorial fractions and official implementation documentation, so it does not depend on that failed runtime check. Do not claim a SciPy runtime validation from these records.

Defer the literal perfect-matching FPRAS alongside the two earlier research backends. Existing-solver certificate integration and bounded exact fragility analysis are concrete engineering components. They need a realistic constraint mapping, useful planning decision and reusable delivery process before a lucrative product claim is justified. No source-proof check, buyer interview or paid pilot has happened.