# Direct-candidate feasibility: schedules, laws and solver certificates

This edition adds explicit construction findings for families 115 and 120 to the [earlier parameter exclusions](FEASIBILITY-2026-10-09-v1.md). The source results remain claims at the pinned revision; no independent proof check was run. The calculations below are derived from stated schedules and guards, not observed runtimes or a proof that no practical variant could exist.

## Fixed-margin tables: the literal schedule is a complexity result

The sampler sets `d=10+(m+1)(n+1)`, `L=d^12`, `U=d^20`, `C=N+dL+U+2` and `b=d+ceil(log2(C+2))`. Its bounded outer routine chooses `T=d^200(k+b)^2` transitions per trial and caps trials at `d^4(k+1)`. The exact version chooses `D=d^6 b^2`, accuracy `k=2D`, and a correction branch with probability `2^-D`. That branch exhaustively tabulates the implemented law; its extremely small probability controls expected cost. It does not provide a deadline bound on every exact-sampling execution.

For the two-by-two margins `[2,2]` and `[2,2]`, the literal outer schedule already has hundreds of decimal digits in its transition count, before charging a transition's dense-completion work. The general sampler has no cell bounds; the separate cell-bounded paper provides approximate counting and explicitly emphasizes complexity over practical runtime. No production crossover has been demonstrated.

[Parameter definitions](../source/openai-math/preprints/Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026/build/sections/model-and-graph.tex), [sampling and exact correction](../source/openai-math/preprints/Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026/build/sections/algorithms.tex), [cell-bounded scales](../source/openai-math/preprints/An-FPRAS-for-Cell-Bounded-Contingency-Tables-September-24-2026/build/sections/scales.tex), [selected scope](../source/openai-math/lean/docs/115.md).

## Uniform tables and conditional independence are different laws

SciPy's `random_table` is designed for the fixed-margin conditional independence distribution and offers Boyett/Patefield generation. Its probability implementation uses `product(row!)*product(column!)/(total!*product(cell!))`. It does not give each integer table equal probability. [SciPy documentation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.random_table.html), [versioned probability implementation](https://github.com/scipy/scipy/blob/v1.18.0/scipy/stats/_multivariate.py).

With two-by-two margins `[2,2]`, there are three tables, indexed by the top-left cell `0,1,2`. Uniform-table probabilities are each `1/3`. Conditional-independence probabilities are `1/6, 2/3, 1/6`. The exact total-variation distance is `1/3`; the probability of the two extreme tables is `2/3` under the uniform law and `1/3` under conditional independence. This difference is a model choice, not a flaw in the existing statistical sampler. A uniform-table engine must not silently replace an independence-test sampler.

The [saved law comparison](snapshots/2026-10-08-baseline/contingency-law-contrast-2026-10-09-v1.json) uses exact fractions. The [new finite reference](tools/contingency_reference.py) counts every feasible table once and un-ranks a supplied integer into a table, also respecting explicit cell bounds. Uniform rank selection maps to uniform tables. It is a conventional bounded dynamic program, capped at dimension six, total 128 and work/state budgets; it does not implement the new polynomial-bit backend. Budget exhaustion returns unknown rather than zero. Recorded ranks permit exact replay of generated examples.

## General matching: an astronomical prerequisite for the literal backend

The uniform program uses accelerated branches indexed by `t>=1`, with `a=1000+t`, and a deterministic fallback. In the cycle backend, `M=2^u`, `b=M^(1/a^2)`, `Lambda=2^(1000a^2)(1+u)`, and `P_star=Lambda^(400a^2)`. The mandatory check `P_star<=b`, together with `M<=S^2`, implies

```text
u/a^2 >= log2(P_star) >= 400000 a^4
u >= 400000 a^6
log2(S) >= u/2 >= 200000 a^6.
```

At the first accelerated branch, `a=1001`. This is an astronomical necessary master-size condition before that backend can pass its first guard. It is not a sufficient threshold; other checks are stronger. Early structural completions, local easy cases and the deterministic fallback may still terminate. The derivation does not disprove the asymptotic theorem, establish an input-size threshold from an unspecified big-O constant, or exclude a substantially redesigned practical variant.

The source's common exponent envelope is defined through a supremum over actual instruction counts, rather than supplied as a numerical crossover estimate. A literal general-purpose implementation therefore lacks a defensible commercial speedup claim. [Backend parameters and guards](../source/openai-math/preprints/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026/build/sections/07-backend-quality.tex), [uniform branches and schedule](../source/openai-math/preprints/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026/build/sections/09-uniformization.tex).

## What can be implemented now for allocation workflows

The [matching certificate audit](tools/audit_matching_certificate.py) checks an unweighted candidate and an explicit vertex subset `S`. If `q` is the number of odd components after removing `S`, at least `q-|S|` vertices must remain unmatched: each odd component needs an outside match or an unmatched vertex, and at most `|S|` components can consume vertices in `S`. Hence every matching has at most `(n-q+|S|)/2` edges, also at most `floor(n/2)`.

A feasible matching attaining either checked bound is maximum cardinality. A loose bound is inconclusive, so the utility preserves unknown optimality instead of rejecting a potentially maximum matching. This is a classical certificate component, not the paper's new solver or a barrier constructor. Weighted objectives, fairness and other allocation constraints need their own model and evidence. NetworkX already offers a blossom-based matcher with a maximum-cardinality option; it is a baseline rather than proof of a new market gap. [NetworkX API](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.max_weight_matching.html).

## Saved evidence and earning consequence

[Exact schedule/guard calculations](snapshots/2026-10-08-baseline/direct-candidate-parameters-2026-10-09-v1.json) record formulas and source locations. [Contingency validation](snapshots/2026-10-08-baseline/contingency-validation-2026-10-09-v1.json) has 325 checks against closed-form and independent Cartesian references. [Matching validation](snapshots/2026-10-08-baseline/matching-certificate-validation-2026-10-09-v1.json) covers all 1,024 five-vertex graphs, compares 32,768 subset bounds against independent brute-force optima, and checks malformed/invalid candidates. It is finite component validation, not an almost-linear solver benchmark.

Defer literal research backends for dossiers 004 and 007. Retain constrained-data law auditing and existing-solver allocation certificates as more plausible integration hypotheses. Demand, delivery cost and recurring value still need validation; small reference scripts alone do not establish profitable products.