# Graph sampling protocol and null-model calibration Edition: 9 October 2026 Australia/Brisbane. Decision: **Prototype bounded protocol audit; defer cheap general certified sampling**. Commercial demand and profitable delivery remain unvalidated. ## Research finding Family 131 claims total-variation mixing time at distance one-quarter at most `2n^8` for every graphical labeled degree vector, for one precisely specified lazy chain on simple undirected graphs with the complete host. Half the steps hold. Other steps choose a uniform four-set and one of six ordered distinct pairings; invalid proposals hold. The selected formal scope covers connectivity, gap and chain estimates, excluding the paper's exact uniform sampler. That sampler uses a rare exhaustive residual correction and expected polynomial bit cost, with exponential correction work and unbounded rejection tails. No independent proof check was run. ## Problem and buyer A network analyst needs a degree-conditioned null comparison but may record only accepted swaps, impose a restricted host, or assume degree preservation proves uniformity. Those choices change the chain or state space. The proposed method review makes the intended law, proposal, time counter, allowed constraints and uncertainty visible before a graph-analysis conclusion is relied on. A recurring scientific or graph analytics team is the buyer hypothesis. ## What the finding could enable The all-degree mixing result could supply a general complete-host guarantee when the actual implementation and step counter match the theorem. The implemented bounded calibration reference enumerates the fiber and exact finite-time law, validates the precise lazy kernel, and exposes state-space and stationary-law counterexamples. It supports a protocol report or test suite for a practical sampler; it does not implement the unrestricted exact source sampler or certify large-graph practical stopping times. ## Technical and commercial limits Directed, weighted, connected-only, attribute-conditioned and host-restricted chains are outside this theorem. The exact ordinary branch uses `t=24n^2*binom(n,4)*(B+2D+2)`, `B=binom(n,2)`, `D=4B+10`, plus rare tabulation. The quarter-TV bound alone is about `3.57*10^12` chain steps at 34 vertices and `2*10^16` at 100 vertices. These declared upper bounds are not necessary mixing times, measured runtimes or useful empirical deadlines. Accepted-event time is distinct from all holding/rejected/accepted chain steps. The finite reference caps six vertices, 512 states, 64 propagation steps and two million enumeration/proposal/transition work units. It uses exact integers and fractions, and measures TV from one selected start. This does not establish worst-case mixing. Exhaustion returns unknown instead of a completed state-space conclusion. Uniform labeled graphs, uniform graph isomorphism types and uniform accepted events are different laws. ## Minimal architecture Graph/degree model -> documented host and allowed constraints -> proposal/time-counter mapping -> exact small-fiber controls -> practical sampler diagnostics -> analyst report with guarantee/unknown labels. Record all proposal attempts and holdings if invoking the source bound. Large-graph heuristic stopping remains separately unverified. The shared documentary contract now includes chain/host/time-accounting obligations. ## Existing alternatives and differentiation NetworkX provides double-edge swaps and reports `nswap` as the number of swaps performed, with a separate attempt cap and no connectivity enforcement. Its API is not the paper's uniform four-set lazy-step interface; do not transfer the bound using an accepted-swap count. The generic accepted-switch counterexample below is not a full audit or universal defect claim about NetworkX. Value must come from a useful method review and reproducible evidence beyond existing randomization tools. [NetworkX API](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.swap.double_edge_swap.html). ## Monetization hypothesis Hypothesis: AUD 4,000–8,000 for a bounded graph-method calibration project, then support for repeated analyses if needed. At an assumed AUD 6,000 fee and 20 specialist hours at AUD 180/hour, AUD 2,400 remains before sales, support and overhead; 35 hours exceed the fee. The module overlaps the evidence platform. Infrequent academic usage may support funded work or consulting rather than a standalone subscription. ## Validation experiment The reference passed 69 checks, including every four-vertex degree fiber against separate edge enumeration and neighbor-pattern checks, a closed-form three-state TV law, invalid inputs and budget semantics. For degree one on a six-cycle host, the two feasible perfect pairings are isolated: their TV from uniform remains `1/2`. For six vertices all of degree two, there are 60 six-cycles with 12 valid-switch neighbors and ten two-triangle graphs with 18. A generic chain selecting a uniform valid neighbor has stationary mass proportional to neighbor count, so the triangle event has probability `1/5`, compared with uniform probability `1/7`; stationary TV is `2/35`. The precise lazy chain preserves uniformity. Its saved one-start TV reaches one-quarter at 38 steps, a finite fixture observation, not a broad improved bound. ## Conditions to reject or defer Reject the source-bound label when proposal, time unit or extra constraints differ without a separate proof. Defer practical exact sampling until finite constants and latency requirements are met. Reject a paid service if its report does not change a material analytical decision or existing diagnostics already supply equivalent evidence. Preserve a distinct status for heuristic mixing and requested exactness. ## Next concrete action Run [audit_switch_chain.py](../../tools/audit_switch_chain.py) on the [restricted six-cycle fixture](../../fixtures/six-cycle-host-switch-2026-10-09-v1.json), then use the exact controls to review one real public graph-analysis protocol. Independently map an external library's actual proposal/stopping semantics before claiming its stationary law or calibrated p-values. ## Pinned evidence - [Introduction/kernel](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026/build/sections/introduction.tex), [mixing derivation](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026/build/sections/mixing.tex), [exact residual sampler](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026/build/sections/exact-sampling.tex). - [Selected formal scope](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/docs/131.md); independent verification not run. - [Saved exact finite laws/counterexamples/declared schedules](../../snapshots/2026-10-08-baseline/switch-chain-examples-2026-10-09-v1.json), [69 checks](../../snapshots/2026-10-08-baseline/switch-chain-validation-2026-10-09-v1.json), [ten documentary contracts](../../prototypes/curated-contracts-2026-10-09-v2.json).