Strong thin spanning trees and their construction

Source and verification

This article explains family 174 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Cuts and thin spanning trees

Let $G=(V,E)$ be a finite loopless undirected multigraph. Parallel edge copies count separately. For a nonempty proper $S\subset V$, the cut ${\delta }_G(S)$ consists of edges with exactly one endpoint in $S$. The graph is $k$-edge-connected when every such cut has at least $k$ edges.

A spanning tree $T$ is $\alpha$-thin when, for every nonempty proper $S\subset V$,

$$|{\delta }_T(S)|\le \alpha |{\delta }_G(S)|.$$

The same tree must satisfy every cut inequality. A tree with small expected load on each fixed cut is not yet a thin tree.

Manuscript claims

There is an absolute $C>0$ such that every finite loopless $k$-edge-connected multigraph with at least two vertices has a $C/k$-thin spanning tree. (OpenAI, 2026)

A companion gives a deterministic algorithm constructing such a tree in time polynomial in the total binary input length, including when parallel-edge multiplicities are encoded in binary. A one-vertex input returns the empty tree. (OpenAI, 2026a)

The scale $1/k$ is necessary: two vertices joined by $k$ parallel edges have a spanning tree using exactly one edge of their only cut. The constants are absolute, rather than depending on graph order.

🏷️ Packing trees does not select one thin tree

The Nash–Williams–Tutte packing criterion says that a graph contains $r$ edge-disjoint spanning trees exactly when every partition of its vertices into $p$ nonempty parts has at least $r(p-1)$ edges between parts.

If $G$ is $k$-edge-connected, summing the cut bounds of the $p$ parts counts each crossing edge twice. There are therefore at least $kp/2$ crossing edges, enough to guarantee a packing of $\lfloor k/2\rfloor$ spanning trees.

For any one cut, the average load of these trees is at most $|{\delta }_G(S)|/r$. But the tree minimizing that load can depend on $S$. The manuscript instead keeps a large packing through successive sparsifications. At each stage, cut sizes and the packing size decrease by almost the same factor. When only a bounded packing size remains, any retained tree has the desired load compared with the original graph.

🏷️ Laplacians and resistance

Choose an orientation for each edge $e=uv$ and let $b_e=1_u-1_v$. The graph Laplacian is

$$L_H=\sum _{e\in E(H)}{b}_e{b}_e^{\mathsf{T}}.$$

For a cut indicator, $1_S^{\mathsf{T}}{L}_H{1}_S=|{\delta }_H(S)|$. Thus quadratic-form bounds can control every cut simultaneously.

The manuscript constructs a positive definite shortcut matrix $X$ above $L_H$ in the positive semidefinite order, while ensuring

$$1_S^{\mathsf{T}}X{1}_S\le 3|{\delta }_H(S)|.$$

If $H$ contains $r$ edge-disjoint spanning trees and $r$ is sufficiently large, the edges with resistance

$$b_e^{\mathsf{T}}{X}^{-1}{b}_e\le 4r^{-1/2}$$

still contain at least $\lfloor (1-r^{-1/16})r\rfloor$ edge-disjoint spanning trees.

The construction must make $X$ compatible with the low-resistance graph defined by $X$ itself. The source organizes maximal packing regions into nested partitions, applies a hierarchy estimate simultaneously to selected levels, and uses a fixed-point argument. A nontrivial final packing partition would have too many crossing edges, yielding the extraction conclusion.

🏷️ Two representations and bounded accumulated loss

The sparsification step uses two vector representations of the same edge set. One controls quadratic forms and hence cut sizes. The other is isotropic, meaning its vector outer products sum to the identity, and preserves the rank information needed for the tree-packing partition inequalities.

Stacking the two representations allows a matrix partition theorem to select one edge subset satisfying both requirements. It retains approximately half the packing while reducing every cut by approximately half, with relative losses $1+O(r^{-1/16})$.

These losses remain bounded through iteration. Reading the packing parameters backwards from a fixed terminal threshold $R$, they grow geometrically, so

$$\sum _j{r}_j^{-1/16}\le C^{\prime }{R}^{-1/16}.$$

Using $\log (1+x)\le x$ bounds the product of the multiplicative losses by an absolute constant. This is the quantitative reason repeated sparsification does not reintroduce a factor depending on $|V|$.

A weighted spectral approximation alone would not preserve the needed packing. One edge of weight $q$ and $q$ parallel unit edges have the same Laplacian, but only the latter graph contains $q$ edge-disjoint spanning trees. Retaining actual edge copies is part of the theorem.

🏷️ From existence to finite-bit computation

The companion has additional obligations. A fixed point does not provide a uniform finite search bound, real matrix whitening can introduce irrational data, and an existential matrix partition theorem does not specify how to find its signs.

The algorithmic proof enlarges the geometric tests from cut vectors to a cone of positive semidefinite matrices whose squared distances satisfy triangle inequalities. This cone has polynomially many explicit constraints. The original cut-only geometry is not sufficient on its own; the companion extends the hierarchy argument to the larger cone.

Continuous capacity ramps replace abrupt resistance thresholds. Rational separation and a quantitative interior estimate make the responses computable through convex optimization. The second vector representation is approximated rationally, its covariance is completed exactly to the identity, and a constructive matrix-signing procedure returns certificates for the cut and packing inequalities.

For binary multiplicities, expanding all edge copies could take exponential time. A preliminary truncation and rounding reduction produces only polynomially many explicit copies before the main iteration. The final tree then lifts to original edge copies. This step is indispensable for the stated input model.

The paper also obtains simultaneous cut-and-cost rounding for rational fractional edge data and nonnegative costs. The result is an algorithmic theorem, not a report of a practical implementation tested in these notes; no running-time benchmark is claimed here.

🏷️ Key steps and proof outlines

Normalize a packing without changing any subset rank

Suppose $B$ is the union of $q$ disjoint spanning trees. Work on the $(n-1)$-dimensional space perpendicular to constants, with incidence columns $b_e$. For real edge parameters $a_e$, set

$$N(a)=\sum _e{e}^{a_e}{b}_e{b}_e^{\mathsf{T}},h(a)=\log \det N(a)-q^{-1}\sum _e{a}_e.$$

Cauchy–Binet expresses the determinant as a sum over bases. Keeping the $q$ known trees and applying arithmetic-geometric mean gives a finite lower bound on $h$. Minimize $h(a)+\gamma \Vert a{\Vert }^2$ and let $\gamma$ be small. Comparison with $a=0$ bounds $\gamma \Vert a{\Vert }^2$, while stationarity gives $\Vert \nabla h(a)\Vert =2\gamma \Vert a\Vert$, so the gradient can be made arbitrarily small at a finite parameter vector. (OpenAI, 2026b)

Differentiating shows

$${\partial }_{e}h=e^{a_e}{b}_e^{\mathsf{T}}N(a{)}^{-1}{b}_e-1/q.$$

Thus $z_e=e^{a_e/2}N(a{)}^{-1/2}{b}_e$ satisfy ${\sum }_e{z}_e{z}_e^{\mathsf{T}}=I$ and $\Vert z_e{\Vert }^2\le (1+\rho )/q$ for any prescribed $\rho >0$. Crucially, the common map is invertible and every scaling is positive. Every edge subset therefore keeps exactly its incidence rank, including dependencies among parallel edges.

Projected trace turns a matrix lower bound into all packing inequalities

Suppose a selected edge set $A$ satisfies ${\sum }_{e\in A}{z}_e{z}_e^{\mathsf{T}}⪰cI$. Fix any partition into $d$ vertex parts. The vectors of within-part edges span a space $W$ of dimension at most $n-d$. Project onto $W^{\perp }$, using orthogonal projection $P$ with trace at least $d-1$. Then

$$c(d-1)\le \sum _{e\text{ crossing the partition}}\Vert P{z}_e{\Vert }^2\le \frac{1+\rho }{q}|E_A(\mathcal{P})|.$$

The within-part terms vanish exactly. This verifies every partition inequality for at least $\lfloor cq/(1+\rho )\rfloor$ disjoint spanning trees. The same argument works for every partition because the matrix inequality was global.

Stack the two systems, including their cross terms

The resistance extraction supplies a shortcut matrix $X$ and a large packing with $a_e=X^{-1/2}{b}_e$ of small norm. Stack $w_e=(a_e,z_e)$. Its covariance has cross blocks ${\sum }_e{a}_e{z}_e^{\mathsf{T}}$, which generally do not vanish. Nevertheless,

$$\sum _e(⟨x,a_e⟩+⟨y,z_e⟩{)}^2\le 2\Vert x{\Vert }^2+2\Vert y{\Vert }^2,$$

so $\Sigma ={\sum }_e{w}_e{w}_e^{\mathsf{T}}⪯2I$. If $\Vert w_e{\Vert }^2\le ϵ$, the two-sided matrix splitting lemma gives one subset $A$ with

$$\frac{1}{2}\Sigma -\tau I⪯\sum _{e\in A}{w}_e{w}_e^{\mathsf{T}}⪯\frac{1}{2}\Sigma +\tau I,\tau =2\sqrt{ϵ}+ϵ.$$

Its proof places each $w_e$ randomly in one of two coordinate blocks and pads the expected covariance to the identity with fixed small vectors. Applying the source’s matrix partition theorem and subtracting that fixed padding controls both halves, even if $\Sigma$ is singular.

The lower $z$-block preserves a packing; the upper $a$-block gives $L_A⪯L_H/2+\tau X$, hence every cut shrinks by at most $1/2+3\tau$. With $u=r^{-1/16}$, the retained packing size is $r^{\prime }=\lfloor (1-4u)r/2\rfloor$, and the ratio of cut shrinkage to packing shrinkage is at most $1+15u$. Summing $r^{-1/16}$ backward along the geometrically shrinking packing sizes bounds the product of these losses independently of graph order.

The algorithm needs a quantitative normalization argument

The companion replaces the regularized existence argument by finite-bit descent. With reduced incidence columns, the log-determinant Hessian is the covariance of a spanning-tree indicator vector, so its operator norm is at most $M=|B|$. A gradient estimate of error at most $1/(10r^2)$ supports steps of size $1/(2(M+1))$. Unless the estimated gradient norm is at most $2/r^2$, each step decreases the objective by at least a constant times $1/((M+1)r^4)$. The initial gap is at most $n\log (2M)$, giving a prescribed polynomial iteration bound.

The bounded iterate range controls matrix condition numbers with polynomial logarithms. Positive rational approximations to the edge weights then define one exact whitened frame; numerical approximations refer to that frame and do not redefine its subset ranks. Together with the companion’s computable extraction, signing certificates, and binary-multiplicity reduction, this supplies the extra obligations behind the algorithmic theorem. (OpenAI, 2026a)

See Also

• Hypercube Ramsey embeddings uses probability laws satisfying simultaneous load constraints before selecting an integral embedding.
• Second neighborhoods uses controlled deletion to preserve a different global graph invariant.

🏷️ Manuscripts and verification scope

• The strong thin tree conjecture — pinned manuscript and companion source.
• A polynomial-time construction of strong thin trees — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page has separate existence and deterministic polynomial-time comparator entries. The first does not assert an algorithm; the second includes binary-encoded multiplicities. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A polynomial-time construction of strong thin trees.

🐻  OpenAI 2026b. The strong thin tree conjecture.