MathIdeasResearch in progressRepository ↗
← Research catalogOriginal Markdown ↓
On this page

Perfect-pairing fragility and flexibility analyzer

Edition: 9 October 2026 Australia/Brisbane. Decision: Prototype bounded exact diagnostics; defer the literal FPRAS backend. Buyer value and profitability remain hypotheses.

Research finding

Family 113 claims an FPRAS for the number of perfect matchings in every finite simple unweighted undirected graph. It returns zero with certainty on infeasible input and has worst-case polynomial bit time on every random tape. Its companion paper bounds maximum entropy at feasible matching marginals and gives a deterministic count approximation between N/512^n and N. That exponential factor is not fixed relative-error accuracy. The selected formal scope covers the FPRAS and entropy/count statements but excludes the sharp global face-dimension bound; no independent proof check was run.

Problem and buyer

A small pairing planner may find one perfect allocation while missing that every feasible allocation depends on a particular compatibility edge. The proposed workflow reveals forced edges, forbidden edges that can never appear in a perfect pairing, and the exact number of plans surviving a single edge failure. A research group could also use it as a bounded reference for a new approximate counter. A buyer must already have a recurring planning decision where those diagnostics change action.

What the finding could enable

A practical approximate counter could extend flexibility comparisons to general graphs beyond exact enumeration. The literal source schedule is currently unsuitable as a production backend. The implemented capability is a conventional small-graph exact counter, rank-to-matching replay and edge-failure sensitivity. The identity count(containing uv)=count(G-{u,v}) gives edge marginals under a uniform perfect-pairing law and counts surviving deletion of that edge. These diagnostics are classical consequences of exact enumeration, not new mathematics from the repository.

Technical and commercial limits

The source chooses D0=10^8(n+1)^4, p=2K+2, N=n+4p*binom(n,2), D=100N^2D0, sigma=min(1/(10^7D),epsilon/(1000K)) and S=ceil(10 sigma^-2(n+K+1)) fresh sampler runs per stage. At n=2, epsilon=1/10, delta=1/20, the literal nonempty general routine has K=16, N=138, and roughly 4.52*10^48 runs per stage, before replicated-chain work. Empty/infeasible branches are separate; this does not rule out a redesigned practical method or efficient special cases.

The finite reference caps vertices at 24, memo states at 200,000 and count-work units at one million. It can exhaust its budget earlier. Counting exhaustion returns unknown with no count; sensitivity exhaustion preserves the completed count and visibly partial edge results. Work units are subset evaluations and partner branches, not bit operations or a wall-time guarantee. It counts labeled simple-graph unweighted perfect pairings. Weights, fairness, quotas and multiway tasks require separate models. A high count does not prove resilience to simultaneous failures or good operational outcomes. Source sampling corollaries give total-variation approximation, not exact general sampling.

Minimal architecture

Validated pairing constraints -> bounded simple graph -> exact count and optional rank replay -> forced/unused-edge and single-edge survival report -> planner review. Larger graphs need an independently assessed approximate backend with recorded error/confidence and cost. Keep model constraints, arithmetic limits, unknown states and the implementation revision in the evidence report.

Existing alternatives and differentiation

NetworkX can produce maximum-cardinality matchings; optimizers support broader assignment constraints. Returning another feasible plan alone adds little. Differentiation requires a useful disruption decision or reference validation that existing solver reports omit. The exact prototype and existing-solver certificate adapter complement one another, but cover different size/objective limits. NetworkX API, Gurobi licensing.

Monetization hypothesis

Hypothesis: AUD 3,000–8,000 for a bounded disruption-analysis integration. At an assumed AUD 6,000 fee and 25 specialist hours at AUD 180/hour, AUD 1,500 remains before sales, support and overhead; 35 hours exceed the fee. A recurring license needs repeated scenarios and reusable model adapters. This overlaps allocation dossier 007 and the shared assurance platform; do not add overlapping prices as independent customer revenue.

Validation experiment

The exact utility passed 93 checks: all 64 four-vertex graphs, 16 seeded six-vertex cases, independent edge-subset enumeration, count/rank coverage, edge inclusion/deletion identities, a complete-graph formula, invalid inputs and budget semantics. A two-triangle graph joined by one bridge has one perfect pairing and three forced edges. This is finite component evidence, not a source-FPRAS implementation, a realistic buyer workload or proof that the report improves decisions. Next compare decisions before/after this report on a public planning-shaped dataset, explicitly accounting for omitted real-world constraints.

Conditions to reject or defer

Defer the literal FPRAS until practical constants are reduced and benchmarked. Reject a paid integration if required constraints leave the graph model, graph size routinely exceeds useful exact limits, or forced-edge/count information does not change the buyer's planning action. Reject subscription assumptions if maintaining bespoke adapters consumes the fee. Entropy bounds require feasible marginals, including odd-cut constraints; merely assigning row sums is insufficient.

Next concrete action

Run perfect_matching_reference.py on the two-triangle fixture, then prepare one disruption experiment using a public technical dataset. Continue inspecting source sampler reductions separately from this bounded reference. Preserve exact failure/confidence semantics for any future approximate backend.

Source evidence