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

All-cut tree assurance and rounding research toolkit

Edition: 9 October 2026 Australia/Brisbane. Decision: Prototype exact finite cut audit; defer the literal constructor. Buyer value and profitable delivery remain hypotheses.

Research finding

Family 174 claims a deterministic polynomial-bit constructor of a C/k-thin spanning tree in every finite loopless k-edge-connected multigraph, including binary multiplicities. A separate corollary gives simultaneous all-cut and nonnegative-cost rounding for rational fractional cut inputs. The construction uses hierarchy geometry, exact rational separation, frame normalization and matrix signing. Selected formal statements cover the existence and algorithmic thin-tree claims; the full fractional cost corollary is not stated in that family scope. The existence proof's compactness/fixed-point choice is distinct from the finite-bit algorithm. Family 089's planar/bounded-treewidth metric embeddings remain a separate conditional input, with no new review or arbitrary-graph extension here.

Problem and buyer

A graph-optimization researcher or solver team needs to check whether a proposed tree meets an all-cut fraction, rather than infer it from a few familiar cuts. It also needs to know whether compressed multiplicities, chosen costs and downstream routing objectives actually match the mathematical model. A funded graph-algorithm integration or assurance module is a more plausible initial buyer hypothesis than general network-design SaaS.

What the finding could enable

A practically redesigned constructor could provide deterministic thin-tree and cost/cut rounding modules for optimization research. The implemented bounded audit now reports exact connectivity, worst all-cut ratio, an attaining witness and the achieved k*alpha constant for a supplied tree. It exposes a concrete fundamental-cut checking error and handles large integer multiplicities without expanding copies. This is a finite reference for constructor validation, not a polynomial source constructor.

Technical and commercial limits

The signing estimate explicitly permits Cs=2^20. Its declared cut factor is 1/2+3Cs*r^(-1/8), which certifies strict contraction only when r>(6Cs)^8, a 55-digit packing parameter. This is an algebraic condition on a conservative estimate, not a measured runtime, final theorem constant, input-size lower bound or impossibility for another algorithm. The absolute iteration cutoff R0 and final C are unspecified numerically; below the cutoff the stated explicit routine returns any spanning tree. No practical constructive advantage has been shown.

The finite audit caps 16 vertices, 256-bit positive multiplicities and five million cut-edge examinations. It exhausts all nontrivial cuts up to complements, so its cost is exponential in vertex count. Partial scanning cannot certify the all-cut guarantee. Integer multiplicities count distinct edge copies; arbitrary traffic capacities are a different model. Thinness alone supplies neither route-load bounds nor latency, capacity planning or redundancy. A tree can disconnect after one edge failure. Cost rounding needs nonnegative rational data and the all-cut fractional promise.

Minimal architecture

Binary-multiplicity graph and candidate tree -> support/tree validity -> exact bounded all-cut scan -> witness and actual ratio -> separate constructor/cost benchmark -> solver-specific interpretation. For larger inputs, an independently assessed separation/certificate method is required. Keep metric embeddings and routing objectives separate from thinness. Preserve the proposed constant, completeness status and original edge-copy interpretation.

Existing alternatives and differentiation

Existing minimum-spanning-tree and network-optimization methods are practical baselines. A smaller or cheaper tree already preserves connectivity; the extra value needs a measured all-cut or downstream benefit. On K4, a path tree has actual thinness 3/4, whereas its fundamental tree-cut ratios are at most 1/3. An assurance report catches a claimed 1/3 guarantee that those cuts alone would miss. This is a mathematical verification gap, not evidence of a customer's existing error.

Monetization hypothesis

Hypothesis: AUD 5,000–15,000 for a bounded solver/rounding validation integration. At an assumed AUD 8,000 fee and 35 specialist hours at AUD 180/hour, AUD 1,700 remains before support and overhead; 50 hours exceed the fee. A full source-constructor implementation could require substantial R&D and is not priced by that pilot. The cut-audit module overlaps the graph/evidence platform and should not be counted as another independent subscriber.

Validation experiment

Thirty saved checks cover all 16 labeled K4 spanning trees against closed-form star/path ratios, an exact target boundary, parallel-copy scaling, a two-vertex graph with 2^100 copies, malformed/invalid trees and incomplete scan semantics. The K4 path fails target 1/3 despite passing every fundamental tree cut; its worst witness crosses three tree edges out of four original edges. Next compare supplied standard trees on a public small graph and evaluate whether a complete witness changes a solver decision. No source constructor or downstream operational improvement is demonstrated.

Conditions to reject or defer

Defer the literal constructor while constants/cutoffs and finite workload costs are unresolved. Reject an all-cut certificate based only on partial or fundamental-cut checks. Reject commercial network claims when the required capacities, reliability or route objective lacks a separate bridge. Metric guarantees remain restricted to their source graph class. A valid actual ratio may be useful even when the universal theorem constant is commercially uninformative.

Next concrete action

Run audit_tree_thinness.py on the K4 path fixture. Use it to validate a small baseline tree and record costs separately. Extract a fully numerical hierarchy cutoff and signing implementation only if a plausible solver workload warrants the R&D effort.

Pinned evidence