# Graph sampling, all-cut trees and spectral construction

This edition extends the [earlier direct-backend exclusions](FEASIBILITY-2026-10-09-v3.md). New source readings clarify three graph-product boundaries. Finite reference checks do not verify the source proofs or establish buyer value.

## Sampling protocol changes the law

Family 131's bound applies to the half-hold, uniform-four-set, uniform-ordered-pair chain on the complete host. Invalid proposals hold and count as steps. Its quarter-TV bound is `2n^8`; exactness uses an ordinary run of `24n^2*binom(n,4)*(B+2D+2)` steps and a rare exhaustive residual correction, with `B=binom(n,2)` and `D=4B+10`. The exact algorithm has expected bit cost, exponential correction work and unbounded rejection-draw tails. The selected formal scope excludes that exact sampler.

The [bounded audit](tools/audit_switch_chain.py) enumerates up to six vertices and calculates the precise rational law from one start. On degree one with a six-cycle host, its two feasible states are isolated; TV remains `1/2`. For degree two on six vertices, sixty six-cycles have twelve valid neighbors and ten two-triangle graphs have eighteen. Selecting uniformly among valid neighbors gives stationary triangle-event mass `1/5`, versus uniform mass `1/7`, and TV `2/35`. This generic accepted-event chain is separate from an exhaustive external-library audit. NetworkX's swap API counts performed swaps and has a separate attempt cap; its interface cannot inherit the paper's step bound without a kernel/time correspondence. [NetworkX documentation](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.swap.double_edge_swap.html).

[Saved exact laws, counterexamples and schedules](snapshots/2026-10-08-baseline/switch-chain-examples-2026-10-09-v1.json), [69 finite checks](snapshots/2026-10-08-baseline/switch-chain-validation-2026-10-09-v1.json), [source kernel](../source/openai-math/preprints/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026/build/sections/introduction.tex), [scope](../source/openai-math/lean/docs/131.md).

## Fundamental cuts do not certify all cuts

For a path tree in K4, fundamental tree-cut ratios are at most `1/3`, while an alternating-vertex cut crosses three tree edges out of four original edges: actual thinness `3/4`. The [exact all-cut audit](tools/audit_tree_thinness.py) finds this witness. It handles positive binary multiplicities without expanding copies and computes exact connectivity and achieved `k*alpha`. Its 16-vertex cap and five-million edge-examination budget support exponential finite checking. Partial scanning grants no all-cut certificate.

Family 174's constructive signing estimate takes `Cs=2^20`, giving declared cut factor `1/2+3Cs*r^(-1/8)`. That conservative factor certifies strict contraction only for `r>(6Cs)^8`, a 55-digit quantity. This is not a final `C`, numerical input-size/runtime lower bound or impossibility for another method. The iteration cutoff and final constant remain numerically unselected. The fractional corollary promises simultaneous cut/cost rounding for nonnegative rational inputs with an all-cut mass promise; it is not separately listed in the selected family scope.

[Saved ratio/constant calculations](snapshots/2026-10-08-baseline/tree-thinness-examples-2026-10-09-v1.json), [30 checks](snapshots/2026-10-08-baseline/tree-thinness-validation-2026-10-09-v1.json), [iteration source](../source/openai-math/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/build/source/sections/iteration.tex), [signing source](../source/openai-math/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/build/source/sections/signing.tex).

## Spectral acceptance is separate from graph construction

Family 178 fixes `a=1/10000`, so its largest-primary auxiliary group has `ceil(10/(0.03a))=3,333,334` points and uses both signs: 6,666,668 signed auxiliary points during early/cleanup phases. These are parameter points, not a moment order, complexity exponent or required simultaneous-memory allocation. Repair enumerates `P^2` affine seeds for a prime of order `n^Cprime`, with the sufficiently-large fixed exponent not numerically selected here; search can stop at the first passing candidate. The fixed-degree threshold and polynomial exponent remain uninstantiated.

The theorem outputs a full adjacency list at sufficiently large even orders for fixed degree. It does not supply joint-polynomial dependence on degree and size or local adjacency queries. The existing rational contrast test remains a useful exact finite acceptance component. A heuristic generator plus a passing test does not implement the source's deterministic polynomial constructor.

[Exact parameter record](snapshots/2026-10-08-baseline/spectral-constructor-parameters-2026-10-09-v1.json), [setup](../source/openai-math/preprints/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026/build/sections/setup.tex), [repair](../source/openai-math/preprints/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026/build/sections/repair.tex), [existing checker](tools/audit_ramanujan_graph.py).

The revised graph businesses are method calibration, finite cut assurance and exact spectral acceptance, with full constructors retained as separate R&D objectives. Their usefulness, repeatability and pricing still need buyer validation. [Dossier 005](opportunities/005-graph-null-model-calibration/2026-10-09-v2.md), [dossier 024](opportunities/024-thin-tree-network-analysis/2026-10-09-v2.md), [dossier 036](opportunities/036-deterministic-spectral-topology-library/2026-10-09-v2.md).