64c3814
==== TABLE OF CONTENTS ====
The-strong-thin-tree-conjecture//source/figures/packing_hierarchy.tex
The-strong-thin-tree-conjecture//source/main.tex
The-strong-thin-tree-conjecture//source/sections/extraction.tex
The-strong-thin-tree-conjecture//source/sections/fixedpoint.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_construction.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_order.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_postprocess.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_preprocess.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_bags.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_bags_spectral.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_compact.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_dual.tex
The-strong-thin-tree-conjecture//source/sections/hierarchy_proof.tex
The-strong-thin-tree-conjecture//source/sections/introduction.tex
The-strong-thin-tree-conjecture//source/sections/iteration.tex
The-strong-thin-tree-conjecture//source/sections/mss.tex
The-strong-thin-tree-conjecture//source/sections/preliminaries.tex
The-strong-thin-tree-conjecture//source/sections/sparsification.tex
The-strong-thin-tree-conjecture//source/references.bib
===========================
==== BEGIN The-strong-thin-tree-conjecture//source/figures/packing_hierarchy.tex ====
\begin{figure}[tbp]
\centering
\begingroup
\definecolor{hierarchyblue}{RGB}{37,87,128}
\begin{tikzpicture}[
x=1cm,y=1cm,
font=\small,
coarse/.style={draw=black,line width=.8pt,rounded corners=5pt},
fine/.style={draw=black!65,dashed,line width=.65pt,rounded corners=4pt},
vertex/.style={circle,fill=black,inner sep=1.5pt},
levelarrow/.style={-{Stealth[length=1.8mm]},line width=.55pt},
every node/.style={inner sep=2pt}
]
\node at (6.35,6.25) {Selected threshold partitions: fine to coarse};
\node (pzero) at (1.10,5.78) {$\mathcal P_0$};
\node (dotsleft) at (2.85,5.78) {$\cdots$};
\node (pi) at (4.60,5.78) {$\mathcal P_i$};
\node (pinext) at (7.00,5.78) {$\mathcal P_{i+1}$};
\node (dotsright) at (9.00,5.78) {$\cdots$};
\node (root) at (11.05,5.78) {$\{V\}$};
\draw[levelarrow] (pzero) -- (dotsleft);
\draw[levelarrow] (dotsleft) -- (pi);
\draw[levelarrow] (pi) -- (pinext);
\draw[levelarrow] (pinext) -- (dotsright);
\draw[levelarrow] (dotsright) -- (root);
\draw[fine] (1.20,5.12) -- (2.00,5.12);
\node[anchor=west] at (2.10,5.12) {parts of $\mathcal P_i$};
\draw[coarse] (7.15,5.12) -- (7.95,5.12);
\node[anchor=west] at (8.05,5.12) {parts of $\mathcal P_{i+1}$};
\draw[coarse] (.25,1.40) rectangle (6.15,4.65);
\draw[coarse] (6.55,1.40) rectangle (12.45,4.65);
\node at (3.20,4.33)
{$C=A^*=(A')^*$};
\node at (9.50,4.33) {$D$};
\draw[fine] (.65,1.85) rectangle (2.95,3.98);
\draw[fine] (3.45,1.85) rectangle (5.75,3.98);
\draw[fine] (6.95,1.85) rectangle (9.25,3.98);
\draw[fine] (9.75,1.85) rectangle (12.05,3.98);
\node at (1.80,3.65) {$A$};
\node at (4.60,3.65) {$A'$};
\node at (8.10,3.65) {$D_1$};
\node at (10.90,3.65) {$D_2$};
\node[vertex] at (1.20,2.48) {};
\node[vertex] at (1.45,3.10) {};
\node[vertex] (u) at (2.25,2.80) {};
\node[vertex] (v) at (4.15,2.80) {};
\node[vertex] at (4.95,3.10) {};
\node[vertex] (w) at (5.10,2.35) {};
\node[vertex] (z) at (7.60,2.35) {};
\node[vertex] at (7.70,3.10) {};
\node[vertex] at (8.60,2.75) {};
\node[vertex] at (10.35,2.50) {};
\node[vertex] at (10.60,3.10) {};
\node[vertex] at (11.40,2.80) {};
\draw[hierarchyblue,line width=1.3pt] (u) -- (v)
node[midway,above=3pt,text=hierarchyblue] {$e$};
\draw[black,line width=.7pt] (w) -- (z)
node[midway,above=3pt] {$f$};
\node[text=hierarchyblue] at (6.35,.86)
{$e\in B_i\setminus B_{i+1},\qquad e\in O(A)\cap O(A')$};
\node at (6.35,.30)
{$O(A)=E_H(A,C\setminus A),\qquad f\in B_{i+1}\subseteq B_i$};
\end{tikzpicture}
\endgroup
\caption{At a selected transition $\mathcal P_i\to\mathcal P_{i+1}$,
the parts $A,A'$ merge into their immediate parent $C$.
The edge $e$ leaves the crossing set and belongs to both $O(A)$ and
$O(A')$, whereas $f$ remains a crossing edge.
Only representative vertices and edges are shown.}
\label{fig:hierarchy}
\end{figure}
==== END The-strong-thin-tree-conjecture//source/figures/packing_hierarchy.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/main.tex ====
\newcommand{\DoNotLoadEpstopdf}{}
\pdftrailerid{}
\pdfsuppressptexinfo=15
\documentclass[11pt]{amsart}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\ifdefined\pdfglyphtounicode
\pdfgentounicode=1
\pdfglyphtounicode{tfm:lmex10/parenleftbig}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbig}{0029}
\pdfglyphtounicode{tfm:lmex10/bracketleftbig}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightbig}{005D}
\pdfglyphtounicode{tfm:lmex10/braceleftbig}{007B}
\pdfglyphtounicode{tfm:lmex10/bracerightbig}{007D}
\pdfglyphtounicode{tfm:lmex10/vextendsingle}{23D0}
\pdfglyphtounicode{tfm:lmex10/vextenddouble}{2016}
\pdfglyphtounicode{tfm:lmex10/parenleftbigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbigg}{0029}
\pdfglyphtounicode{tfm:lmex10/floorleftbigg}{230A}
\pdfglyphtounicode{tfm:lmex10/floorrightbigg}{230B}
\pdfglyphtounicode{tfm:lmex10/parenleftBigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightBigg}{0029}
\pdfglyphtounicode{tfm:lmex10/floorleftBigg}{230A}
\pdfglyphtounicode{tfm:lmex10/floorrightBigg}{230B}
\pdfglyphtounicode{tfm:lmex10/braceleftBigg}{007B}
\pdfglyphtounicode{tfm:lmex10/bracerightBigg}{007D}
\pdfglyphtounicode{tfm:lmex10/parenlefttp}{239B}
\pdfglyphtounicode{tfm:lmex10/parenrighttp}{239E}
\pdfglyphtounicode{tfm:lmex10/bracelefttp}{23A7}
\pdfglyphtounicode{tfm:lmex10/braceleftbt}{23A9}
\pdfglyphtounicode{tfm:lmex10/braceleftmid}{23A8}
\pdfglyphtounicode{tfm:lmex10/braceex}{23AA}
\pdfglyphtounicode{tfm:lmex10/parenleftbt}{239D}
\pdfglyphtounicode{tfm:lmex10/parenrightbt}{23A0}
\pdfglyphtounicode{tfm:lmex10/parenleftex}{239C}
\pdfglyphtounicode{tfm:lmex10/parenrightex}{239F}
\pdfglyphtounicode{tfm:lmex10/summationtext}{2211}
\pdfglyphtounicode{tfm:lmex10/uniontext}{22C3}
\pdfglyphtounicode{tfm:lmex10/summationdisplay}{2211}
\pdfglyphtounicode{tfm:lmex10/productdisplay}{220F}
\pdfglyphtounicode{tfm:lmex10/integraldisplay}{222B}
\pdfglyphtounicode{tfm:lmex10/uniondisplay}{22C3}
\pdfglyphtounicode{tfm:lmex10/tildewide}{02DC}
\pdfglyphtounicode{tfm:lmex10/ceilingleftBig}{2308}
\pdfglyphtounicode{tfm:lmex10/ceilingrightBig}{2309}
\pdfglyphtounicode{tfm:lmex10/braceleftBig}{007B}
\pdfglyphtounicode{tfm:lmex10/bracerightBig}{007D}
\pdfglyphtounicode{tfm:lmex10/radicalbig}{221A}
\pdfglyphtounicode{tfm:lmex10/radicalBig}{221A}
\pdfglyphtounicode{tfm:lmex10/radicalBigg}{221A}
\pdfglyphtounicode{tfm:lmmi10/mu}{03BC}
\pdfglyphtounicode{tfm:lmmi8/mu}{03BC}
\pdfglyphtounicode{tfm:lmsy10/mapsto}{23D0}
\pdfglyphtounicode{tfm:lmsy10/A}{1D49C}
\pdfglyphtounicode{tfm:lmsy10/B}{212C}
\pdfglyphtounicode{tfm:lmsy10/C}{1D49E}
\pdfglyphtounicode{tfm:lmsy10/E}{2130}
\pdfglyphtounicode{tfm:lmsy10/F}{2131}
\pdfglyphtounicode{tfm:lmsy10/K}{1D4A6}
\pdfglyphtounicode{tfm:lmsy10/M}{2133}
\pdfglyphtounicode{tfm:lmsy10/P}{1D4AB}
\pdfglyphtounicode{tfm:lmsy10/R}{211B}
\pdfglyphtounicode{tfm:lmsy10/T}{1D4AF}
\pdfglyphtounicode{tfm:lmsy10/U}{1D4B0}
\pdfglyphtounicode{tfm:lmsy10/Z}{1D4B5}
\pdfglyphtounicode{tfm:lmsy10/bardbl}{2016}
\pdfglyphtounicode{tfm:lmsy10/backslash}{2216}
\pdfglyphtounicode{tfm:lmsy8/A}{1D49C}
\pdfglyphtounicode{tfm:lmsy8/C}{1D49E}
\pdfglyphtounicode{tfm:lmsy8/E}{2130}
\pdfglyphtounicode{tfm:lmsy8/F}{2131}
\pdfglyphtounicode{tfm:lmsy8/M}{2133}
\pdfglyphtounicode{tfm:lmsy8/P}{1D4AB}
\pdfglyphtounicode{tfm:lmsy8/Z}{1D4B5}
\pdfglyphtounicode{tfm:lmsy8/backslash}{2216}
\pdfglyphtounicode{tfm:msbm10/C}{2102}
\pdfglyphtounicode{tfm:msbm10/E}{1D53C}
\pdfglyphtounicode{tfm:msbm10/H}{210D}
\pdfglyphtounicode{tfm:msbm10/P}{2119}
\pdfglyphtounicode{tfm:msbm10/R}{211D}
\pdfglyphtounicode{tfm:rm-lmbx10/one}{1D7CF}
\pdfglyphtounicode{tfm:rm-lmbx8/one}{1D7CF}
\pdfglyphtounicode{tfm:rm-lmr10/Delta}{0394}
\pdfglyphtounicode{tfm:rm-lmss10/D}{1D5A3}
\pdfglyphtounicode{tfm:rm-lmss10/M}{1D5AC}
\pdfglyphtounicode{tfm:rm-lmss8/T}{1D5B3}
\fi
\usepackage[margin=1.1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs}
\usepackage[expansion=false]{microtype}
\usepackage{enumitem}
\usepackage{booktabs,array,longtable}
\usepackage{placeins}
\usepackage{needspace}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\usepackage[hidelinks,pdfusetitle]{hyperref}
\usepackage[capitalise,noabbrev,nameinlink]{cleveref}
\hypersetup{pdftitle={The strong thin tree conjecture},pdfauthor={OpenAI},bookmarksdepth=3}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\bbone}{\mathbf1}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\supp}{supp}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{construction}[theorem]{Construction}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\numberwithin{equation}{section}
\title{The strong thin tree conjecture}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\begin{abstract}
We prove that every finite loopless \(k\)-edge-connected multigraph on
at least two vertices, with \(k\ge1\), has a spanning tree meeting each
cut in at most \(C/k\) times the size of the cut,
where \(C\) is a universal constant.
This resolves the strong thin tree conjecture.
\end{abstract}
\maketitle
\setcounter{tocdepth}{1}
\tableofcontents
\input{sections/introduction}
\input{sections/preliminaries}
\input{sections/hierarchy}
\input{sections/extraction}
\input{sections/sparsification}
\input{sections/iteration}
\appendix
\input{sections/mss}
\input{sections/hierarchy_proof}
\input{sections/fixedpoint}
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END The-strong-thin-tree-conjecture//source/main.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/extraction.tex ====
\section{Extracting a tree packing with small resistance}
\label{sec:extraction}
Throughout this section, \(H\) is an \(r\)-tree-packable graph on
\(n\ge2\) vertices. Set
\begin{equation}\label{eq:parameters}
u=r^{-1/16},\qquad q=\lfloor(1-u)r\rfloor.
\end{equation}
We take \(r\) above an absolute threshold, so in particular \(q>1\).
The threshold may be increased finitely many times below.
\begin{theorem}[Shortcut extraction]\label{thm:extraction}
For all sufficiently large integers \(r\), every \(r\)-tree-packable
graph \(H\) admits \(X\succ0\) such that
\begin{equation}\label{eq:shortcut-X}
L_H\preceq X,\qquad
\mathbf1_S^{\mathsf T}X\mathbf1_S\le3|\delta_H(S)|
\quad(\varnothing\ne S\subsetneq V),
\end{equation}
and the edges with \(R_X(e)\le4r^{-1/2}\) contain \(q\)
edge-disjoint spanning trees. The lower threshold on \(r\) is
independent of \(H\) and \(n\).
\end{theorem}
For a nontrivial maximal packing partition,
Lemma~\ref{lem:packing-parts}(iii) limits the number of crossing edges
in the threshold graph. We first construct
a response that makes most crossing edges have small resistance.
Averaging responses at nearby matrices and taking a fixed-point limit transfers
this estimate to the matrix defining the partition, forcing that
partition to be trivial.
\subsection{A compact set of matrices}
Let
\begin{equation}\label{eq:compact-domain}
\mathcal K=
\left\{X=X^{\mathsf T}:
X\succeq L_H+n^{-1}I,\quad
\mathbf1_S^{\mathsf T}X\mathbf1_S\le3|\delta_H(S)|
\text{ for }\varnothing\ne S\subsetneq V\right\}.
\end{equation}
This is a nonempty compact convex subset of the real symmetric
matrices. Indeed, \(H\) is connected, and
\(|S|/n<1\le|\delta_H(S)|\), so \(L_H+n^{-1}I\) belongs to
\(\mathcal K\). Closedness and convexity follow from the defining
inequalities. The singleton cuts give
\(X_{vv}\le3\deg_H(v)\), and positive semidefiniteness gives
\(|X_{vw}|^2\le X_{vv}X_{ww}\); hence the domain is bounded.
Every matrix in \(\mathcal K\) is bounded below by \(n^{-1}I\).
Given any locally \(q\)-connected hierarchy in \(H\), mark exactly
the nonroot nodes satisfying
\[
|O(A)|\ge q^{-1}|P(A)|.
\]
For all sufficiently large absolute \(r\), we have \(q\ge r/2\)
and \(q\ge q_H\). Theorem~\ref{thm:hierarchy-power} gives a shortcut
matrix \(D\) whose average resistance on every marked \(O(A)\) is
at most
\[
q^{-31/40}\le2^{31/40}r^{-31/40}\le r^{-3/4},
\]
where the final inequality holds for \(r\ge2^{31}\). Put
\begin{equation}\label{eq:hierarchy-response}
Y=L_H+n^{-1}I+D.
\end{equation}
Then \(Y\in\mathcal K\), since on every cut its quadratic form is
at most \(2|\delta_H(S)|+|S|/n\le3|\delta_H(S)|\).
Lemma~\ref{lem:resistance-order} also gives
\begin{equation}\label{eq:response-average}
\frac1{|O(A)|}\sum_{e\in O(A)}R_Y(e)\le r^{-3/4}
\qquad\text{for every marked }A.
\end{equation}
\subsection{Packing partitions and a simultaneous response}
Fix \(X\in\mathcal K\). For \(s>0\), let
\[
F_s(X)=\bigl(V,\{e\in E(H):R_X(e)\le s\}\bigr),
\qquad
\mathcal P_s(X)=\mathcal P(F_s(X)),
\]
where \(\mathcal P(F)\) is the maximal packing partition of
Lemma~\ref{lem:packing-parts}. Define
\[
B_s(X)=E_H(\mathcal P_s(X)),\qquad M_s(X)=|B_s(X)|.
\]
The crossing sets contain edges of \(H\), including those absent
from \(F_s(X)\).
As \(s\) increases, the partitions coarsen and their crossing sets
decrease. Only finitely many partitions occur.
Each part induces a \(q\)-edge-connected subgraph of \(H\),
because it contains \(q\) packed trees in \(F_s(X)\).
\begin{lemma}[Simultaneous response]\label{lem:response}
There is an absolute constant \(C_0\), which may be taken to be \(40\),
such that for every \(X\in\mathcal K\) there exists \(Y\in\mathcal K\)
with
\begin{equation}\label{eq:simultaneous-response}
\bigl|\{e\in B_s(X):R_Y(e)>r^{-1/2}\}\bigr|
\le C_0r^{-1/4}M_s(X)
\qquad\text{for every }s>0.
\end{equation}
\end{lemma}
\begin{proof}
Temporarily suppress \(X\) from the notation.
In each occupied bin \(2^a\le M_s<2^{a+1}\), \(a\ge0\),
choose the finest partition that occurs in that bin.
List the chosen partitions in order from fine to coarse as
\(\mathcal P_0,\ldots,\mathcal P_{\ell-1}\), with crossing sets
\(B_i\) and sizes \(M_i\). Append
\(\mathcal P_\ell=\{V\}\), \(B_\ell=\varnothing\), \(M_\ell=0\).
The distinct parts of these partitions, together with all
singletons, form a laminar family containing \(V\).
Give each proper set its smallest proper containing set as parent.
The children of every nonsingleton partition that set, so this is
a hierarchy. Every induced graph at a node is \(q\)-edge-connected:
this was proved for the partition parts, the root is
\(r\)-tree-packable, and singleton conditions are vacuous.
Take the response \(Y\) from \eqref{eq:hierarchy-response} for this
hierarchy.
Consider a transition \(\mathcal P_j\) to \(\mathcal P_{j+1}\).
If a part \(A\in\mathcal P_j\) changes, the part of
\(\mathcal P_{j+1}\) containing it is its immediate parent in the
hierarchy. Indeed, earlier selected partitions are finer and later
ones are coarser, so none supplies a distinct set strictly between
these two. Adding singleton leaves creates no such set.
An edge of \(B_j\setminus B_{j+1}\) has endpoints in two changing
parts of \(\mathcal P_j\) with the same parent. It belongs to the
\(O(A)\) set of each of those parts; see Figure~\ref{fig:hierarchy}.
The total full boundary size of all changing parts is at most
\(2M_j\), since they belong to the single partition \(\mathcal P_j\).
For the unmarked changing parts,
\[
\sum_A |O(A)|\le \frac1q\sum_A|P(A)|\le\frac{2M_j}{q}.
\]
For the marked changing parts, \eqref{eq:response-average} gives
\[
\bigl|\{e\in O(A):R_Y(e)>r^{-1/2}\}\bigr|
\le r^{-1/4}|O(A)|.
\]
Their total bad-edge count is therefore at most \(2M_jr^{-1/4}\).
These counts may cover an edge more than once, which only enlarges
the upper bound. Consequently at most
\[
2(r^{-1/4}+1/q)M_j
\]
of the disappearing edges are bad.
There is only one representative per occupied dyadic bin, so its
bin exponents strictly decrease. For every \(i<\ell\),
\begin{equation}\label{eq:dyadic-tail}
\sum_{j=i}^{\ell-1}M_j<4M_i.
\end{equation}
For example, if \(2^a\le M_i<2^{a+1}\), the successive terms are
bounded by \(2^{a+1},2^a,2^{a-1},\ldots\).
Every edge of \(B_i\) disappears at exactly one later transition.
Its bad-edge count is thus at most
\[
8(r^{-1/4}+1/q)M_i.
\]
For an arbitrary \(s\) with \(M_s>0\), the chosen representative
in its bin is finer, so \(B_s\subseteq B_i\) and \(M_i<2M_s\).
The bad-edge count in \(B_s\) is at most
\[
16(r^{-1/4}+1/q)M_s\le40r^{-1/4}M_s
\]
for all sufficiently large \(r\). If \(M_s=0\), the assertion is
immediate. This proves \eqref{eq:simultaneous-response}
simultaneously for every threshold.
\end{proof}
\input{figures/packing_hierarchy}
\subsection{A consistent matrix from a fixed-point limit}
\begin{proof}[Proof of Theorem~\ref{thm:extraction}]
The response supplied by Lemma~\ref{lem:response} need not vary
continuously with \(X\). We interpolate only finitely many responses
at a time.
For each positive integer \(p\), cover \(\mathcal K\) by finitely
many relative open balls of radius \(1/p\), with centers
\(C_{p,1},\ldots,C_{p,N_p}\in\mathcal K\). At each center choose a
response \(Y_{p,j}\). Define continuous weights
\[
\phi_{p,j}(Z)=
\frac{\max\{0,p^{-1}-\|Z-C_{p,j}\|\}}
{\sum_{h=1}^{N_p}\max\{0,p^{-1}-\|Z-C_{p,h}\|\}}
\qquad(Z\in\mathcal K).
\]
The denominator is positive by the open cover.
The map
\[
\Phi_p(Z)=\sum_{j=1}^{N_p}\phi_{p,j}(Z)Y_{p,j}
\]
is a continuous self-map of the compact convex set \(\mathcal K\).
Theorem~\ref{thm:fixedpoint} gives
\(X_p=\Phi_p(X_p)\).
Pass to a subsequence along which \(X_p\to X\in\mathcal K\).
Choose
\[
3r^{-1/2}0\), then
\[
\|C_{p,j}-X\|1\) parts.
The original \(r\) packed trees in \(H\) give \(M\ge r(d-1)\).
Choose the absolute threshold on \(r\) so that
\(2C_0r^{-1/4}q(d-1),
\]
contradicting Lemma~\ref{lem:packing-parts}(iii).
The partition is therefore \(\{V\}\), so \(F_s(X)\) is
\(q\)-tree-packable. Every one of its edges has resistance at most
\(s<4r^{-1/2}\), and \(X\in\mathcal K\) gives
\eqref{eq:shortcut-X}.
\end{proof}
\begin{remark}\label{rem:uniform-extraction}
For a fixed graph, the finite-cover scale needed to stabilize the
chosen threshold can be arbitrarily small. This does not affect the
absolute cutoff on \(r\). The latter comes only from the hierarchy
estimate and the numerical inequalities in the proof.
The construction makes no claim about its computational cost.
\end{remark}
==== END The-strong-thin-tree-conjecture//source/sections/extraction.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/fixedpoint.tex ====
\section{A finite-dimensional fixed-point theorem}
\label{sec:fixedpoint}
We prove the finite-dimensional fixed-point theorem of
Brouwer~\cite{Brouwer} used in the extraction step, including its
combinatorial ingredient.
\begin{theorem}[Finite-dimensional fixed point]\label{thm:fixedpoint}
Let \(K\) be a nonempty compact convex subset of a finite-dimensional
real vector space. Every continuous map \(F:K\to K\) has a fixed point.
\end{theorem}
\subsection{Triangulations with arbitrarily small mesh}
A \(d\)-simplex is the convex hull of \(d+1\) affinely independent
points; its faces are the convex hulls of subsets of its vertices.
A finite triangulation of a \(d\)-simplex consists of finitely many
\(d\)-simplices and all their faces, covering the original simplex,
such that two members intersect in a common face or not at all.
Its \emph{mesh} is the largest diameter of its members.
We first construct such triangulations with mesh tending to zero.
Let \(S\) have vertices \(a_0,\ldots,a_d\). For every nonempty
vertex set \(A\), write \(b_A=|A|^{-1}\sum_{a\in A}a\).
The barycentric subdivision of \(S\) has one simplex
\[
\operatorname{conv}\{b_{A_0},\ldots,b_{A_d}\},\qquad
A_k=\{a_{\pi(0)},\ldots,a_{\pi(k)}\},
\]
for each permutation \(\pi\) of \(\{0,\ldots,d\}\), together with
all faces of these simplices. The displayed barycenters are affinely
independent: their coordinate columns in the ordered vertices of
\(S\) form an invertible triangular matrix.
Here is a direct verification of the covering and intersection
properties. Write \(x=\sum_i\lambda_i a_i\), where
\(\lambda_i\ge0\) and \(\sum_i\lambda_i=1\), and order the
coordinates so that
\(\lambda_{\pi(0)}\ge\cdots\ge\lambda_{\pi(d)}\).
With \(\lambda_{\pi(d+1)}:=0\), put
\[
t_k=(k+1)(\lambda_{\pi(k)}-\lambda_{\pi(k+1)}).
\]
Then
\[
t_k\ge0,\quad \sum_{k=0}^d t_k=1,\quad
x=\sum_{k=0}^d t_k b_{A_k}.
\]
Conversely, a convex combination of these barycenters has coordinates
in that order. Whenever \(t_k>0\), the prefix \(A_k\) is the set of
vertices whose coordinates are at least the corresponding positive
coordinate level. Thus the barycenters with positive coefficients
are determined by \(x\), independently of how tied coordinates are
ordered. Two subdivision simplices consequently intersect exactly
in the convex hull of their common vertices. Their faces inherit the
same property. On any face of \(S\), coordinates outside that face
are zero, so this construction restricts exactly to the barycentric
subdivision of that face. Subdividing each member of a triangulation
therefore gives another finite triangulation: the constructions agree
on shared faces, and simplices in different original members can
intersect only there.
For nested nonempty vertex sets \(A\subsetneq B\),
\[
b_B=\frac{|A|}{|B|}b_A+
\left(1-\frac{|A|}{|B|}\right)b_{B\setminus A},
\qquad
\|b_B-b_A\|\le\frac{d}{d+1}\operatorname{diam}(S).
\]
The diameter of a convex hull is at most the largest distance between
its vertices, by the triangle inequality applied to convex
combinations. Every new simplex thus has diameter at most
\(d/(d+1)\) times that of its parent. For \(d\ge1\), iterating
gives mesh tending to zero. The case \(d=0\) is immediate.
\subsection{Sperner's counting argument}
Write
\[
\Delta_d=\{x\in\R^{d+1}:x_i\ge0\ (0\le i\le d),\quad
\sum_{i=0}^d x_i=1\}.
\]
A triangulation restricts to a triangulation of each face of
\(\Delta_d\): intersecting a small simplex with a coordinate
hyperplane \(x_i=0\) selects precisely its vertices on that
hyperplane, since all coordinates are nonnegative. The intersections
of full dimension cover the face: their union is closed, while the
remaining finitely many lower-dimensional simplices cannot cover
any relatively open subset of the face. Every smaller member is a
face of a full-dimensional one, by the common-face property applied
at a relative interior point of the smaller member.
\begin{lemma}[Sperner~\cite{Sperner1928}]\label{lemma:sperner}
Label every vertex \(v\) of a finite triangulation of \(\Delta_d\)
by an integer \(\ell(v)\in\{0,\ldots,d\}\), with
\(v_{\ell(v)}>0\). The number of \(d\)-simplices whose vertex
labels are \(0,\ldots,d\), each occurring once, is odd.
\end{lemma}
\begin{proof}
For \(d\ge1\), we use the following elementary incidence fact.
A small \((d-1)\)-face belongs to two small \(d\)-simplices if
it is not contained in the boundary, and to one if it is.
To see this, choose a point in its relative interior. Any simplex containing that point
contains the entire face, by the common-face intersection property.
Finiteness allows a sufficiently small ball in the affine hull of
\(\Delta_d\), centered at the point, to avoid all other simplices.
Shrinking the ball further, each incident \(d\)-simplex occupies
exactly one half of this ball, on one side of the face's affine
hyperplane: the point lies on none of its other facets. Disjoint
interiors permit at most one simplex on either side, and the covering
property supplies all sides belonging to \(\Delta_d\). A boundary
\((d-1)\)-face lies in exactly one original facet, so precisely one
side belongs to \(\Delta_d\). Indeed, a coordinate vanishing at a
relative interior point vanishes on the whole face, and two distinct
original facets intersect in dimension at most \(d-2\).
Induct on \(d\). For \(d=0\), there is one vertex, labeled zero.
For \(d\ge1\), call a small \((d-1)\)-face \emph{special} if
its labels are exactly \(0,\ldots,d-1\). Count incidences between
small \(d\)-simplices and their special faces. A simplex with all
\(d+1\) labels contributes one incidence. A simplex containing
\(0,\ldots,d-1\) but not \(d\) has exactly one repeated label
and contributes two, by deleting either vertex with that label.
Every other simplex contributes zero. Modulo two, the incidence
count is therefore the number asserted to be odd.
By the incidence fact, the same count modulo two is the number of
special faces on the boundary. Such a face cannot lie in
\(x_i=0\) for \(iF_i(v)\). Such an index exists because the two coordinate
sums are equal and \(v\ne F(v)\); it satisfies \(v_i>0\).
Lemma~\ref{lemma:sperner} supplies a fully labeled simplex in each
subdivision. Denote its vertex labeled \(i\) by \(v^{(m,i)}\),
where \(m\) is the subdivision index. By compactness, a subsequence
of \(v^{(m,0)}\) converges to some \(x\in\Delta_d\).
The mesh tends to zero, so all \(v^{(m,i)}\) converge to the same
\(x\) along that subsequence. Continuity gives
\(x_i\ge F_i(x)\) for every \(i\). Equality of the coordinate
sums forces equality in every coordinate, proving \(F(x)=x\).
Affine coordinates give the same result for every simplex.
Now equip the affine hull of \(K\) with Euclidean coordinates.
For any point \(x\) in this hull, compactness gives a nearest
point \(P(x)\in K\). It is unique: if distinct \(p,q\in K\)
both minimized the squared distance, convexity and
\[
\left\|x-\frac{p+q}{2}\right\|^2
=\frac{\|x-p\|^2+\|x-q\|^2}{2}
-\frac{\|p-q\|^2}{4}
\]
would contradict minimality. If \(p=P(x)\) and \(z\in K\),
comparison with \(p+t(z-p)\), followed by division by \(t>0\)
and the limit \(t\downarrow0\), yields
\(\langle x-p,z-p\rangle\le0\).
Apply this with \(p=P(x),z=P(y)=q\), and with \(q=P(y),z=p\).
Adding the inequalities gives
\[
\|p-q\|^2\le\langle x-y,p-q\rangle
\le\|x-y\|\,\|p-q\|.
\]
Thus \(\|P(x)-P(y)\|\le\|x-y\|\), so \(P\) is continuous,
and \(P(x)=x\) for \(x\in K\).
If the affine hull has dimension zero, \(K\) is a singleton.
Otherwise identify it with \(\R^d\), \(d\ge1\), and choose
\(M>0\) so that \(K\subseteq[-M,M]^d\). The simplex
\[
S=\{x\in\R^d:x_j\ge-M\ (1\le j\le d),\quad
\sum_{j=1}^d x_j\le dM\}
\]
contains that cube: its vertices are
\(a=(-M,\ldots,-M)\) and \(a+2dM e_j\), \(1\le j\le d\).
The continuous map \(F\circ P:S\to K\subseteq S\) has a fixed
point \(x\) by the simplex case. Its image lies in \(K\), so
\(x\in K\), \(P(x)=x\), and \(F(x)=x\), as required.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/fixedpoint.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy.tex ====
\section{Shortcuts for a locally connected hierarchy}\label{sec:hierarchy}
We require one matrix that controls average resistances on several related
boundaries. A hierarchy specifies the boundaries on which this control is
required. The matrix need only obey an upper bound on cuts; an upper bound
in the positive semidefinite order would be a stronger condition.
\begin{definition}[Hierarchy and its boundaries]\label{def:hierarchy}
Let $H=(V,E)$ be a finite loopless multigraph. A \emph{hierarchy} on $V$
is a finite rooted tree of distinct nonempty vertex sets. Its root is $V$,
its leaves are the singleton sets, and the children of every nonleaf form
a partition of that node into at least two sets. For a nonroot node $A$,
write $A^*$ for its parent and define
\[
P(A)=\delta_H(A),\qquad
O(A)=E_H(A,A^*\setminus A).
\]
All edge sets here retain multiplicities. Given an integer $h\ge2$, the
hierarchy is \emph{locally $h$-connected} if $H[A]$ is $h$-edge-connected
for every node $A$. For singleton nodes this condition is vacuous.
\end{definition}
In this definition $|O(A)|\ge h$ for every nonroot $A$: it is the boundary
of the nonempty proper set $A$ in the $h$-edge-connected graph $H[A^*]$.
An edge belongs to $O(A)$ for exactly two nodes of the full hierarchy.
Indeed, if $C$ is the least node containing both endpoints, these two
nodes are the two children of $C$ containing its endpoints. Consequently
an edge belongs to at most two parent boundaries in any subcollection.
Orient each edge arbitrarily and let $b_e$ be its incidence column. As
usual, $L_H=\sum_{e\in E}b_eb_e^{\mathsf T}$. A \emph{shortcut matrix}
for $H$ means a symmetric positive definite matrix $D$ on $\mathbb R^V$
such that
\begin{equation}\label{eq:hierarchy-shortcut}
\mathbf 1_S^{\mathsf T}D\mathbf 1_S\le |\delta_H(S)|
\qquad(\varnothing\ne S\subsetneq V).
\end{equation}
Its edge resistance is $R_D(e)=b_e^{\mathsf T}D^{-1}b_e$.
The restriction to proper nonempty cuts in
\eqref{eq:hierarchy-shortcut} is essential: imposing the same inequality
at $S=V$ would contradict positive definiteness. We do not impose
$D\preceq L_H$.
The following estimate is the hierarchy input used in this paper.
It is a polynomial consequence of the Tree-CP theorem of Anari and
Oveis Gharan~\cite[Theorem~3.5, printed p.~22]{AOG}. We give a complete
proof in Appendix~\ref{app:hierarchy-proof}, following their dual and
geometric method with parameters chosen for this weaker bound.
\begin{theorem}[Polynomial shortcut bound]\label{thm:hierarchy-power}
There is an absolute integer $q_H\ge2$ such that the following holds for
each integer $q\ge q_H$. Let $H$ have a locally $q$-connected hierarchy,
and let $\mathcal M$ be any collection of its nonroot nodes satisfying
$|O(A)|\ge |P(A)|/q$. Then $H$ has a shortcut matrix $D$ such that
\begin{equation}\label{eq:hierarchy-power}
\frac{1}{|O(A)|}\sum_{e\in O(A)}R_D(e)\le q^{-31/40}
\qquad(A\in\mathcal M).
\end{equation}
The cutoff is independent of the graph, the hierarchy depth and the
marked collection $\mathcal M$.
\end{theorem}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned.tex ====
\subsection{Charging assigned bags}
\label{sec:hierarchy-assigned}
The second charging argument uses the hierarchy to allow geometric overlap:
two overlapping shells will charge edges in disjoint induced subgraphs.
We give the labeling, construction, and accounting explicitly, following
the assigned-bag argument of Anari and Oveis Gharan
\cite[Proposition~7.2 and Section~7.2]{AOG}.
\begin{proposition}[Assigned-bag charging]
\label{prop:hierarchy-assigned}
Let $X:V\to\{0,1\}^{d}$, and let $\mathcal T$ be a locally
$k$-connected hierarchy of $G$, with selected nonroot nodes $T$ satisfying
$|O(t)|\ge k\lambda|P(t)|$ for $t\in T$.
Suppose $\mathcal F_1,\ldots,\mathcal F_m$ is a $\lambda$-geometric
sequence of families of $(24C_3/k)$-assigned bags, of types
$(\delta_i,T_i)$, with $T_i\subseteq T$. If
\[
C_4\ge3,\qquad \lambda\le\frac1{6C_4},\qquad
C_3\ge2\bigl((C_4+1)+4(C_4+2)^2\bigr),
\]
then
\begin{equation}\label{ha:assigned-bound}
\sum_{\{u,v\}\in E}\|X_u-X_v\|_1
\ \ge\ \frac{k}{8}\frac{C_4}{12C_3}
\sum_{i=1}^m\delta_i\sum_{t\in T_i}|\operatorname{Bag}_t|.
\end{equation}
In particular, one may take $C_4=3$, $C_3=10^4$ and
$\lambda\le1/18$.
\end{proposition}
The proof first discards noninsertable balls while retaining at least
half the total mass. It then constructs a valid labeled collection
whose total width is at least $C_4/(12C_3)$ times the retained mass.
Lemma~\ref{ha:labeled-energy} converts that width to graph length
at rate $k/4$.
\input{sections/hierarchy_assigned_preprocess}
\input{sections/hierarchy_assigned_order}
\input{sections/hierarchy_assigned_construction}
\input{sections/hierarchy_assigned_postprocess}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_construction.tex ====
\subsubsection{Carving the interior balls}
\label{ha:carving}
Write $[z]_+=\max\{z,0\}$ and set
\[
\theta=\frac{C_4}{6C_3}.
\]
The assumptions on the constants imply
\begin{equation}
\begin{split}
C_3-1&\geq 2\bigl(C_4+4(C_4+2)^2\bigr),\\
\frac78(C_3-1)&\geq C_4+4,\qquad
C_3\geq 2C_4(C_4+2),\qquad
\theta\leq\frac1{12(C_4+2)}\leq\frac1{60}.
\end{split}
\label{ha:constant-consequences}
\end{equation}
For example, the first inequality follows by subtracting $1$ from
$C_3\geq2(C_4+1)+8(C_4+2)^2$; this same lower bound gives the remaining
inequalities for $C_4\geq3$.
During phase $\ell$, assign a nonnegative potential to each record
$A$ in the current arrangement, with center $x$ and numerical inner
and outer radii $a2C_3\delta$, the old potential is
$(R-C_4\delta)/(2(C_4+2))$. Give $B$ all the potentials of $B_1,B_2$ and
$\delta/2$ from $A$. Positive parts can only increase the following
lower bound:
\begin{align*}
\operatorname{tok}_\ell(B_1)+\operatorname{tok}_\ell(B_2)
+\frac\delta2
&\geq\frac{R-2\delta-2C_4\delta}{2(C_4+2)}
+\frac\delta2\\
&=\frac{R-C_4\delta}{2(C_4+2)}
=\operatorname{tok}_\ell(B).
\end{align*}
The remaining potential of $A$ is at least
\[
\delta-C_4\delta_{\ell+1}-\frac\delta2
\geq\frac\delta3\geq\theta\delta.
\]
Give it to $t$. Thus treating this one ball preserves every old
allocation and increases the allocation to $t$ by the required amount.
\paragraph{\textbf{The common setup for operations 2 and 3.}}
Suppose no ball of $\operatorname{Int}_t$ is interior to an avoiding
shell. Write $t^*$ for the parent of $t$.
If enough interior centers lie near a short radial interval, inserting
their balls will pay for the width removed from the old record.
When the interval is long compared with their total radius, we instead
create two overlapping central shells with crossing paths in
$G[V(t)]$ and $G[V(t^*)\setminus V(t)]$, respectively.
Local connectivity supplies the first set of paths; the decomposition
below supplies the second. Define
\[
H=G[V(t^*)\setminus V(t)],\qquad
O'(t)=\{\{u,v\}\in O(t):\|X_u-X_v\|_1<\delta\}.
\]
Partition $V(H)$ into sets $S_1,\ldots,S_j$ whose induced graphs are
$k/4$-edge-connected, by repeatedly splitting a part along a cut of
size less than $k/4$ until no such cut remains. Singleton parts are
allowed. There are $j-1$ splits, and each edge between final parts is
counted at precisely the split that first separates its endpoints.
Consequently
\[
\sum_{i=1}^j|\partial_H S_i|
<\frac{k}{2}(j-1)\quad(j>1),
\]
and the sum is zero when $j=1$. Each $S_i$ is a nonempty proper subset
of $V(t^*)$, so the $k$-edge-connectivity of $G[V(t^*)]$ gives
\begin{align*}
jk
&\leq\sum_{i=1}^j|\partial_{G[V(t^*)]}S_i|\\
&=|O(t)|+\sum_{i=1}^j|\partial_H S_i|
\leq |O(t)|+\frac{k}{2}(j-1).
\end{align*}
In particular,
\begin{equation}
j\leq\frac{2|O(t)|}{k}.
\label{ha:component-count}
\end{equation}
This proves the decomposition estimate directly, including when $H$
is disconnected and without assuming that $k/4$ is an integer.
Let $U$ be the centers, identified with vertices, of the balls still
in $\operatorname{Int}_t$, and set
\[
\begin{split}
U_i&=\{u\in U:\{u,v\}\in O'(t)\text{ for some }v\in S_i\},\\
V_i&=\{v\in S_i:\{u,v\}\in O'(t)\text{ for some }u\in U\}.
\end{split}
\]
The definition of an assigned bag ensures $\bigcup_iU_i=U$.
By the loop condition and the $12C_3/k$ assignment bound,
\[
|U|\geq\frac12|\operatorname{Bag}_t|
\geq\frac{6C_3|O(t)|}{k}.
\]
Choose $i$ with $|U_i|$ maximal. Even if the sets $U_i$ overlap,
their union bound and \eqref{ha:component-count} imply
\begin{equation}
|U_i|\geq\frac{|U|}{j}\geq3C_3.
\label{ha:many-neighbors}
\end{equation}
Choose a nonavoiding record $B$ with center $x$ and numerical radii
$r_1\rho(u_0)-\delta
>r_1+(C_3-1)\delta.
\]
These prove both cases of \eqref{ha:radial-range}.
\paragraph{\textbf{Operation 2: a dense group in the radial interval.}}
Suppose $m\delta>3L$. Replace $B$ by
\[
B_1=B(x,r_1\Vert a-2\delta),\qquad
B_2=B(x,b+2\delta\Vert r_2),
\]
with its labels, and insert all $m$ original balls of $\mathcal A$,
with their original labels. Treat these $m$ balls. Their supports are
disjoint from $B_1,B_2$ because their centers have radii strictly
between $a-\delta$ and $b+\delta$. They are pairwise disjoint as
members of the same family. We proved that each lies in the interior
of $B$, so Lemma~\ref{ha:unique-interior} makes each compatible with
every old record other than $B$. Their individual conditions follow
from insertability. Residual shells inherit validity, proving that
the whole replacement is valid.
The number treated is large. If $U_i\subseteq U_{\mathcal A}$, then
\eqref{ha:many-neighbors} gives $m\geq3C_3$. Otherwise,
\eqref{ha:radial-range} and $m\delta>3L$ give
\begin{equation}
m\geq3(C_3-1).
\label{ha:dense-count}
\end{equation}
Allocate to $B$ all the potential of $B_1,B_2$ and three quarters of
the potential of each newly inserted ball. Writing $R=r_2-r_1$,
the old potential is $R-C_4\delta$; it is positive because $B$
contains an interior ball. Even if a residual shell is empty, its
potential is at least its formal width minus $C_4\delta$. Therefore
\begin{align*}
&\operatorname{tok}_\ell(B_1)+\operatorname{tok}_\ell(B_2)
+\frac34\sum_{A\in\mathcal A}\operatorname{tok}_\ell(A)\\
&\quad\geq R-L-4\delta-2C_4\delta+\frac58m\delta\\
&\quad\geq\operatorname{tok}_\ell(B)
-(C_4+4)\delta+\frac7{24}m\delta\\
&\quad\geq\operatorname{tok}_\ell(B)
-(C_4+4)\delta+\frac78(C_3-1)\delta\\
&\quad\geq\operatorname{tok}_\ell(B).
\end{align*}
The successive estimates use \eqref{ha:fresh-potential},
$Lb-\delta.
\label{ha:radial-witnesses}
\end{equation}
By \eqref{ha:sparse-width}, $a+\delta1$.
The operations specified below maintain the following invariants.
Each intermediate collection has a valid labeling. An original
ball from $\mathcal F_\ell$ that is inserted during phase $\ell$
is unchanged for the rest of that phase. All restrictions of an
existing record are concentric radial restrictions and retain its
labels. Any additional record created while processing
$\operatorname{Bag}_t$ lies inside a replaced record $B$, has conflict
domain contained in $C(B)$, and has owner either $t(B)$ or $t$.
In the latter case its owner is $t$ and it is nonavoiding. The only
new avoiding records retain owner $t(B)$ and avoid $t$.
The construction below verifies the required labeling conditions
for each operation, so these invariants are inductive requirements,
not extra hypotheses on the input.
\begin{lemma}[Ancestor relation]\label{ha:ancestor}
While $\operatorname{Bag}_t\in\mathcal F_\ell$ is being processed,
if a candidate $A\in\operatorname{Bag}_t$ and a current record $B$
have intersecting conflict domains, then $t(B)$ is a weak ancestor of
$t$, and $t\in C(B)$.
\end{lemma}
\begin{proof}
Two rooted connected subtrees which intersect have comparable roots.
Every current owner belongs either to an earlier family or to a bag
already reached in this phase. An owner in $T_\ell$ cannot be a
proper descendant of $t$, by the depth order. Suppose an owner
$s\in T_i$, $i<\ell$, were a proper descendant of $t$. Then
$s\in\operatorname{Pred}(t)=t_P(A)$.
The whole subtree of $s$, and hence $C(B)$, would be disjoint
from $C(A)$. This is a contradiction. The roots are therefore
ordered with $t(B)$ above $t$. Connectedness of $C(B)$ shows that
the path from its root to any common node passes through $t$, proving
$t\in C(B)$.
\end{proof}
\begin{lemma}[Unique interior record]\label{ha:unique-interior}
Under the preceding hypotheses, suppose $C(A)\cap C(B)\ne\varnothing$.
If another current record $D\ne B$ intersects $B$, then
$C(A)\cap C(D)=\varnothing$. Consequently a candidate is interior
to at most one current record.
\end{lemma}
\begin{proof}
If both conflict intersections were nonempty,
Lemma~\ref{ha:ancestor} would give $t\in C(B)\cap C(D)$.
This violates condition~\ref{ha:L4} for the intersecting records
$B,D$. If $A$ were interior to both, the two records would
intersect on the nonempty support of $A$, giving the same contradiction.
\end{proof}
\begin{lemma}[Inheritance of separation]\label{ha:heredity}
Suppose $B,D$ satisfy condition~\ref{ha:L4}. If a new record
$B'$ has support contained in $B$ and $C(B')\subseteq C(B)$,
then $B',D$ also satisfy that condition. A concentric radial
restriction of $B$ retaining all its labels also retains
conditions~\ref{ha:L1}--\ref{ha:L3}, if it has positive width.
\end{lemma}
\begin{proof}
An intersection of $B'$ with $D$ is also an intersection of $B$
with $D$, and its conflict intersection is a subset of
$C(B)\cap C(D)$. For a concentric restriction, predecessor
endpoints remain outside the smaller outer radius. The old
inner witness still has distance at most the new inner radius,
and the old crossing paths also cross the restricted radial interval.
The labels and their induced vertex domains are unchanged.
\end{proof}
\begin{lemma}[Border balls stay border balls]\label{ha:border-monotone}
During the processing of this phase, a candidate which is a border
ball never becomes interior. In particular every border ball
retained for the end of a bag's processing remains a border ball
at the end of the phase.
\end{lemma}
\begin{proof}
Consider any single operation before the final phase transition.
A newly inserted original ball has radius $\delta_\ell$ and cannot
contain a candidate with the two radial margins in
\eqref{ha:interior}, since $C_3>1$.
Every other new record is a concentric radial restriction of an
old record, with a subset of its conflict domain. If a candidate
satisfies \eqref{ha:interior} for that new record, it therefore
satisfies it for the old record as well. Unchanged records create
no new interiors. Iterating this observation proves the claim.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_order.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_postprocess.tex ====
\subsubsection{Completing a phase}
\label{ha:postprocess}
We complete the induction in Lemma~\ref{ha:construction} by handling
the border balls. At the end of processing the bags of
$\mathcal F_\ell$, let $\operatorname{Bor}_t$ and
$\operatorname{Int}_t$ be the unprocessed border and interior balls
left by its loop. The loop stops with
$|\operatorname{Int}_t|<|\operatorname{Bag}_t|/2$.
It is enough to give each $t\in T_\ell$ an additional
\[
\frac{C_4}{6C_3}|\operatorname{Bor}_t|\delta_\ell
\]
tokens. Together with the credit already obtained during its loop,
this gives at least
\begin{equation}\label{ha:phase-target}
\frac{C_4}{6C_3}
(|\operatorname{Bag}_t|-|\operatorname{Int}_t|)\delta_\ell
\ \ge\ \frac{C_4}{12C_3}|\operatorname{Bag}_t|\delta_\ell.
\end{equation}
Write $Z$ for the collection just before this last step,
$p(B)=\operatorname{tok}_\ell(B)$, and let $q(B)$ be the token
value of the same unchanged record at the beginning of phase
$\ell+1$. Thus for an original ball inserted in the current phase
both $p(B)$ and $q(B)$ equal $\delta_\ell-C_4\delta_{\ell+1}$.
For all other nonavoiding records the threshold in the positive
part decreases from $C_4\delta_\ell$ to $C_4\delta_{\ell+1}$;
for avoiding records the same formula is divided by $2(C_4+2)$.
In particular $q(B)\ge p(B)$.
Set
\[
b=\sum_{t\in T_\ell}|\operatorname{Bor}_t|,
\qquad e=\sum_{B\in Z}(q(B)-p(B)).
\]
If $b=0$ there is no border credit to supply, and the phase is
complete. If $e\ge (C_4/(6C_3))b\delta_\ell$, retain $Z$ and
distribute these extra tokens among the current nodes in proportion
to $|\operatorname{Bor}_t|$. Every node obtains the required
additional amount, and all earlier credits remain available.
It remains to handle
\begin{equation}\label{ha:small-excess}
e<\frac{C_4}{6C_3}b\delta_\ell.
\end{equation}
Leave current-phase original balls unchanged. Replace every other
record $B$, with center $x$ and numerical radii $r_1C_4\delta_\ell$ and
$\delta_{\ell+1}\le\delta_\ell/3$,
\[
q(B)-p(B)=C_4(\delta_\ell-\delta_{\ell+1})
\ge\frac23 C_4\delta_\ell.
\]
Using the positive-part formula, whether or not the restriction
survives,
\[
p(B)-q(S(B))
\le2(C_3+1)\delta_\ell-C_4(\delta_\ell-\delta_{\ell+1})
\le2C_3\delta_\ell,
\]
where the last step uses $C_4\ge3$.
These two bounds imply \eqref{ha:shrink-comparison}.
For avoiding records both sides of these estimates have the common
factor $1/(2(C_4+2))$, giving exactly the same conclusion.
Summing \eqref{ha:shrink-comparison} and then using
\eqref{ha:small-excess} gives
$\mathsf D\le(3C_3/C_4)e\le b\delta_\ell/2$.
\end{proof}
Each newly inserted border ball has
$\delta_\ell-C_4\delta_{\ell+1}$ tokens. Reserve at most
$\delta_\ell/2$ of these to cover the deficits of the old records.
Lemma~\ref{ha:shrink-cost} guarantees enough in the resulting pool:
if $\mathsf D>0$, distribute the pool in proportion to the individual
deficits, stopping once each is paid; if $\mathsf D=0$, no transfer is
needed. Send the tokens of $S(B)$ together with this payment back
to the old record $B$, and redistribute its former credits by
induction. Each border ball still has at least
\[
\delta_\ell-C_4\delta_{\ell+1}-\frac12\delta_\ell
\ge\frac13\delta_\ell
\ge\frac{C_4}{6C_3}\delta_\ell
\]
tokens for its own node. The first inequality uses
$C_4\lambda\le1/6$; the second follows from the stated lower bound
on $C_3$. This supplies precisely the missing border credit.
Both phase-transition cases preserve all previous credits and
give \eqref{ha:phase-target} to every node of the current family.
Starting with $Z=\varnothing$ and applying the interior construction
and the phase transition for $\ell=1,\ldots,m$ therefore yields
\[
\frac{C_4}{12C_3}
\sum_{i=1}^m\delta_i\sum_{t\in T_i}|\operatorname{Bag}_t|
\le\sum_{B\in Z}\operatorname{tok}_{m+1}(B)
\le\sum_{B\in Z}\operatorname{width}(B).
\]
This proves Lemma~\ref{ha:insertable-arrangement}, completing the
proof of Proposition~\ref{prop:hierarchy-assigned} by the reduction
above. If a countable geometric sequence is used, apply the finite
statement to every initial segment and take the increasing limit
of its nonnegative right-hand mass; no limiting arrangement is
required.
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_postprocess.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_preprocess.tex ====
\subsubsection{Labels, routing domains, and preprocessing}
\label{ha:preprocessing}
Write $\mathcal F_i$ for the family of bags at scale $\delta_i$ and
$\mathcal B_i=\bigcup_{t\in T_i}\operatorname{Bag}_t$ for its balls.
The balls in $\mathcal B_i$ are pairwise disjoint, whereas balls at
different scales need not be disjoint. Throughout this proof all
geometric sets are restricted to the continuous cube $Q=[0,1]^d$.
We abbreviate the common notation $B_Q$ to $B$ in this proof; in particular,
\[
B(x,r)=\{y\in Q:\|x-y\|_1\ell$,
assign to every counted ball one endpoint of an edge in $P(s)$ that
lies in that ball. Pairwise disjointness of the center-inclusive
balls in $\mathcal B_i$ makes this assignment injective on endpoint
vertices. There are at most $2|P(s)|$ such vertices, even when edges
are parallel or several vertices have the same image. Thus the
left-hand side is at most
\begin{align*}
2|P(s)|\sum_{i>\ell}\delta_i
&\le \frac{2\lambda}{1-\lambda}|P(s)|\delta_\ell\\
&\le 4\lambda|P(s)|\delta_\ell
\le \frac{4}{k}|O(s)|\delta_\ell
\le \frac{4}{C_3}|\operatorname{Bag}_s|\delta_\ell.
\end{align*}
The last inequality is precisely the assigned-bag cardinality bound.
\end{proof}
\Needspace*{3\baselineskip}
\begin{lemma}[Charging a valid labeled collection]\label{ha:labeled-energy}
Every finite collection $Z$ with a valid labeling satisfies
\[
\frac{k}{4}\sum_{B\in Z}\operatorname{width}(B)
\le \sum_{\{v,w\}\in E}\|X_v-X_w\|_1.
\]
\end{lemma}
\begin{proof}
Realize each graph edge $e=\{v,w\}$ by one fixed straight segment
from $X_v$ to $X_w$ in $Q$, of length $\ell_e=\|X_v-X_w\|_1$.
Different parallel edges are distinct resources even if their
segments coincide geometrically. Concatenating these segments
realizes a graph path as a continuous curve.
Fix a record $B$ with center $x$ and radii $a1$.
Choose another ball in the bag, with center vertex $w\in V(t)$.
Disjointness of the two open balls gives $X_w\notin B$, so
$\|X_u-X_w\|_1\ge\delta_i$. Since $G[V(t)]$ is
$k$-edge-connected, Lemma~\ref{ha:edge-paths} supplies
$k$ pairwise edge-disjoint $u$--$w$ paths in this induced graph.
These witness \ref{ha:L3}, with inner radius zero, and in fact give
the stronger count $k$ in place of $k/4$.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_preprocess.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_bags.tex ====
\subsection{From the dual numerator to bags of balls}\label{hb:section}
We give the geometric construction with explicit losses. No boundary
ratio or connectivity assumption is used in this construction; those
assumptions enter the subsequent charging estimates. Throughout this
subsection, $\mathcal T$ is a hierarchy of a finite graph $G=(V,E)$,
$X_v\in\{0,1\}^d$, and $U:\mathbb R^d\to\mathbb R^E$ is a linear
contraction. For an oriented edge $e=uv$, put
\[
X_e=X_u-X_v,\qquad a_e=\langle u_e,X_e\rangle,\qquad
d_e=\|X_e\|_2^2=\|X_e\|_1.
\]
Here $u_e^{\mathsf T}$ is row $e$ of $U$. We assume $a_e\ge0$; multiplying individual
rows by signs preserves contraction and replaces each $a_e$ by $|a_e|$,
which can only increase every squared boundary sum under consideration.
In particular $a_e^2\le d_e$. An edge is counted with its multiplicity
and occurs in at most two sets $O(t)$.
\begin{definition}[Balls, bags, and geometric sequences]\label{hb:definitions}
Set $Q=[0,1]^d$ and
\[
B_Q(x,r)=\{y\in Q:\|y-x\|_10).
\]
A \emph{bag} is a nonempty collection of pairwise disjoint such balls,
all of the same radius and with centers among the $X_v$. Its type is
$(\delta)$ when that radius is $\delta$, and its type is $(\delta,\Delta)$
when, in addition, all distances between its centers are at most
$\Delta$. Its size $|\mathrm{Bag}|$ is its number of balls.
For $\beta>1$, a bag of type $(\delta,\Delta)$ is
\emph{$\beta$-compact} if
\[
|\mathrm{Bag}|\ge2,\qquad
\beta\Delta\le\delta|\mathrm{Bag}|.
\]
The midpoint of two centers belongs to $Q$, so disjoint radius-$\delta$
balls have centers at distance at least $2\delta$. Hence a compact bag
has $\Delta\ge2\delta$.
A bag of radius $\delta$ is \emph{$\eta$-assigned to $t$} if
\[
|\mathrm{Bag}_t|\ge\eta|O(t)|,
\]
and every ball has a center $X_u$ with $u\in V(t)$ and an edge
$uv\in O(t)$ such that $d_{uv}<\delta$. A \emph{family} of bags is
nonempty, and all balls in all its bags are mutually disjoint.
A compact family has type $(\delta,\Delta)$ when its bags have that
common type. An assigned family has type $(\delta,T)$ when its bags
are assigned to distinct nodes in $T$ and have radius $\delta$.
For $0<\lambda<1$, a sequence of compact families of types
$(\delta_i,\Delta_i)$ is \emph{$\lambda$-geometric} if
$\Delta_{i+1}<\lambda\delta_i$ for all successive families.
A sequence of assigned families of types $(\delta_i,T_i)$ is
$\lambda$-geometric if $\delta_{i+1}<\lambda\delta_i$ and the sets
$T_i$ are pairwise disjoint. Its \emph{mass} is
\[
\mathsf M=\sum_i\delta_i
\sum_{\mathrm{Bag}\in\mathcal F_i}|\mathrm{Bag}|.
\]
\end{definition}
\input{sections/hierarchy_bags_spectral}
\subsubsection{Homogeneity and the two constructions}
\begin{definition}[Bad nodes and homogeneous subsets]\label{hb:bad}
For $0<\alpha\le1$, a nonroot node $t$ with $O(t)\ne\varnothing$
is \emph{$\alpha$-bad} if
\[
\left(\frac{\sum_{e\in O(t)}a_e}{|O(t)|}\right)^2
\ge\frac{\alpha}{|O(t)|}\sum_{e\in O(t)}d_e.
\]
Only nodes with a positive boundary sum need be retained.
A set of edges is \emph{$c$-homogeneous} if its $a_e^2$ are positive
and any two of them have ratio less than $c$, and the same holds for
its $d_e$. A subset $O'(t)\subseteq O(t)$ is
\emph{$\gamma$-dominating} if
\[
\left(\sum_{e\in O'(t)}a_e\right)^2
\ge\gamma\left(\sum_{e\in O(t)}a_e\right)^2.
\]
\end{definition}
\begin{lemma}[Two elementary truncations]\label{hb:bucketing}
Define
\[
J=1+\left\lceil\log_2(256/\alpha^2)\right\rceil,
\qquad \gamma=\frac1{4J^4}.
\]
Every $\alpha$-bad node with a positive boundary sum admits a
$2$-homogeneous, $\gamma$-dominating subset $O'(t)$.
\end{lemma}
\begin{proof}
Fix the node, let $m=|O(t)|$, and let expectations be uniform on $O(t)$.
Writing $\mu=\mathbb E a_e>0$, badness says
$\mathbb E d_e\le\mu^2/\alpha$. Discard edges for which
$a_e<\mu/4$ or $d_e>16\mu^2/\alpha^2$. The first class contributes
at most $\mu/4$ to $\mathbb E a_e$. For the second class, Markov's
inequality gives probability at most $\alpha/16$, and therefore
Cauchy--Schwarz and $a_e^2\le d_e$ give
\[
\mathbb E\bigl[a_e\mathbf1_{\{d_e>16\mu^2/\alpha^2\}}\bigr]
\le\sqrt{\mathbb E a_e^2\,
\mathbb P\{d_e>16\mu^2/\alpha^2\}}
\le\mu/4.
\]
The remaining edges contribute at least $m\mu/2$ to the boundary sum.
On those edges both $a_e^2$ and $d_e$ lie in
$[\mu^2/16,16\mu^2/\alpha^2]$. Divide this interval into half-open
dyadic intervals, with an extra last interval if needed. There are
at most $J$ choices for each quantity and at most $J^2$ pairs of
choices. Some pair contains edges whose $a_e$ sum is at least
$m\mu/(2J^2)$. Its edges are $2$-homogeneous, and squaring this
last estimate gives the asserted dominance.
\end{proof}
\begin{lemma}[One homogeneous family]\label{hb:homogeneous-bags}
Let $T$ be a nonempty set of $\alpha$-bad nodes with positive boundary
sums, and let $0<\gamma\le1$. Suppose that $O'(t)$ is
$\gamma$-dominating for each $t\in T$
and that $F=\bigcup_{t\in T}O'(t)$ is $4$-homogeneous. Write
\[
s=\frac{\alpha\gamma}{32},\qquad
c_1=\min_{e\in F}a_e^2,
\qquad
S'=\sum_{t\in T}\frac1{|O(t)|}
\left(\sum_{e\in O'(t)}a_e\right)^2.
\]
For $\beta>1$ and $0<\epsilon<1/3$, put
$C=C_1(\epsilon)=1024\epsilon^{-2}$. If
\begin{equation}\label{hb:smallness}
s^\epsilon\le\frac1{48\beta C},
\end{equation}
there is either a family of $\beta$-compact bags or a family of
$s^{1+2\epsilon}$-assigned bags, assigned to a subset of $T$, whose
mass is at least
\begin{equation}\label{hb:one-mass}
\frac{s^\epsilon}{192\beta C}\,S'.
\end{equation}
Its radius, and also its diameter parameter in the compact case,
belong to $[sc_1,12c_1/s]$.
\end{lemma}
\begin{proof}
Set $m_t=|O(t)|$, $m'_t=|O'(t)|$,
$N=\sum_{t\in T}m_t$, $N'=|F|$, and $c_2=\max_{e\in F}d_e$.
The sets $O'(t)$ are nonempty. Homogeneity, dominance, and badness
imply, for each $t$,
\[
4c_1(m'_t)^2
\ge\left(\sum_{O'(t)}a_e\right)^2
\ge\gamma\left(\sum_{O(t)}a_e\right)^2
\ge\alpha\gamma m_t\sum_{O(t)}d_e
\ge\frac{\alpha\gamma}{4}\,m_tm'_tc_2.
\]
Cancel $m'_t$ and sum. Since
$\sum_t m'_t\le2N'$, we obtain
\begin{equation}\label{hb:density}
c_1N'\ge sNc_2.
\end{equation}
Also $N\ge N'$ and $c_1\le c_2$, since $a_e^2\le d_e$.
Consequently
\[
s\le\widetilde\alpha:=sN/N'\le c_1/c_2\le1.
\]
Let $Y_v=UX_v$. The row-$e$ coordinate of $Y_u-Y_v$ is $a_e$.
Moreover $\|Y_u-Y_v\|_2^2\le d_e$, so
\[
(\mathbb E_{e\in F}a_e)^2
\ge c_1\ge\widetilde\alpha c_2
\ge\widetilde\alpha\mathbb E_{e\in F}\|Y_e\|_2^2.
\]
Lemma~\ref{hb:spectral-packing} yields $b$ disjoint Euclidean balls
with squared radius $r$ and centers at endpoint images $Y_v$, with
\[
b\ge\widetilde\alpha N'/C,
\qquad br\ge\widetilde\alpha^\epsilon c_1N'/C.
\]
Their center distances squared are at least $4r$. Contraction and
the binary-coordinate identity therefore give $\|X_u-X_v\|_1\ge4r$
for distinct selected centers. Thus the corresponding $Q$-balls of
radius $r$ are disjoint. Shrink their common radius to $\delta$ so that
\begin{equation}\label{hb:normalized-mass}
b\delta=w:=\widetilde\alpha^\epsilon c_1N'/C.
\end{equation}
Call this family of $b$ small balls $\mathcal A$.
There are at most $2N'$ distinct endpoint centers. It follows that
\[
\frac{s^\epsilon c_1}{2C}\le\delta
\le c_1\widetilde\alpha^{\epsilon-1}\le c_1/s.
\]
As $\epsilon<1/2$, condition~\eqref{hb:smallness} implies
$s^{1-\epsilon}\le s^\epsilon\le1/(2C)$; hence
\begin{equation}\label{hb:radius-range}
sc_1\le\delta\le c_1/s.
\end{equation}
Finally, homogeneity and the multiplicity bound show
\begin{equation}\label{hb:numerator-mass}
S'\le4c_1\sum_t\frac{(m'_t)^2}{m_t}
\le8c_1N'\le8Cs^{-\epsilon}w.
\end{equation}
Let $V'(t)$ consist of the endpoints of $O'(t)$ that lie in $V(t)$,
and let $V'=\bigcup_tV'(t)$. Define
$D=\max\{\delta,2c_2\}$. Choose a maximal disjoint collection
$\mathcal B$ of radius-$D$ balls centered at $X_u$ for $u\in V'$.
Every such center is within $2D$ of a chosen center: otherwise its ball
could be added. Each center of a small ball is an endpoint of an edge
of $F$, so it is within $c_2$ of a point of $V'$, and hence within $3D$
of a chosen center.
If $|\mathcal B|1$.
Their balls are still mutually disjoint and their mass is at least
$w/2$, which implies~\eqref{hb:one-mass}.
In the other case, $|\mathcal B|\ge w/(12\beta D)$, assign each ball
of $\mathcal B$ to one node $t$ for which its center belongs to $V'(t)$.
Keep the bag assigned to $t$ when
\[
|\mathrm{Bag}_t|\ge\frac{|\mathcal B|m_t}{2N}.
\]
Discarding the other bags loses fewer than $|\mathcal B|/2$ balls.
For each retained ball its center is in $V(t)$ and some edge of
$O'(t)$ has length at most $c_21$, $0<\epsilon<1/3$, $0<\lambda<1$, and
$s^\epsilon\le(48\beta C_1(\epsilon))^{-1}$.
There is a $\lambda$-geometric sequence of families, consisting either
entirely of $\beta$-compact bags or entirely of
$s^{1+2\epsilon}$-assigned bags assigned to distinct nodes of $T$,
whose mass satisfies
\begin{equation}\label{hb:extraction-bound}
\mathsf M\ge
\frac{s^\epsilon}{384\beta C_1(\epsilon)C_2(\alpha)LH}
\sum_{t\in T}\frac1{|O(t)|}
\left(\sum_{e\in O(t)}a_e\right)^2.
\end{equation}
In particular, all losses are functions of $\alpha,\epsilon,\beta$
and $\lambda$, independent of the number of vertices and hierarchy depth.
\end{proposition}
\begin{proof}
Lemma~\ref{hb:bucketing} gives $2$-homogeneous subsets $O'(t)$ with
$\gamma=1/(4J^4)=32/C_2(\alpha)$. Define
\[
A_t=\min_{e\in O'(t)}a_e^2,
\qquad B_t=\min_{e\in O'(t)}d_e,
\qquad s_t=\frac{(\sum_{O'(t)}a_e)^2}{|O(t)|}.
\]
All are positive. For $m=|O(t)|$ and $m'=|O'(t)|$, the same
pointwise argument used above, now with $2$-homogeneity, gives
\[
2A_t(m')^2\ge\gamma\left(\sum_{O(t)}a_e\right)^2
\ge\alpha\gamma mm'B_t.
\]
Consequently
\begin{equation}\label{hb:local-scale-ratio}
1\le B_t/A_t\le2/(\alpha\gamma)=1/(16s).
\end{equation}
Partition the nodes according to the two integers
$n=\lfloor\log_2 A_t\rfloor$ and
$m=\lfloor\log_2 B_t\rfloor$. For each fixed $n$,
\eqref{hb:local-scale-ratio} allows at most $L$ values of $m$.
Retain the value $m(n)$ maximizing the sum of the $s_t$ over that group,
and call the resulting node set $T_n$. Summing over $n$ yields
\begin{equation}\label{hb:retained-sum}
\sum_n\sum_{t\in T_n}s_t
\ge\frac1L\sum_{t\in T}s_t
\ge\frac1{C_2(\alpha)L}
\sum_{t\in T}\frac{(\sum_{O(t)}a_e)^2}{|O(t)|}.
\end{equation}
The last inequality uses $\gamma\ge1/C_2(\alpha)$.
The union of the $O'(t)$ over $T_n$ is $4$-homogeneous: its $a_e^2$
lie in $[2^n,2^{n+2})$ and its $d_e$ in
$[2^{m(n)},2^{m(n)+2})$. Apply
Lemma~\ref{hb:homogeneous-bags} to every nonempty $T_n$.
Let $\mathcal F_n$ be the resulting family. Its radius is at least
$s2^n$ and at most $24\,2^n/s$; the latter upper bound also holds for
its compact diameter parameter. Its mass is at least
$s^\epsilon\sum_{t\in T_n}s_t/(192\beta C_1(\epsilon))$.
Partition these families by their integer $n$ modulo $H$ and by whether
they are compact or assigned. One of the $2H$ resulting classes has
at least $1/(2H)$ of their total mass. Order that class by decreasing
$n$. If $n'$ follows $n$, then $n'\le n-H$, and the definition of $H$
implies
\[
\frac{24\,2^{n'}}s
\le\frac{24\,2^{n-H}}s
<\lambda s2^n.
\]
This verifies the geometric condition, including the stronger diameter
condition for compact families. Assigned nodes are distinct across the
sequence because the original $T_n$ are disjoint and each construction
uses only a subset of its own $T_n$. Finally combine its $1/(2H)$ mass
share with~\eqref{hb:retained-sum} and the mass guarantee for each
$\mathcal F_n$. This is exactly~\eqref{hb:extraction-bound}.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_bags.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_bags_spectral.tex ====
\subsubsection{Spectral packing}
\label{hb:spectral-subsection}
We first prove the geometric estimate underlying the construction of
bags. It is the spectral packing statement of
\cite[Lemma~6.4]{AOG}; the argument below gives a logarithmic bound and
chooses the radius explicitly.
Here a Euclidean ball of \emph{squared radius} \(r\) means
\[
\mathcal B_2(y,r)=\{z:\|z-y\|_2^2\le r\}.
\]
In particular, two such closed balls are disjoint when their centers
are at distance strictly greater than \(2\sqrt r\).
\begin{lemma}[Spectral packing]\label{hb:spectral-packing}
Let \(F\) be a nonempty set of oriented edges of a finite multigraph
with edge set \(E\), and put \(m=|F|\).
For points \(Y_v\in\R^E\), write
\(Y_e=Y_u-Y_v\) when \(e=(u,v)\), and denote the \(e\)-coordinate of
\(Y_e\) by \(Y_{e,e}\).
Suppose that \(a>0\) and
\begin{equation}\label{hb:spectral-assumption}
\Upsilon:=\left(\frac1m\sum_{e\in F}Y_{e,e}\right)^2>0,
\qquad
\Upsilon\ge\frac a m\sum_{e\in F}\|Y_e\|_2^2.
\end{equation}
Then \(a\le1\), and there are \(b\ge2\) pairwise disjoint Euclidean
balls of one positive squared radius \(r\), centered at images of
endpoints of edges in \(F\), such that
\begin{equation}\label{hb:spectral-logarithmic}
b\ge\frac{am}{16},
\qquad
br\ge\frac{9m\Upsilon}
{512\bigl(5+\log_2(1/a)\bigr)^2}.
\end{equation}
Consequently, for every \(0<\varepsilon<1/3\), the choice
\begin{equation}\label{hb:spectral-constant}
C_1(\varepsilon)=\frac{1024}{\varepsilon^2}
\end{equation}
gives
\begin{equation}\label{hb:spectral-conclusion}
b\ge\frac{a|F|}{C_1(\varepsilon)},
\qquad
br\ge\frac{a^\varepsilon\Upsilon|F|}{C_1(\varepsilon)}.
\end{equation}
\end{lemma}
\begin{proof}
The scalar Cauchy--Schwarz inequality gives
\[
\Upsilon\le\frac1m\sum_{e\in F}Y_{e,e}^2
\le\frac1m\sum_{e\in F}\|Y_e\|_2^2.
\]
The last quantity is positive, so the assumption implies \(a\le1\).
\smallskip
\noindent\emph{The matrix estimate.}
Let \(P_F:\R^E\to\R^F\) be coordinate restriction, and form the
\(m\)-by-\(m\) matrix \(A\) whose column indexed by \(e\in F\)
is \(P_FY_e\). Set \(\tau=m\sqrt\Upsilon\).
The singular values \(\sigma_1\ge\cdots\ge\sigma_m\ge0\) of \(A\)
satisfy
\begin{equation}\label{hb:spectral-matrix-bounds}
\sum_{i=1}^m\sigma_i\ge|\tr A|=\tau,
\qquad
\sum_{i=1}^m\sigma_i^2=\|A\|_F^2
\le\frac{\tau^2}{am}.
\end{equation}
Indeed, writing a singular value decomposition as
\(A=\sum_i\sigma_i u_i v_i^{\mathsf T}\), the trace is
\(\sum_i\sigma_i\langle u_i,v_i\rangle\), whose absolute value
is at most \(\sum_i\sigma_i\). The Frobenius norm identity follows
from orthonormality, and its upper bound follows from
\eqref{hb:spectral-assumption} and the fact that coordinate restriction
does not increase a vector's norm.
We will also use the following rank approximation inequality:
for \(0\le k\le m\) and any matrix \(C\) of rank at most \(k\),
\begin{equation}\label{hb:spectral-rank-bound}
\|A-C\|_F^2\ge\sum_{i=k+1}^m\sigma_i^2.
\end{equation}
For completeness, let \(Q\) be orthogonal projection onto the column
space of \(C\). Since \((I-Q)C=0\), orthogonal projection and the
singular value decomposition give
\[
\|A-C\|_F^2
\ge\|(I-Q)A\|_F^2
=\sum_{i=1}^m\sigma_i^2\bigl(1-\|Qu_i\|_2^2\bigr).
\]
The numbers \(w_i=\|Qu_i\|_2^2\) lie in \([0,1]\), and
\(\sum_iw_i=\rank Q\le k\).
Because the \(\sigma_i^2\) are nonincreasing,
\(\sum_i\sigma_i^2w_i\le\sum_{i=1}^k\sigma_i^2\):
moving available weight from a later index to an earlier index never
decreases this weighted sum, and its maximum therefore puts weight one
on the first \(k\) indices. This proves
\eqref{hb:spectral-rank-bound}, including \(k=0\).
\smallskip
\noindent\emph{Selecting a singular-value tail.}
Define
\[
p_0=\left\lfloor\frac{am}{16}\right\rfloor+1,
\qquad T_p=\sum_{i=p}^m\sigma_i^2\quad(1\le p\le m).
\]
We have \(1\le p_0\le m\). By \eqref{hb:spectral-matrix-bounds},
\[
\sum_{i\frac{am}{16},
\qquad
pT_p\ge\frac{9\tau^2}{16L^2}>0.
\end{equation}
\smallskip
\noindent\emph{Selecting the balls at an explicit radius.}
Fix the positive number
\begin{equation}\label{hb:spectral-radius}
r=\frac{T_p}{32m}.
\end{equation}
Scan the endpoint images of edges in \(F\), keeping a point precisely
when its distance from every previously kept point is greater than
\(2\sqrt r\). This finite procedure produces centers
\(Y_{w_1},\ldots,Y_{w_b}\) for pairwise disjoint closed balls of
squared radius \(r\). Its maximality also ensures that each endpoint
image \(Y_v\) lies within distance \(2\sqrt r\) of one of the
centers; choose such a center and call its vertex \(c(v)\).
If \(b\le p\), define a matrix \(C\) by
\[
C_e=P_F\bigl(Y_{c(u)}-Y_{c(v)}\bigr)
\qquad(e=(u,v)\in F).
\]
Every column of \(C\) belongs to the span of
\(P_F(Y_{w_j}-Y_{w_1})\), \(2\le j\le b\), so
\(\rank C\le b-1\le p-1\). On the other hand,
\begin{align*}
\|A-C\|_F^2
&\le\sum_{e=(u,v)\in F}
\bigl\|(Y_u-Y_{c(u)})-(Y_v-Y_{c(v)})\bigr\|_2^2\\
&\le\sum_{e=(u,v)\in F}
2\bigl(\|Y_u-Y_{c(u)}\|_2^2+
\|Y_v-Y_{c(v)}\|_2^2\bigr)
\le16mr=\frac{T_p}{2}.
\end{align*}
This contradicts \eqref{hb:spectral-rank-bound} with \(k=p-1\),
which bounds the same quantity below by \(T_p>0\).
Thus \(b\ge p+1\ge2\). Combining
\eqref{hb:spectral-large-tail} and \eqref{hb:spectral-radius} yields
\[
b>\frac{am}{16},
\qquad
br\ge\frac{pT_p}{32m}
\ge\frac{9m\Upsilon}{512L^2}.
\]
The bound on \(L\) proves \eqref{hb:spectral-logarithmic}.
\smallskip
\noindent\emph{Conversion to the power bound.}
Put \(t=\log(1/a)\ge0\). Since \(\log2\ge1/2\),
\(5+\log_2(1/a)\le5+2t\).
The elementary maximum of \(t e^{-\varepsilon t/2}\) is
\(2/(e\varepsilon)\le1/\varepsilon\), and
\(5\le5/(3\varepsilon)\) for \(0<\varepsilon<1/3\).
Consequently,
\[
\bigl(5+\log_2(1/a)\bigr)e^{-\varepsilon t/2}
\le5+\frac2\varepsilon<\frac4\varepsilon.
\]
Squaring and substituting in \eqref{hb:spectral-logarithmic} gives
\[
br\ge\frac{9\varepsilon^2}{8192}
a^\varepsilon m\Upsilon
\ge\frac{\varepsilon^2}{1024}
a^\varepsilon m\Upsilon.
\]
Finally \(C_1(\varepsilon)\ge16\), so the count estimate in
\eqref{hb:spectral-conclusion} follows as well.
\end{proof}
The positivity assumption on \(\Upsilon\) is needed when one asks for
many distinct centers. If \(\Upsilon=0\),
\eqref{hb:spectral-assumption} forces \(Y_e=0\) for every \(e\in F\),
and all endpoint images may coincide. Such a set contributes zero to
the squared sums for which this lemma is used and can be discarded.
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_bags_spectral.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_compact.tex ====
\subsection{Charging compact bags}
\label{hc:section}
We prove the compact-bag estimate, including its geometric charging
step. The argument follows the construction underlying
\cite[Proposition~7.1 and Section~7.1]{AOG}; the proof below includes the
boundary conventions, the positive-part accounting, and the invariants
needed when the scale changes.
\begin{proposition}[Compact-bag charging]
\label{prop:hierarchy-compact}
Let \(G=(V,E)\) be a finite \(k\)-edge-connected multigraph, and let
\(X_v\in Q=[0,1]^h\) for \(v\in V\).
Suppose \((\mathcal F_i)\) is a finite or countable
\(\lambda\)-geometric sequence of nonempty families of
\(\beta\)-compact bags, of respective types \((\delta_i,\Delta_i)\), where
\(0<\lambda\le 1/12\) and \(\beta\ge36\). Thus all balls in
\(\mathcal F_i\) are mutually disjoint ordinary balls
\(B_Q(X_v,\delta_i)\), every bag \(D\in\mathcal F_i\) has at least two
balls and center diameter at most \(\Delta_i\), and
\[
\beta\Delta_i\le |D|\delta_i,
\qquad
\Delta_{i+1}\le\lambda\delta_i.
\]
Then
\begin{equation}
\label{hc:conclusion}
\frac{k}{4}\sum_i\delta_i\sum_{D\in\mathcal F_i}|D|
\le \sum_{e\in E}\|X_e\|_1,
\qquad X_{\{u,v\}}=X_u-X_v.
\end{equation}
\end{proposition}
An ordinary ball is \(B_Q(x,r)=\{y\in Q:\|y-x\|_10\), and let \(X_v\in Q=[0,1]^h\) for \(v\in V\).
Let \(\mathcal Z\) be a finite collection of pairwise disjoint ordinary
or hollowed balls in \(Q\). For each \(H\in\mathcal Z\), write
\(x_H,a_H,b_H\) for its center and numerical inner and outer radii.
Suppose there are vertices \(u_H,v_H\in V\) such that
\begin{equation}
\label{hc:witness}
\|X_{u_H}-x_H\|_1\le a_H,
\qquad \|X_{v_H}-x_H\|_1\ge b_H.
\end{equation}
Then
\begin{equation}
\label{hc:length-bound}
k\sum_{H\in\mathcal Z}(b_H-a_H)
\le \sum_{\{u,v\}\in E}\|X_u-X_v\|_1.
\end{equation}
\end{lemma}
\begin{proof}
For \(H\in\mathcal Z\), clamp the radial distance to its radial
interval:
\[
f_H(y)=\min\{b_H,\max\{a_H,\|y-x_H\|_1\}\}.
\]
For every \(a_H0\), then
\(t=w-6\Delta_i\). The widths of the two shells sum to
\(w-(R-L)-2\delta_i\), including zero-width shells formally, so
\begin{align}
\label{hc:split-capacity}
&p_i(H_-)+p_i(H_+)+n(\delta_i-6\Delta_{i+1})\notag\\
&\qquad\ge w-(R-L)-2\delta_i-12\Delta_i
+\frac{n\delta_i}{2}\notag\\
&\qquad\ge t+\frac{n\delta_i}{2}-8\Delta_i
\ge t+\frac{n\delta_i}{4}.
\end{align}
The first bound uses \([s]_+\ge s\), also when a shell is discarded.
The second uses \(R-L\le\Delta_i\) and
\(2\delta_i\le\Delta_i\). The last uses
\(n\delta_i\ge \beta\Delta_i\) and \(\beta\ge36\ge32\).
Unchanged objects keep their capacities. Thus (iii) also survives,
with the new bag included on its right-hand side. Each such operation
processes one new bag, so the loop ends after finitely many steps.
\paragraph{Inserting the remaining bags and changing scale.}
At the end of the loop, let \(\mathcal R_i\) be the unprocessed bags.
None of their balls satisfies \eqref{hc:interior} for any live object.
Set
\(s_i=2\delta_i+\Delta_i\).
Retain every fresh ball. For each old object with numerical radii
\(a,b\), replace it by
\begin{equation}
\label{hc:shrink}
H^{\mathrm{sh}}=B_Q(x;a+s_i,b-s_i)
\quad\text{if }b-a>2s_i,
\end{equation}
and otherwise discard it. Insert every ball of every bag in
\(\mathcal R_i\), and mark those bags processed. We now regard all
surviving objects as old objects at the beginning of phase \(i+1\).
After phase \(q\), this is just a final accounting state with
\(\Delta_{q+1}=0\) and capacity equal to width.
Shrinking preserves pairwise disjointness among old objects and
preserves their witnesses: increasing the inner radius and decreasing
the outer radius only weakens the witness conditions. A remaining
ball \(B_Q(z,\delta_i)\) is disjoint from each retained fresh ball,
because both belong to \(\mathcal F_i\). For an old object, failure
of \eqref{hc:interior} says that at least one of
\[
\|z-x\|_1b-\delta_i-\Delta_i
\]
holds. In the first case every point of \(B_Q(z,\delta_i)\) has
radial distance less than \(a+s_i\); in the second every such point
has radial distance greater than \(b-s_i\). In either case this ball
avoids \(H^{\mathrm{sh}}\). All newly inserted balls are mutually
disjoint by the family assumption, and their witnesses are again
their own centers and another center in the same bag. This verifies
(i) and (ii) after the transition, including the center condition.
It remains to verify (iii) across the change in its definition of
capacity. A retained fresh ball has capacity
\(\delta_i-6\Delta_{i+1}\) both before and after the transition.
For a surviving old object, the new capacity is
\([
w-2s_i-6\Delta_{i+1}]_+\). By \eqref{hc:scales},
\begin{equation}
\label{hc:reserve}
2s_i+6\Delta_{i+1}
=2\Delta_i+4\delta_i+6\Delta_{i+1}
\le2\Delta_i+\frac92\delta_i
\le\frac{17}{4}\Delta_i
\le6\Delta_i.
\end{equation}
Thus its new capacity is at least \([w-6\Delta_i]_+\), its old
capacity. If an old object is discarded, then
\(w\le2s_i\le4\Delta_i\), so its old capacity was zero.
Finally, every ball inserted from \(\mathcal R_i\) contributes
\(\delta_i-6\Delta_{i+1}\ge\delta_i/2\) in the new state. These
capacities pay at least \(|D|\delta_i/4\) for each newly processed
bag \(D\). No previous capacity decreases, so
\eqref{hc:potential-invariant} holds at the start of the next phase.
After phase \(q\), every bag in the chosen initial sequence has been
processed and the capacity of each live object equals its width.
The final collection \(\mathcal Z_{\mathrm{fin}}\) is disjoint and
has both witnesses for every object. The potential invariant and
Lemma~\ref{hc:length} give
\[
\frac14\sum_{i=1}^q\delta_i\sum_{D\in\mathcal F_i}|D|
\le\sum_{H\in\mathcal Z_{\mathrm{fin}}}w(H)
\le\frac1k\sum_{e\in E}\|X_e\|_1.
\]
For a countable sequence, its nonnegative sum is the supremum of
these finite initial sums. Taking that supremum proves
\eqref{hc:conclusion}.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_compact.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_dual.tex ====
\subsection{The dual reduction for a hierarchy}
\label{app:hierarchy-dual}
This section proves the matrix-to-embedding reduction needed for the
hierarchy estimate. The marked nodes may be any subset of the nonroot
nodes. In fact, the only hierarchical property used in this reduction is
that an edge belongs to at most two of the sets $O(t)$.
Let $G=(V,E)$ be a connected loopless multigraph, with $n=|V|\geq2$
and $m=|E|$. Fix an orientation of every edge, write $b_e$ for its
incidence column, and put
\[
B=[b_e]_{e\in E},\qquad L_G=BB^{\mathsf T},\qquad
\mathcal C=\{S:\varnothing\ne S\subsetneq V\},\qquad
d_S=|\delta_G(S)|.
\]
Thus $d_S=\mathbf1_S^{\mathsf T}L_G\mathbf1_S>0$ for $S\in\mathcal C$.
Let $\mathcal M$ be the set of marked nodes, and assume that
$O(t)\ne\varnothing$ for $t\in\mathcal M$. Define the value of
the shortcut program by an infimum:
\begin{equation}
\label{hd:primal}
p_*=
\inf_{\substack{D\succ0\\
\mathbf1_S^{\mathsf T}D\mathbf1_S\leq d_S\ (S\in\mathcal C)}}
\ \max_{t\in\mathcal M}
\frac1{|O(t)|}\sum_{e\in O(t)} b_e^{\mathsf T}D^{-1}b_e.
\end{equation}
Here and throughout this section, $D\succ0$ means positive definite on
the full space $\mathbb R^V$. No constraint for $S=V$ is imposed.
When $\mathcal M=\varnothing$, set the objective and $p_*$ equal to zero.
For a binary matrix $X\in\{0,1\}^{h\times V}$, let
\[
\mathcal E(X)=\sum_{e\in E}\|Xb_e\|_2^2.
\]
A matrix $U\in\mathbb R^{E\times h}$ will be called
\emph{row semiorthogonal} if $UU^{\mathsf T}=I_m$; its row indexed by
$e$ is denoted by $u_e^{\mathsf T}$. Thus the vectors $u_e\in\mathbb R^h$
are orthonormal, and this convention requires $h\geq m$. The dimension
$h$ is otherwise arbitrary. Zero rows can always be added to $X$.
\Needspace*{3\baselineskip}
\begin{lemma}[Dual reduction]
\label{lem:hierarchy-dual}
With the preceding notation, set
\begin{equation}
\label{hd:ratio}
Q_*=
\sup_{\substack{h\geq m,\ X\in\{0,1\}^{h\times V},\ \mathcal E(X)>0\\
U\in\mathbb R^{E\times h},\ UU^{\mathsf T}=I_m}}
\frac{\displaystyle
\sum_{t\in\mathcal M}\frac1{|O(t)|}
\left(\sum_{e\in O(t)}\langle u_e,Xb_e\rangle\right)^2}
{\mathcal E(X)}.
\end{equation}
Then
\begin{equation}
\label{hd:comparison}
p_*\leq Q_*\leq2p_*.
\end{equation}
Consequently, if every ratio in \eqref{hd:ratio} is at most $K$, then for
every $\eta>0$ there is a full positive definite matrix $D$ satisfying
all the cut constraints in \eqref{hd:primal} and all the marked-node
average-resistance bounds with right side $K+\eta$.
\end{lemma}
\begin{proof}
The assertion for an empty marked set follows by taking a sufficiently
small positive multiple of the identity, so assume $\mathcal M\ne\varnothing$.
We give the finite-dimensional duality argument as well as the matrix
and embedding steps.
\paragraph{Separation in finite dimension.}
We use the following elementary geometric fact: if $\mathcal U$ is a
nonempty open convex subset of a Euclidean space and $a\notin\mathcal U$,
there is a nonzero vector $v$ such that
$\langle v,x-a\rangle\geq0$ for every $x\in\mathcal U$.
Here is a proof. Choose $y\in\mathcal U$ and put
$a_j=a+(a-y)/j$. None of the points $a_j$ belongs to
$K=\overline{\mathcal U}$. Otherwise $a$, being a strict convex
combination of $y\in\mathcal U$ and $a_j\in K$, would belong to
$\mathcal U$: an open ball about $y$, convexly combined with points of
$\mathcal U$ approaching $a_j$, gives an open ball about $a$ in
$\mathcal U$. Choose a nearest point $z_j\in K$ to $a_j$.
Such a point exists by minimizing distance on a sufficiently large
closed ball. Convexity and differentiation of squared distance along
the segment from $z_j$ to any $x\in K$ give
\[
\langle z_j-a_j,x-z_j\rangle\geq0.
\]
Hence, for $v_j=(z_j-a_j)/\|z_j-a_j\|_2$,
$\langle v_j,x-a_j\rangle\geq\|z_j-a_j\|_2\geq0$.
A convergent subsequence of the unit vectors $v_j$ has a unit limit
$v$, which has the stated property since $a_j\to a$.
\paragraph{Strong duality for this program.}
Put
\[
A_t=\frac1{|O(t)|}\sum_{e\in O(t)}b_eb_e^{\mathsf T},\qquad
f_t(D)=\operatorname{tr}(A_tD^{-1}),\qquad
g_S(D)=\mathbf1_S^{\mathsf T}D\mathbf1_S-d_S.
\]
Each $f_t$ is convex on $D\succ0$. Indeed, completing the square gives
\[
b^{\mathsf T}D^{-1}b
=\sup_{x\in\mathbb R^V}
\bigl(2b^{\mathsf T}x-x^{\mathsf T}Dx\bigr),
\]
a supremum of affine functions of $D$. The functions $g_S$ are affine.
Choose
\[
0<\varepsilon_0<\min_{S\in\mathcal C}\frac{d_S}{|S|},
\qquad D_0=\varepsilon_0 I.
\]
Then all cut constraints are strict at $D_0$. In particular
$0\leq p_*<\infty$.
Consider the open convex set of vectors $(a,b,s)$ for which there are
$D\succ0$ and $r\in\mathbb R$ such that
\[
f_t(D)-r0$. To see this, choose
$r_0>\max_t f_t(D_0)$; there is then a point of the set with all the
$a_t$ and $b_S$ negative. If $\alpha=0$, this would contradict the
separation inequality and the nonzero, nonnegative vector $(\lambda,y)$.
Normalize $\alpha=1$ and take limits down to the displayed strict
inequalities. For every $D\succ0$ and every $r\in\mathbb R$ this gives
\[
\sum_t\lambda_tf_t(D)+\sum_Sy_Sg_S(D)
+\left(1-\sum_t\lambda_t\right)r\geq p_*.
\]
Since $r$ is unrestricted, $\sum_t\lambda_t=1$.
For any nonnegative $\lambda$ with this sum and any $y\geq0$, weak
duality gives the reverse bound: at a feasible $D$, the weighted
objective plus the weighted constraint residuals is at most
$\max_t f_t(D)$. Consequently, writing
\[
A(\lambda)=\sum_t\lambda_tA_t,\qquad
Z(y)=\sum_{S\in\mathcal C}y_S\mathbf1_S\mathbf1_S^{\mathsf T},\qquad
d(y)=\sum_{S\in\mathcal C}y_Sd_S,
\]
we have proved
\begin{equation}
\label{hd:lagrange}
p_*=
\sup_{\substack{\lambda\geq0,\ \sum_t\lambda_t=1\\y\geq0}}
\inf_{D\succ0}
\left\{\operatorname{tr}(A(\lambda)D^{-1})
+\operatorname{tr}(Z(y)D)-d(y)\right\}.
\end{equation}
This argument neither assumes attainment of the primal infimum nor
requires a uniform positive lower bound on the eigenvalues of its
feasible matrices.
\paragraph{The matrix infimum, including singular matrices.}
For any symmetric positive semidefinite $A,Z$, we claim that
\begin{equation}
\label{hd:matrix-inf}
\inf_{D\succ0}
\bigl\{\operatorname{tr}(AD^{-1})+\operatorname{tr}(ZD)\bigr\}
=2\operatorname{tr}\bigl((Z^{1/2}AZ^{1/2})^{1/2}\bigr).
\end{equation}
First suppose $A,Z\succ0$, and set
$H=Z^{1/2}DZ^{1/2}$ and $C=Z^{1/2}AZ^{1/2}$. The difference between
the left-hand objective and $2\operatorname{tr}(C^{1/2})$ equals
\[
\operatorname{tr}(CH^{-1})+\operatorname{tr}(H)
-2\operatorname{tr}(C^{1/2})
=\|H^{-1/2}C^{1/2}-H^{1/2}\|_{\mathrm F}^2\geq0.
\]
It is zero when $H=C^{1/2}$, proving the identity in this case.
For general $A,Z\succeq0$, replace them temporarily by
$A_\varepsilon=A+\varepsilon I$ and
$Z_\varepsilon=Z+\varepsilon I$. The positive definite identity,
applied at any fixed $D$, and then continuity of positive semidefinite
square roots give the lower bound in \eqref{hd:matrix-inf} as
$\varepsilon\downarrow0$. Conversely, the unperturbed objective is
at most the perturbed objective at every $D$, so its infimum is at
most the known perturbed infimum. Letting $\varepsilon\downarrow0$
gives the upper bound. Continuity here also follows directly from the
spectral theorem: along a convergent sequence of positive semidefinite
matrices their square roots are bounded, and every convergent
subsequence of these square roots has the unique positive
semidefinite square root of the limit as its limit. These
perturbations prove an auxiliary matrix identity; they do not change
the allowed dual multipliers.
For fixed $\lambda,y$, abbreviate the trace of the square root in
\eqref{hd:matrix-inf} by $N(\lambda,y)$. If $y\ne0$, then $d(y)>0$.
Scaling $y$ by $s\geq0$ changes the dual value to
$2\sqrt{s}\,N(\lambda,y)-s\,d(y)$, whose supremum over $s\geq0$ is
$N(\lambda,y)^2/d(y)$. The case $y=0$ contributes zero. Thus
\eqref{hd:lagrange} becomes
\begin{equation}
\label{hd:homogeneous}
p_*=
\sup_{\substack{\lambda\geq0,\ \sum_t\lambda_t=1\\y\geq0,\ y\ne0}}
\frac{N(\lambda,y)^2}{d(y)}.
\end{equation}
\paragraph{From weighted cuts to binary coordinates.}
Let $W=W(\lambda)$ be the diagonal $E\times E$ matrix with entries
\begin{equation}
\label{hd:weights}
w_e=\left(\sum_{t\in\mathcal M:\ e\in O(t)}
\frac{\lambda_t}{|O(t)|}\right)^{1/2}.
\end{equation}
Then $A(\lambda)=BW^2B^{\mathsf T}$. If a matrix $Y$ has rows
$\sqrt{y_S}\,\mathbf1_S^{\mathsf T}$, then $Y^{\mathsf T}Y=Z(y)$.
The matrices $Z(y)^{1/2}A(\lambda)Z(y)^{1/2}$ and
$WB^{\mathsf T}Z(y)BW$ have the same nonzero eigenvalues: they are
the two products $TT^{\mathsf T}$ and $T^{\mathsf T}T$ with
$T=Z(y)^{1/2}BW$. It follows that
\[
N(\lambda,y)=\|YBW\|_*,\qquad
d(y)=\sum_{e\in E}\|Yb_e\|_2^2,
\]
where $\|M\|_*$ denotes the sum of the singular values of $M$.
For fixed $\lambda$, the ratio in \eqref{hd:homogeneous} is continuous
in $y\geq0$, $y\ne0$. Approximate $y$ by nonzero nonnegative rational
vectors. For rational $y$, choose a positive integer $q$ with every
$qy_S$ integral and form a binary matrix $X$ by repeating the row
$\mathbf1_S^{\mathsf T}$ exactly $qy_S$ times. Then
$X^{\mathsf T}X=qZ(y)$, and both the squared numerator and the
denominator in the ratio acquire the same factor $q$. Conversely,
any binary $X$ gives integral cut multiplicities after its constant
rows are discarded. Constant rows contribute zero to $XB$, so they
have no effect on the ratio. Adding zero rows permits $h\geq m$.
These observations prove the exact identity
\begin{equation}
\label{hd:binary-nuclear}
p_*=
\sup_{\substack{h\geq m,\ X\in\{0,1\}^{h\times V},\ \mathcal E(X)>0\\
\lambda\geq0,\ \sum_t\lambda_t=1}}
\frac{\|XBW(\lambda)\|_*^2}{\mathcal E(X)}.
\end{equation}
The limiting argument takes a supremum over all finite dimensions;
it asserts no exact finite binary representation for irrational
cut weights.
\paragraph{Orthonormal edge vectors and the factor two.}
For any $h\times m$ matrix $M$ with $h\geq m$, singular-value
decomposition gives
\begin{equation}
\label{hd:polar}
\|M\|_*=\max_{UU^{\mathsf T}=I_m}\operatorname{tr}(UM).
\end{equation}
Indeed, write $M=P\Sigma V^{\mathsf T}$ with
$P^{\mathsf T}P=I_m$, $V$ orthogonal, and $\Sigma$ diagonal
nonnegative; zero singular values can be included by completing the
columns of $P$. For any admissible $U$, each diagonal entry of
$V^{\mathsf T}UP$ is at most one, giving the upper bound
$\operatorname{tr}(UM)\leq\operatorname{tr}(\Sigma)$.
The choice $U=VP^{\mathsf T}$ attains it.
Write $a_e=\langle u_e,Xb_e\rangle$. Individual rows of $U$ can be
multiplied by $-1$ while preserving $UU^{\mathsf T}=I_m$.
Consequently, when taking either the supremum in \eqref{hd:ratio} or
the supremum of the squared trace in \eqref{hd:polar}, we may restrict
to $a_e\geq0$ for all $e$: replacing $a_e$ by $|a_e|$ cannot decrease
either expression. Equation \eqref{hd:binary-nuclear} therefore says
\begin{equation}
\label{hd:weighted-rows}
p_*=
\sup_{X,U,\lambda}
\frac{\left(\sum_e w_ea_e\right)^2}{\mathcal E(X)},
\qquad a_e\geq0,
\end{equation}
with the other conditions on $X,U,\lambda$ as above.
Every edge belongs to at most two parent boundaries $O(t)$: if its
endpoints have lowest common ancestor $s$, only the two children of
$s$ containing its respective endpoints can have that edge in their
parent boundary. Restricting to marked nodes preserves this property.
Hence, on putting
\[
v_e=\sum_{t\in\mathcal M:\ e\in O(t)}
\sqrt{\lambda_t/|O(t)|},
\]
the elementary inequalities between the Euclidean norm and the sum
of at most two nonnegative numbers give
$w_e\leq v_e\leq\sqrt2\,w_e$. Because $a_e\geq0$,
\begin{equation}
\label{hd:overlap}
\left(\sum_e w_ea_e\right)^2
\leq\left(\sum_e v_ea_e\right)^2
\leq2\left(\sum_e w_ea_e\right)^2.
\end{equation}
For fixed $X,U$, let
\[
c_t=\frac1{\sqrt{|O(t)|}}\sum_{e\in O(t)}a_e\geq0.
\]
Then $\sum_e v_ea_e=\sum_t\sqrt{\lambda_t}\,c_t$.
Cauchy--Schwarz, with equality at
$\lambda_t=c_t^2/\sum_s c_s^2$ when the denominator is nonzero,
shows that
\[
\max_{\lambda\geq0,\ \sum_t\lambda_t=1}
\left(\sum_e v_ea_e\right)^2
=\sum_t c_t^2.
\]
The identity is also valid when all $c_t$ vanish. Taking suprema in
\eqref{hd:overlap} and using \eqref{hd:weighted-rows} proves
$p_*\leq Q_*\leq2p_*$. Finally, if $Q_*\leq K$, the defining
property of the finite infimum $p_*$ supplies a feasible $D\succ0$
whose maximum marked average is less than $p_*+\eta\leq K+\eta$.
\end{proof}
\paragraph{Dimension and orientation conventions.}
The ratio does not depend on the chosen edge orientations, since a
reversed $b_e$ can be accompanied by a reversed $u_e$. Our use of
arbitrarily large $h$ also covers the other usual rectangular
semiorthogonal convention. If $h0.
\]
The map $U$ is a contraction. By changing its row signs, we may
assume
\[
a_e=\langle u_e,Xb_e\rangle\ge0
\qquad(e\in E).
\]
This can only increase the numerator to be bounded. Put
$d_e=\|Xb_e\|_2^2=\|Xb_e\|_1$ and, for $t\in\mathcal M$, set
\[
N_t=\frac{1}{|O(t)|}\left(\sum_{e\in O(t)}a_e\right)^2.
\]
Choose
\begin{equation}\label{hp:parameters}
\alpha=q^{-4/5},\qquad \epsilon=\frac1{10},\qquad
\beta=36,\qquad \rho=\frac1{2q^2},\qquad
C_4=3,\qquad C_3=10^4.
\end{equation}
Let $T\subseteq\mathcal M$ consist of the $\alpha$-bad nodes with
positive numerator, in the sense of Definition~\ref{hb:bad}.
Each node outside $T$ either has zero numerator or satisfies
$N_t<\alpha\sum_{e\in O(t)}d_e$. Since each edge lies in at most
two parent boundaries,
\begin{equation}\label{hp:good}
\sum_{t\in\mathcal M\setminus T}N_t\le2\alpha\mathcal E.
\end{equation}
If $T$ is empty, this already bounds the entire numerator. Otherwise
we apply Proposition~\ref{prop:hierarchy-bags} to $T$, with its geometric
ratio $\lambda$ set equal to $\rho$ and its small parameter $s$ given by
\begin{equation}\label{hp:small-parameters}
\begin{aligned}
J&=1+\left\lceil\log_2(256/\alpha^2)\right\rceil,
&C_2&=128J^4,
&s&=\alpha/C_2,\\
L&=2+\lceil\log_2(1/s)\rceil,
&H&=1+\lceil\log_2(24/(\rho s^2))\rceil,
&C_1&=1024\epsilon^{-2}.
\end{aligned}
\end{equation}
These quantities depend on $q$ alone. In particular, for absolute
constants $c_2,c_5$ and all sufficiently large $q$,
\begin{equation}\label{hp:log-growth}
C_2\le c_2(1+\log q)^4,
\qquad L,H\le c_5(1+\log q).
\end{equation}
For example, the first inequality follows immediately from
$\log_2(256/\alpha^2)=8+(8/5)\log_2q$; the other two follow by taking
logarithms of $s=q^{-4/5}/C_2$ and $\rho=1/(2q^2)$.
The smallness condition in Proposition~\ref{prop:hierarchy-bags} holds
eventually because $s^\epsilon\le q^{-2/25}\to0$, whereas
$48\beta C_1$ is an absolute constant. The assignment strength it
provides also satisfies
\begin{equation}\label{hp:assignment-strength}
s^{1+2\epsilon}=\frac{q^{-24/25}}{C_2^{6/5}}
\ge\frac{24C_3}{q}
\end{equation}
for all sufficiently large absolute $q$. Indeed, after multiplication
by $q$, its left side is $q^{1/25}/C_2^{6/5}$, which tends to infinity
by~\eqref{hp:log-growth}.
The proposition therefore yields a $\rho$-geometric sequence, either
of $36$-compact families or of families that are at least
$(24C_3/q)$-assigned. Let its mass be $\mathsf M$. Its guarantee is
\begin{equation}\label{hp:captured-numerator}
\mathsf M\ge
\frac{s^\epsilon}{384\beta C_1C_2LH}\sum_{t\in T}N_t.
\end{equation}
In the assigned case, a stronger assignment implies the required weaker
assignment because the cardinality condition is a lower bound. The
selected nodes are a subset of the original marked nodes, so
\[
|O(t)|\ge\frac1q|P(t)|\ge q\rho|P(t)|.
\]
Thus the hierarchy satisfies the hypothesis of
Proposition~\ref{prop:hierarchy-assigned} with $k=q$ and $\lambda=\rho$.
The constants in~\eqref{hp:parameters} obey its numerical restrictions,
and $\rho\le1/18$ for all sufficiently large $q$. In the compact
case, Proposition~\ref{prop:hierarchy-compact} applies, since
$\rho\le1/12$. Both cases give the uniform lower bound
\begin{equation}\label{hp:charged-energy}
\mathcal E\ge\kappa q\mathsf M,
\qquad \kappa=\frac{C_4}{96C_3}=\frac1{320000}.
\end{equation}
The energy is the same in the dual and charging estimates, since each
coordinate of $Xb_e$ is $0$, $1$, or $-1$.
Combining~\eqref{hp:captured-numerator} and
\eqref{hp:charged-energy} proves
\begin{equation}\label{hp:bad}
\frac{\sum_{t\in T}N_t}{\mathcal E}
\le\frac{384\beta C_1C_2LH}{\kappa q s^\epsilon}
\le c_6 q^{-23/25}(1+\log q)^7
\end{equation}
for an absolute $c_6$. To check the final exponent, substitute
$s^\epsilon=q^{-2/25}C_2^{-1/10}$ and use
\eqref{hp:log-growth}; the logarithmic power before rounding up is
$4(11/10)+2=32/5<7$.
Equations~\eqref{hp:good} and \eqref{hp:bad}, including the case $T$
is empty, yield the uniform bound
\begin{equation}\label{hp:dual-final}
\frac{\sum_{t\in\mathcal M}N_t}{\mathcal E}
\le2q^{-4/5}+c_6q^{-23/25}(1+\log q)^7
=o(q^{-31/40}).
\end{equation}
Every constant in this estimate is absolute, and the embedding and
semiorthogonal matrix were arbitrary. Hence the same upper bound holds
for the supremum $Q_*$ of Lemma~\ref{lem:hierarchy-dual}. Increase
the absolute integer cutoff $q_H$ so that the right side of
\eqref{hp:dual-final} is at most $q^{-31/40}/2$ for $q\ge q_H$, as well
as so that all previous numerical conditions hold.
Applying that lemma with $K=q^{-31/40}/2$ and
$\eta=q^{-31/40}/2$ supplies a feasible full positive definite $D$
whose every marked average is less than $q^{-31/40}$.
This proves the theorem. In particular, selecting a feasible matrix
from the infimum uses only strict slack; no assertion of attainment is
needed.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_proof.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/introduction.tex ====
\section{Introduction}\label{sec:introduction}
For a finite loopless undirected multigraph \(G=(V,E)\) and a nonempty proper
subset \(S\subset V\), write \(\delta_G(S)\) for the edges with exactly
one endpoint in \(S\). Parallel edges are counted separately.
A graph is \(k\)-edge-connected if \(|\delta_G(S)|\ge k\) for
every nonempty proper \(S\).
A spanning tree \(T\) is \(\alpha\)-thin if
\[
|\delta_T(S)|\le\alpha|\delta_G(S)|
\qquad(\varnothing\ne S\subsetneq V).
\]
A spanning tree retains connectivity using only \(|V|-1\) edges.
Thinness asks that these edges occupy a small fraction of every cut
simultaneously. The question is whether high edge connectivity alone
forces such a tree, with a bound independent of the number of vertices.
\begin{theorem}\label{thm:main}
There is a universal constant \(C>0\) such that, for every integer
\(k\ge1\), every finite \(k\)-edge-connected undirected multigraph
without loops and with at least two vertices has a spanning tree \(T\)
satisfying
\[
|\delta_T(S)|\le\frac Ck\,|\delta_G(S)|
\qquad\text{for every }\varnothing\ne S\subsetneq V.
\]
\end{theorem}
\subsection*{The conjecture and its history}
Goddyn's thin tree conjecture asks whether, for every
\(\varepsilon>0\), a sufficiently high edge connectivity guarantees
an \(\varepsilon\)-thin spanning tree~\cite{Goddyn}.
The strong thin tree conjecture asks for the quantitative rate \(C/k\).
Theorem~\ref{thm:main} resolves this stronger conjecture positively.
The order \(1/k\) is necessary: with two vertices and \(k\) parallel
edges, every spanning tree uses exactly one of the \(k\) edges of
the only cut.
Thin trees connect this graph-theoretic question with approximation
algorithms. In the asymmetric traveling salesman problem, one seeks a
minimum-cost tour through all vertices of a directed metric.
Asadpour, Goemans, M\k{a}dry, Oveis Gharan, and Saberi used
maximum-entropy distributions on spanning trees to round the standard
linear-programming relaxation, obtaining an
\(O(\log n/\log\log n)\)-approximation, where \(n\) is the number
of vertices~\cite{AsadpourSODA,Asadpour}.
Their method explains the usefulness of controlling every cut:
together with control of the tree's cost, cut bounds permit an inexpensive
Eulerian augmentation of a suitable oriented tree.
For the underlying thin-tree problem, Oveis Gharan and
Saberi established the inverse-connectivity bound for planar graphs
and, with constants depending on the surface, for graphs of bounded
orientable genus~\cite[Theorem~5.1]{OveisGharanSaberi2011}.
For general multigraphs, Anari and Oveis Gharan developed
effective-resistance-reducing flows and the geometry of locally
connected hierarchies. They proved the existence of a spanning tree
with thinness \(\operatorname{poly}(\log\log n)/k\)
\cite[Corollary~1.8]{AOG}.
Their work provides the principal geometric foundation of the present
proof. Progress for specified families of cuts gives a complementary
view of the problem. Klein and Olver obtained inverse-connectivity
thinness for every prescribed laminar family~\cite{KleinOlver2023}.
Klein, Olver, and Yeoh constructed a spanning tree crossing every cut
of size less than \((1+1/40)k\) at most \(88\) times
\cite[Theorem~1]{KleinOlverYeoh}.
Theorem~\ref{thm:main} controls all cuts simultaneously and removes
the dependence on \(n\).
The thin-tree approach to asymmetric traveling salesman remains
structurally useful, although constant-factor approximation for that
problem has already been obtained by other methods. Svensson,
Tarnawski, and V\'egh proved the first such guarantee
\cite{SvenssonTarnawskiVegh2020}; Traub and Vygen subsequently
improved it~\cite{TraubVygen2022}. Our objective here is the
underlying all-cut spanning-tree theorem.
\subsection*{The two main deductions}
High edge connectivity supplies many edge-disjoint spanning trees
through the Nash--Williams--Tutte theorem~\cite{NashWilliams,Tutte}.
For any fixed cut, the average number of edges used by the trees in
such a packing is small. This averaging does not select one tree
that is small on every cut. We maintain a large packing throughout
a sequence of sparsifications: each step reduces cut sizes and the
packing size by almost the same factor, and the accumulated relative
loss remains bounded.
The first deduction extracts a large tree packing on edges of small
resistance. For a graph \(H\), let \(b_e=\mathbf1_u-\mathbf1_v\)
be an arbitrarily oriented incidence column of an edge \(e=uv\),
and let \(L_H=\sum_e b_eb_e^{\mathsf T}\) be its Laplacian.
The resistance of \(e\) with respect to a positive definite matrix
\(X\) is \(b_e^{\mathsf T}X^{-1}b_e\).
Write \(\mathbf1_S\) for the indicator column of \(S\), and
\(A\preceq B\) when \(B-A\) is positive semidefinite.
For all sufficiently large integers \(r\), if \(H\) on at least
two vertices contains \(r\) edge-disjoint spanning trees, we
construct such a matrix \(X\) with
\[
L_H\preceq X,\qquad
\mathbf1_S^{\mathsf T}X\mathbf1_S
\le3|\delta_H(S)|
\quad(\varnothing\ne S\subsetneq V),
\]
such that the edges of \(H\) with
\(b_e^{\mathsf T}X^{-1}b_e\le4r^{-1/2}\) still contain
\(\lfloor(1-r^{-1/16})r\rfloor\) edge-disjoint spanning trees.
The starting point is a polynomial consequence of the locally connected
hierarchy theorem of Anari and Oveis Gharan~\cite[Theorem~3.5]{AOG};
we prove the required consequence in full.
For a given matrix, retain the edges below each resistance threshold
and partition the vertices into maximal sets supporting the prescribed
number of disjoint spanning trees. These partitions are nested.
Selecting them by dyadic crossing-edge counts gives a rooted hierarchy
of nested vertex sets and avoids a loss depending on the number of
levels. The hierarchy estimate supplies a response matrix \(Y\) with
small resistance on almost all crossing edges of every selected
partition at once (Lemma~\ref{lem:response}). We interpolate finitely
many such responses and take a fixed-point limit. At the resulting
matrix \(X\), a nontrivial maximal packing partition of its own
low-resistance graph would have too many crossing edges. This
contradiction yields the extracted packing
(Theorem~\ref{thm:extraction}).
The second deduction is a sparsification step that retains about half
the tree packing while bounding each new cut by approximately half its
previous size. We use two vector representations of the incidence
columns. The matrix \(X\) controls cut size. A separate isotropic
representation---whose vector outer products sum to the identity---
controls the partition inequalities for tree packing.
Applying the Marcus--Spielman--Srivastava theorem~\cite{MSS} to the stacked
columns controls both systems on the same selected edge set.
The relative losses are \(1+O(r^{-1/16})\). They have a bounded product
as the packing parameter decreases geometrically.
Harvey and Olver used iterated matrix halving to obtain spectrally thin
trees under an effective-resistance hypothesis
\cite[Appendix~F]{HarveyOlver2014}. The additional packing
representation here permits iteration from edge connectivity.
Preserving a packing requires more than a weighted spectral
approximation. Sampling by effective resistance and spectral
sparsification provide powerful ways to reduce a graph while
approximately preserving its Laplacian
\cite{SpielmanSrivastava2011,BatsonSpielmanSrivastava2012}.
Here the edges must retain their original unit multiplicities.
For example, \(q\) parallel edges between two vertices have the same
Laplacian as one edge of weight \(q\), but the former graph packs
\(q\) edge-disjoint spanning trees and the latter has only one.
The second representation supplies the rank information needed to
certify the partition inequalities after selecting an unweighted
subset of edges.
\subsection*{Organization and inputs}
Section~\ref{sec:preliminaries} proves the tree-packing facts used below.
Section~\ref{sec:hierarchy} gives the precise hierarchy input, and
Section~\ref{sec:extraction} proves the extraction theorem.
Sections~\ref{sec:auxiliary} and~\ref{sec:sparsification} develop the
auxiliary representation and the sparsification step.
Section~\ref{sec:iteration} proves Theorem~\ref{thm:main}, including
the small-connectivity cases.
The independent-vector theorem used in the sparsification appears
as Theorem~\ref{thm:mss}. The required hierarchy estimate and the
finite-dimensional fixed-point theorem are proved in the appendices.
All sufficiently large thresholds in the argument are absolute.
Choices made after a particular finite graph has been fixed need
not have a uniform algorithmic running time.
The companion article \emph{A polynomial-time construction of strong
thin trees}~\cite{ConstructiveThinTreesCompanion} develops the
separate finite-bit construction, including graphs given by
binary-encoded parallel-edge multiplicities. Its geometric input
extends the hierarchy proof here from cut tests to a larger cone of
metric tests.
==== END The-strong-thin-tree-conjecture//source/sections/introduction.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/iteration.tex ====
\section{Iteration and the thin spanning tree}\label{sec:iteration}
We now turn the sparsification step into a uniform bound.
The estimate keeps track of the tree-packing parameter rather than
the number of rounds.
The bounded product of losses uses the summable-error principle in
the spectral-halving argument of Harvey and Olver
\cite[Appendix~F, Claims~F.3--F.4]{HarveyOlver2014}.
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Choose an absolute integer \(r_*\) at least the cutoff in
Proposition~\ref{prop:step}. For every \(r\ge r_*\), that proposition
supplies a positive integer \(r'\) satisfying
\[
\frac5{16}\le\frac{r'}r\le\frac12,
\qquad
\frac{1/2+3\tau}{r'/r}\le1+15r^{-1/16}.
\]
These are exactly the estimates in \eqref{eq:step-ratio-bound}.
First let \(H_0\) be any graph on at least two vertices with
\(r_0\ge1\) packed spanning trees. As long as \(r_i\ge r_*\), apply
Proposition~\ref{prop:step} to obtain a subgraph \(H_{i+1}\)
with at least
\[
r_{i+1}=
\left\lfloor\frac{(1-4r_i^{-1/16})r_i}{2}\right\rfloor
\]
packed spanning trees. Stop at the first \(j\) with \(r_j0$, and let $v_1,\ldots,v_m$ be independent random vectors
with finite support in $\mathbb C^d$. If
\begin{equation}
\sum_{i=1}^m\mathbb E[v_iv_i^*]=I_d,
\qquad \mathbb E\|v_i\|^2\leq\epsilon\quad(1\leq i\leq m),
\label{eq:mss-hypotheses}
\end{equation}
then
\begin{equation}
\mathbb P\left\{
\left\|\sum_{i=1}^m v_iv_i^*\right\|
\leq(1+\sqrt\epsilon)^2\right\}>0.
\label{eq:mss-conclusion}
\end{equation}
Here $*$ denotes conjugate transpose and the norm is the operator norm.
In particular, some outcome satisfies the corresponding
positive-semidefinite upper bound. Real vectors are a special case.
\end{theorem}
The case $d=0$ is immediate, so the proof below assumes $d\geq1$.
We will use polynomial factorization, elementary compactness, and
standard finite-dimensional linear algebra. The polynomial and
analytic lemmas needed beyond those facts are proved below.
\subsection{Polynomial limits and stability}
Write $\mathbb H=\{z\in\mathbb C:\operatorname{Im}z>0\}$.
A nonzero polynomial $p$ in several variables is \emph{stable} if it
does not vanish when all its arguments lie in $\mathbb H$. It is
\emph{real stable} if, in addition, its coefficients are real.
A nonzero real univariate polynomial is stable exactly when all its
roots are real: nonreal roots of a real polynomial occur in conjugate
pairs.
\begin{lemma}[Limits of univariate polynomials]
\label{lem:mss-polynomial-limits}
Suppose nonzero univariate polynomials $f_\nu$ have uniformly bounded
degrees and converge coefficientwise to a nonzero polynomial $f$.
If all $f_\nu$ have no zeros in $\mathbb H$, neither does $f$.
If all $f_\nu$ are real-rooted, so is $f$.
For monic real-rooted polynomials of a fixed degree, their ordered
roots depend continuously on their coefficients.
\end{lemma}
\begin{proof}
For the first assertion choose $a\in\mathbb H$ with $f(a)\ne0$.
Pass to a subsequence on which the degree is constant, and enumerate
its roots $\lambda_{\nu,1},\ldots,\lambda_{\nu,e}$ with multiplicity.
By compactness of the complex plane together with the point at
infinity, a further subsequence makes every root converge, allowing
infinite limits. Every finite limit lies outside $\mathbb H$.
In the factorization
\[
\frac{f_\nu(z)}{f_\nu(a)}
=\prod_{k=1}^e\frac{z-\lambda_{\nu,k}}{a-\lambda_{\nu,k}},
\]
a root tending to infinity contributes a factor tending to $1$, and
a root tending to a finite $\lambda_k$ contributes
$(z-\lambda_k)/(a-\lambda_k)$. The limiting identity factors
$f(z)/f(a)$ with all its roots outside $\mathbb H$.
For real-rooted $f_\nu$, the same proof uses the extended real line;
all finite limiting roots are then real.
For the last assertion, a bounded set of monic coefficient vectors
has bounded roots. Indeed a root of
$z^d+\sum_{k0$. The resulting univariate polynomials
have no zeros in $\mathbb H$ and converge coefficientwise to the
stated nonzero real polynomial. Apply
Lemma~\ref{lem:mss-polynomial-limits}.
\end{proof}
\subsection{Expected characteristic polynomials}
For positive-semidefinite Hermitian $d$-by-$d$ matrices
$A_1,\ldots,A_m$, define
\begin{equation}
\mu[A_1,\ldots,A_m](x)
=\left.
\left(\prod_{i=1}^m(1-\partial_{z_i})\right)
\det\left(xI_d+\sum_{i=1}^m z_iA_i\right)
\right|_{z_1=\cdots=z_m=0}.
\label{eq:mss-mixed-polynomial}
\end{equation}
\begin{lemma}[The expectation identity and real roots]
\label{lem:mss-expectation}
The polynomial in \eqref{eq:mss-mixed-polynomial} is monic of degree
$d$ and real-rooted. If $v_1,\ldots,v_m$ are independent finitely
supported random vectors and $A_i=\mathbb E[v_iv_i^*]$, then
\begin{equation}
\mathbb E\det\left(xI_d-\sum_{i=1}^m v_iv_i^*\right)
=\mu[A_1,\ldots,A_m](x).
\label{eq:mss-expectation-identity}
\end{equation}
\end{lemma}
\begin{proof}
The determinant in \eqref{eq:mss-mixed-polynomial} is stable by
Lemma~\ref{lem:mss-stability}; applying all the operators preserves
stability. Specializing all $z_i$ to zero leaves a nonzero real-rooted
polynomial. To see directly both that it is nonzero and that it is
monic of degree $d$, the coefficient of $x^d$ in the determinant is
$1$, independent of the $z_i$, and every term involving at least one
$z_i$ has smaller $x$-degree. The operations leave that leading
coefficient unchanged. The specialization can be performed all at
once by substituting $z_i=\mathrm i\eta$ and using
Lemma~\ref{lem:mss-polynomial-limits}.
For the identity, let $M$ be any square matrix, let $v$ be a random
vector, and put $A=\mathbb E[vv^*]$. The rank-one determinant identity
and the derivative formula for the determinant give
\begin{align*}
\mathbb E\det(M-vv^*)
&=\det M-\operatorname{tr}(\operatorname{adj}(M)A)\\
&=\left.(1-\partial_z)\det(M+zA)\right|_{z=0}.
\end{align*}
Here $\operatorname{adj}(M)$ is the adjugate. These identities hold
also for singular $M$: they are polynomial identities in its entries,
or follow directly by multilinearity of the determinant in its
columns. Apply this formula conditionally to $v_m$, then $v_{m-1}$,
and so forth. Independence keeps each covariance $A_i$ unchanged
under conditioning. Finite sums, differentiation, and the
specializations commute, giving
\eqref{eq:mss-expectation-identity}.
\end{proof}
\subsection{Interlacing and the choice of an outcome}
For a monic real-rooted degree-$d$ polynomial $f$, write its roots as
$\lambda_1(f)\leq\cdots\leq\lambda_d(f)$, counting multiplicity.
A finite collection of such polynomials has a \emph{common
interlacing} if there are real numbers
$c_1\leq\cdots\leq c_{d-1}$ such that
\[
\lambda_k(f)\leq c_k\leq\lambda_{k+1}(f)
\quad(1\leq k0$, obtaining
two nonreal roots. For $\ell\geq3$, the equation
$z^\ell=-\sigma b/a\ne0$ has nonreal roots for either sign.
This contradiction proves the claim.
Thus $N$ can change by at most one, at that single simple crossing.
It follows that $|N(0)-N(1)|\leq1$.
If $\lambda_k(p)>\lambda_{k+1}(q)$ for some $k\rho$, $P(x)>0$, so at least one $p_i(x)>0$.
Its first $d-1$ roots are below $x$; positivity therefore implies
$\lambda_d(p_i)0
\text{ for every }s\in[0,\infty)^m\}.
\]
Such a point is said to be \emph{above the roots}. At a point of
this set define
\[
\Phi_p^i(z)=\frac{\partial_i p(z)}{p(z)}.
\]
The set $\operatorname{Ab}_p$ is closed under adding a vector with
nonnegative coordinates. The derivatives below are well defined
locally because $p$ is positive at all the points under discussion.
\begin{lemma}[Positive partial fractions]
\label{lem:mss-partial-fractions}
Let $p$ be real stable, $z\in\operatorname{Ab}_p$, and let $i,j$ be
coordinate indices. As a rational function of $t$,
\begin{equation}
\Phi_p^i(z+te_j)
=c+\sum_{\ell=1}^s\frac{c_\ell}{t-\lambda_\ell},
\qquad c\geq0,\quad c_\ell>0,\quad\lambda_\ell<0,
\label{eq:mss-positive-partial-fractions}
\end{equation}
where the sum may be empty. In particular, for $t\geq0$ this
function is nonnegative, nonincreasing, and convex.
\end{lemma}
\begin{proof}
Set $h(t)=p(z+te_j)$ and $a(t)=\partial_i p(z+te_j)$.
The polynomial $h$ is real-rooted by
Lemma~\ref{lem:mss-stability}, and is nonzero since $h(0)>0$.
It is positive on $[0,\infty)$, so every root is strictly negative.
Thus the real rational function $R=a/h$ has only negative real
poles, after cancelling common factors.
We next show that $\operatorname{Im}R(t)\leq0$ for $t\in\mathbb H$.
In \eqref{eq:mss-log-derivative-upper}, use the point with argument
$z_j+t$ in coordinate $j$ and argument $z_k+\mathrm i\eta$ in every
other coordinate. All coordinates have positive imaginary parts,
and the logarithmic derivative in direction $i$ has nonpositive
imaginary part. Let $\eta\downarrow0$.
Since $h(t)\ne0$ for $t\in\mathbb H$, the quotient converges to
$R(t)$ and proves the desired inequality.
Also $R(t)\geq0$ for real $t\geq0$. Indeed
$g(s)=p(z+te_j+se_i)$ is a nonzero real-rooted polynomial, positive
for $s\geq0$. Factoring it with its negative real roots $\beta_k$
gives
\[
R(t)=\frac{g'(0)}{g(0)}=\sum_k\frac1{-\beta_k}\geq0;
\]
the empty sum covers a constant $g$.
It remains to classify this rational function, which can be done
directly. At a pole $\lambda$ of order $b\geq1$, let its highest
principal part be $a_0(t-\lambda)^{-b}$, with $a_0\ne0$ real.
At $t=\lambda+r\exp(\mathrm i\theta)$, as $r\downarrow0$, the
leading imaginary part is
$-a_0r^{-b}\sin(b\theta)$.
For $b\geq2$ this has both signs for $0<\theta<\pi$, contradicting
$\operatorname{Im}R\leq0$. Hence every pole is simple, and the same
inequality for $b=1$ forces its residue to be positive.
Subtract these simple principal parts. The remainder is a real
polynomial. If its degree were at least two, its leading term along
large rays $t=r\exp(\mathrm i\theta)$ would again have imaginary
parts of both signs; the subtracted fractions are $O(1/r)$ and
cannot affect this conclusion. Thus the remainder has degree at
most one, and a linear remainder must have nonpositive slope.
The inequality $R(t)\geq0$ for all real $t\geq0$ rules out a
negative slope and forces its constant term to be nonnegative.
This proves \eqref{eq:mss-positive-partial-fractions}.
Finally, direct differentiation on $t\geq0$ gives
\[
R'(t)=-\sum_\ell\frac{c_\ell}{(t-\lambda_\ell)^2}\leq0,
\qquad
R''(t)=2\sum_\ell\frac{c_\ell}{(t-\lambda_\ell)^3}\geq0.
\]
Together with $R(t)\geq0$, these are the asserted properties.
\end{proof}
\begin{lemma}[One barrier shift]
\label{lem:mss-barrier-shift}
Let $p$ be real stable, let $z\in\operatorname{Ab}_p$, and suppose
$\delta>0$ satisfies
\begin{equation}
\Phi_p^j(z)+\frac1\delta\leq1.
\label{eq:mss-shift-hypothesis}
\end{equation}
For $q=(1-\partial_j)p$ and $w=z+\delta e_j$, one has
$w\in\operatorname{Ab}_q$ and
\begin{equation}
\Phi_q^i(w)\leq\Phi_p^i(z)\qquad\text{for every }i.
\label{eq:mss-shift-conclusion}
\end{equation}
\end{lemma}
\begin{proof}
The polynomial $q$ is real stable by
Lemma~\ref{lem:mss-stability}. Applying the monotonicity in
Lemma~\ref{lem:mss-partial-fractions} successively in each coordinate,
for every vector $s\geq0$ we have
\[
\Phi_p^j(z+s)\leq\Phi_p^j(z)\leq1-1/\delta<1.
\]
It follows that
$q(z+s)=p(z+s)(1-\Phi_p^j(z+s))>0$.
Thus $z$, and therefore also $w$, belongs to $\operatorname{Ab}_q$.
Fix $i$ and put $f(t)=\Phi_p^i(z+te_j)$.
Commuting the mixed derivatives of $\log p$ in a neighborhood of
$w$ gives
\[
\Phi_q^i(w)
=f(\delta)-\frac{f'(\delta)}{1-\Phi_p^j(w)}.
\]
By monotonicity, the denominator is at least $1/\delta$, and
$f'(\delta)\leq0$. By convexity,
$f(0)\geq f(\delta)-\delta f'(\delta)$; this also follows by
integrating the nondecreasing derivative on $[0,\delta]$.
Therefore
\[
\Phi_q^i(w)
\leq f(\delta)-\delta f'(\delta)
\leq f(0)=\Phi_p^i(z),
\]
as required.
\end{proof}
\subsection{The largest-root bound and conclusion}
\begin{lemma}[Largest root of the mixed polynomial]
\label{lem:mss-root-bound}
If $A_i\succeq0$, $\sum_iA_i=I_d$, and
$\operatorname{tr}A_i\leq\epsilon$ for every $i$, where $\epsilon>0$,
then the largest root of $\mu[A_1,\ldots,A_m]$ is at most
$(1+\sqrt\epsilon)^2$.
\end{lemma}
\begin{proof}
Let
\[
p_0(y)=\det\left(\sum_{i=1}^m y_iA_i\right),
\qquad
p_j=(1-\partial_{y_j})p_{j-1}\quad(1\leq j\leq m).
\]
The first polynomial is real stable by
Lemma~\ref{lem:mss-stability}, since $\sum_iA_i=I_d$.
Moreover,
\begin{equation}
\mu[A_1,\ldots,A_m](x)=p_m(x,\ldots,x).
\label{eq:mss-diagonal-identity}
\end{equation}
To check this identity, substitute $y_i=x+z_i$ before applying the
operators. Then $\sum_i y_iA_i=xI_d+\sum_i z_iA_i$,
$\partial_{y_i}$ acts as $\partial_{z_i}$, and setting every $z_i=0$
is exactly \eqref{eq:mss-mixed-polynomial}.
Set
\[
t=\epsilon+\sqrt\epsilon,
\qquad \delta=1+\sqrt\epsilon,
\qquad \varphi=\frac\epsilon t=1-\frac1\delta.
\]
At $z^{(0)}=t\mathbf1$, the matrix in $p_0$ is $tI_d$.
Adding nonnegative coordinates adds a positive-semidefinite matrix,
so $z^{(0)}\in\operatorname{Ab}_{p_0}$.
Differentiating the determinant gives, for every $i$,
\[
\Phi_{p_0}^i(z^{(0)})
=\operatorname{tr}((tI_d)^{-1}A_i)
\leq\frac\epsilon t=\varphi.
\]
Inductively define
$z^{(j)}=t\mathbf1+\delta(e_1+\cdots+e_j)$.
Suppose $z^{(j-1)}\in\operatorname{Ab}_{p_{j-1}}$ and all its
barriers are at most $\varphi$.
Because $\varphi+1/\delta=1$, Lemma~\ref{lem:mss-barrier-shift}
applies in direction $j$ and yields
$z^{(j)}\in\operatorname{Ab}_{p_j}$, with all its barriers still
at most $\varphi$. This proves the induction for every $j$.
At the end, $z^{(m)}=(t+\delta)\mathbf1$ is above the roots of
$p_m$. By \eqref{eq:mss-diagonal-identity}, the mixed polynomial
is positive for every real $x\geq t+\delta$.
It is real-rooted by Lemma~\ref{lem:mss-expectation}; hence its
largest root is at most
\[
t+\delta=\epsilon+2\sqrt\epsilon+1
=(1+\sqrt\epsilon)^2.
\]
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:mss}]
Put $A_i=\mathbb E[v_iv_i^*]$. These matrices are Hermitian
positive semidefinite, and \eqref{eq:mss-hypotheses} says that
$\sum_iA_i=I_d$ and
$\operatorname{tr}A_i=\mathbb E\|v_i\|^2\leq\epsilon$.
Lemma~\ref{lem:mss-root-bound} bounds the largest root of their
mixed polynomial by $(1+\sqrt\epsilon)^2$.
Lemma~\ref{lem:mss-selection} then supplies an outcome of positive
probability whose largest eigenvalue obeys the same bound.
The matrix $\sum_i v_iv_i^*$ is positive semidefinite, so this
largest eigenvalue is its operator norm. This proves
\eqref{eq:mss-conclusion}.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/mss.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/preliminaries.tex ====
\section{Laplacians and tree packings}\label{sec:preliminaries}
Unless a base is specified, $\log$ denotes the natural logarithm.
All graphs in the proof are finite undirected loopless multigraphs.
They have a common vertex set when one is said to be a subgraph of
another. Each parallel edge has its own index.
For a partition \(\mathcal P\) of the vertex set, let
\(E_H(\mathcal P)\) denote the edges whose endpoints lie in different
parts. A graph is \(r\)-tree-packable if it contains \(r\) pairwise
edge-disjoint spanning trees. On a singleton vertex set this property
is taken to hold for every positive integer \(r\).
\subsection{Matrix conventions}
Choose an orientation of each edge solely to define
\(b_e=\mathbf1_u-\mathbf1_v\in\R^V\), and put
\[
L_H=\sum_{e\in E(H)}b_eb_e^{\mathsf T}.
\]
Changing an orientation changes no matrix or resistance used below.
For a real symmetric positive definite matrix \(X\), define
\[
R_X(e)=b_e^{\mathsf T}X^{-1}b_e.
\]
The order \(A\preceq B\) means that \(B-A\) is positive semidefinite.
We use the operator norm for matrices unless otherwise specified.
For every nonempty proper \(S\subset V\),
\[
\mathbf1_S^{\mathsf T}L_H\mathbf1_S=|\delta_H(S)|.
\]
An inequality required only for these indicator vectors is called a
\emph{cut inequality}. It need not be a semidefinite inequality.
In particular, no cut inequality is imposed at \(S=V\).
\begin{lemma}\label{lem:resistance-order}
For \(X\succ0\), a column \(b\), and \(t>0\),
\[
b^{\mathsf T}X^{-1}b\le t
\quad\Longleftrightarrow\quad
bb^{\mathsf T}\preceq tX.
\]
If \(X\succeq Y\succ0\), then
\(b^{\mathsf T}X^{-1}b\le b^{\mathsf T}Y^{-1}b\).
\end{lemma}
\begin{proof}
Congruence by \(X^{-1/2}\) reduces the first assertion to the fact
that the only possible nonzero eigenvalue of \(aa^{\mathsf T}\) is
\(\|a\|^2\), with \(a=X^{-1/2}b\).
For the second, \(Y^{-1/2}XY^{-1/2}\succeq I\); diagonalization and
inversion give \(X^{-1}\preceq Y^{-1}\).
\end{proof}
When a Laplacian is inverted, we will explicitly restrict it to
\[
\mathbf1^\perp=\{x\in\R^V:\textstyle\sum_{v\in V}x_v=0\}.
\]
The shortcut matrices \(X\) used in extraction are positive definite
on the full space \(\R^V\), so their inverses require no such convention.
\begin{lemma}[Incidence rank]\label{lem:incidence-rank}
If \(F\) has \(n\) vertices and \(c\) connected components, its
incidence columns span a space of dimension \(n-c\).
In particular the columns of a spanning tree form a basis of
\(\mathbf1^\perp\).
\end{lemma}
\begin{proof}
A vector is orthogonal to every incidence column precisely when
its coordinates agree at the endpoints of each edge, equivalently
when it is constant on every connected component.
The orthogonal complement thus has dimension \(c\).
A tree on \(n\) vertices has \(n-1\) edges, as follows by deleting
leaves successively, so its spanning columns form a basis.
\end{proof}
\subsection{The partition criterion}
\begin{theorem}[Nash--Williams--Tutte]\label{thm:packing}
For a positive integer \(r\), a graph \(H\) contains \(r\)
edge-disjoint spanning trees if and only if
\[
|E_H(\mathcal P)|\ge r(|\mathcal P|-1)
\qquad\text{for every partition }\mathcal P\text{ of }V(H).
\]
\end{theorem}
We include an exchange proof of this classical
criterion~\cite{NashWilliams,Tutte}.
The insertion and cycle exchanges below are the graphic form of
the circuit exchanges in Edmonds's matroid-partition
proof~\cite[Section~1.6]{Edmonds1965}.
\begin{proof}
The necessity follows by counting the crossings of each tree.
For sufficiency, choose \(r\) disjoint forests whose total number
\(m\) of edges is maximum. A \emph{state} is such a choice.
Starting from this state, allow a move that adds an unused edge to
one forest and removes an edge of the resulting cycle.
In every reachable state, every unused edge closes a cycle with
each forest: otherwise adding it would increase \(m\).
Let \(U\) be the set of edges that are unused in at least one reachable
state. If an unused edge is added to a forest, every edge of the
resulting cycle lies in \(U\), since any one of its original edges
can be made unused by the corresponding move.
Such a move preserves the components of that forest restricted to
its edges in \(U\). It also leaves the other forests unchanged.
Fix \(e\in U\). In a state where \(e\) is unused, its endpoints are
connected by edges in \(U\) in each forest. The component invariance
just proved carries this statement to the initial state.
Consequently each component of \((V(H),U)\) is spanned by the
\(U\)-edges of every forest.
If there are \(d\) such components, this accounts for \(r(n-d)\)
used edges, where \(n=|V(H)|\).
Every edge between these components is used, since every unused
edge belongs to \(U\). Their number is therefore at most
\[
m-r(n-d).
\]
If \(m1\), then
\[
|E_F(\mathcal P(F))|1\), the quotient would have a set
\(W\) of at least two vertices with
\(|E(W)|\ge q(|W|-1)\).
Choose such \(W\) inclusion-minimal. For each proper nonempty
\(J\subset W\),
\[
|E(J)|\le q(|J|-1);
\]
this also holds for a singleton because loops were removed.
For a partition \(W=J_1\sqcup\cdots\sqcup J_t\), with \(t\ge2\),
subtraction gives at least
\[
q(|W|-1)-\sum_{\ell=1}^t q(|J_\ell|-1)=q(t-1)
\]
edges between its parts. Theorem~\ref{thm:packing} supplies \(q\)
quotient trees on \(W\).
Attach to each color a packed tree inside each of its quotient
vertices. This gives \(q\) disjoint spanning trees on their union
in \(F\), contradicting maximality of the parts.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/preliminaries.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/sparsification.tex ====
\section{A vector representation that certifies tree packings}
\label{sec:auxiliary}
The next representation gives a matrix inequality sufficient for all the
partition inequalities in Theorem~\ref{thm:packing}. Its construction uses
strictly positive edge weights, which preserve every subset rank.
The normalization uses the log-determinant variational method behind
radial isotropic position~\cite[Section~2.2]{Barthe1998}. Here the target
vector of edge weights is the average of the edge-set indicator vectors
of the given disjoint trees. We give the approximate positive-weight form
that keeps every subset rank unchanged.
\begin{lemma}[Isotropic representation preserving ranks]
\label{lem:auxiliary-representation}
Let $B$ be the union of $q\geq1$ edge-disjoint spanning trees on an
$n$-vertex set, where $n\geq2$. For every $\rho>0$ there are vectors
$z_e\in\mathbb R^{n-1}$, indexed by the individual edges of $B$, such that
\begin{equation}
\sum_{e\in B}z_ez_e^{\mathsf T}=I_{n-1},
\qquad \|z_e\|^2\leq\frac{1+\rho}{q}.
\label{eq:auxiliary-isotropy}
\end{equation}
Moreover, there are an invertible linear map $M:\mathbf1^\perp\to
\mathbb R^{n-1}$ and positive numbers $s_e$ such that $z_e=s_eMb_e$.
Consequently the incidence vectors and the $z_e$ have the same rank on
every subset of edges.
\end{lemma}
\begin{proof}
Choose orthonormal coordinates on $\mathbf1^\perp$ and write $b_e$ for
the incidence columns in these coordinates. Denote the given trees by
$T_1,\ldots,T_q$. For $a\in\mathbb R^{E(B)}$, set
\[
N(a)=\sum_{e\in B}\exp(a_e)b_eb_e^{\mathsf T},
\qquad
h(a)=\log\det N(a)-\frac1q\sum_{e\in B}a_e.
\]
Every $N(a)$ is positive definite: the columns of $T_1$ are a basis and
all its weights are positive. Thus $h$ is a smooth, everywhere finite
function.
Let $c_t>0$ be the square of the determinant of the basis of columns
indexed by $T_t$. Cauchy--Binet, followed by the arithmetic--geometric
mean inequality, gives
\begin{align*}
\det N(a)
&\geq\sum_{t=1}^q c_t\exp\left(\sum_{e\in T_t}a_e\right)\\
&\geq q\left(\prod_{t=1}^q c_t\right)^{1/q}
\exp\left(\frac1q\sum_{e\in B}a_e\right).
\end{align*}
Here the last exponent uses the fact that the $T_t$ partition $E(B)$.
In particular,
\[
h(a)\geq L:=\log q+\frac1q\sum_{t=1}^q\log c_t.
\]
For $\gamma>0$, the function $h(a)+\gamma\|a\|^2$ is continuous and
coercive, hence has a minimizer $a^\gamma\in\mathbb R^{E(B)}$.
Comparison with $a=0$ shows that, with $K=h(0)-L\geq0$,
\[
\gamma\|a^\gamma\|^2\leq K,
\qquad
\|\nabla h(a^\gamma)\|
=2\gamma\|a^\gamma\|\leq2\sqrt{\gamma K}.
\]
The stationarity equation supplies the equality in the second formula.
Thus one may choose a finite $a=a^\gamma$ for which every coordinate of
$\nabla h(a)$ has absolute value at most $\rho/q$. This remains valid
when $K=0$, since the displayed gradient bound is then zero.
The determinant derivative formula yields
\[
\frac{\partial h}{\partial a_e}
=\exp(a_e)b_e^{\mathsf T}N(a)^{-1}b_e-\frac1q.
\]
Define $z_e=\exp(a_e/2)N(a)^{-1/2}b_e$. Their outer products sum
exactly to the identity, and the gradient bound gives their asserted
norm bound. The common map $N(a)^{-1/2}$ is invertible and every
$\exp(a_e/2)$ is positive. These operations preserve all subset ranks,
including the dependencies among parallel edges.
\end{proof}
\begin{lemma}[Projected trace and packing]
\label{lem:projected-trace-packing}
With the vectors in Lemma~\ref{lem:auxiliary-representation}, suppose
$A\subseteq E(B)$ and $c>0$ satisfy
\[
\sum_{e\in A}z_ez_e^{\mathsf T}\succeq cI_{n-1}.
\]
Then $(V,A)$ contains at least
$\lfloor cq/(1+\rho)\rfloor$ edge-disjoint spanning trees.
\end{lemma}
\begin{proof}
Fix a partition $\mathcal P=\{V_1,\ldots,V_d\}$ into nonempty parts.
Let $W$ be the span of the $z_e$ indexed by all edges of $B$ whose
endpoints lie in one part. The corresponding incidence vectors lie in
the direct sum of the zero-sum spaces on the parts. The representation
therefore gives
\[
\dim W\leq\sum_{j=1}^d(|V_j|-1)=n-d.
\]
Let $P$ be the orthogonal projection onto $W^\perp$, so that
$\operatorname{tr}P\geq d-1$. Taking the trace after multiplication by
$P$ preserves the stated positive-semidefinite inequality: indeed,
$\operatorname{tr}(PQ)\geq0$ for positive-semidefinite $P,Q$.
Writing $E_A(\mathcal P)$ for the edges of $A$ crossing the partition,
we obtain
\begin{align*}
c(d-1)
&\leq c\operatorname{tr}P
\leq\operatorname{tr}\left(P\sum_{e\in A}z_ez_e^{\mathsf T}\right)\\
&=\sum_{e\in E_A(\mathcal P)}\|Pz_e\|^2
\leq\frac{1+\rho}{q}|E_A(\mathcal P)|.
\end{align*}
The within-part terms vanish by the choice of $P$. Every partition
therefore has at least $\lfloor cq/(1+\rho)\rfloor(d-1)$ crossing
edges. Theorem~\ref{thm:packing} completes the proof; if the floor is
zero, the conclusion is immediate.
\end{proof}
\section{One sparsification step}
\label{sec:sparsification}
We first derive the exact consequence of the Marcus--Spielman--Srivastava
random-vector theorem~\cite[Theorem~1.4]{MSS}
needed here. The use of deterministic padding permits singular
covariance matrices and keeps both halves under simultaneous control.
\begin{lemma}[Two-sided splitting]
\label{lemma:two-system-split}
Let $w_e\in\mathbb R^D$ be finitely many vectors, let
$\Sigma=\sum_e w_ew_e^{\mathsf T}\preceq2I_D$, and suppose that
$\|w_e\|^2\leq\epsilon$ for every $e$, where $\epsilon>0$.
There is a subset $A$ of the indices for which
\begin{equation}
\frac12\Sigma-\tau I_D
\preceq\sum_{e\in A}w_ew_e^{\mathsf T}
\preceq\frac12\Sigma+\tau I_D,
\qquad \tau=2\sqrt\epsilon+\epsilon.
\label{eq:two-sided-split}
\end{equation}
\end{lemma}
\begin{proof}
Independently for each $e$, let $v_e\in\mathbb R^{2D}$ equal
$(w_e,0)$ or $(0,w_e)$, each with probability $1/2$. Then
\[
M:=\sum_e\mathbb E[v_ev_e^{\mathsf T}]
=\operatorname{diag}(\Sigma/2,\Sigma/2)\preceq I_{2D},
\qquad \mathbb E\|v_e\|^2=\|w_e\|^2\leq\epsilon.
\]
To make the covariance exactly isotropic, diagonalize the
positive-semidefinite matrix $I_{2D}-M$. For each positive eigenvalue
$\lambda$ with unit eigenvector $f$, put
$m_\lambda=\lceil\lambda/\epsilon\rceil$ and introduce
$m_\lambda$ deterministic vectors equal to
$\sqrt{\lambda/m_\lambda}\,f$.
There are finitely many such vectors; each has squared norm at most
$\epsilon$, and their outer products sum to $I_{2D}-M$.
Deterministic vectors have singleton support and are independent of
all other vectors. Consequently Theorem~\ref{thm:mss} applies to the
enlarged family.
In its successful outcome, let $A$ be the indices assigned to the first
block, and set $S_A=\sum_{e\in A}w_ew_e^{\mathsf T}$.
Subtracting the fixed padding matrix from the theorem's conclusion
gives
\[
\operatorname{diag}(S_A,\Sigma-S_A)
\preceq M+\bigl((1+\sqrt\epsilon)^2-1\bigr)I_{2D}
=M+\tau I_{2D}.
\]
The first block gives the upper bound in
\eqref{eq:two-sided-split}; the second block gives its lower bound.
\end{proof}
\begin{proposition}[Packing-preserving sparsification]
\label{prop:step}
There is an absolute integer $r_{\mathrm{step}}$ such that the following
holds for every integer $r\geq r_{\mathrm{step}}$. If $H$ has at
least two vertices and contains $r$ edge-disjoint spanning trees, set
\[
u=r^{-1/16},\qquad q=\lfloor(1-u)r\rfloor,
\qquad \epsilon=6r^{-1/2},\qquad
\tau=2\sqrt\epsilon+\epsilon.
\]
Then $H$ has a spanning subgraph $H'$ containing at least
\begin{equation}
r'=\left\lfloor\frac{(1-4u)r}{2}\right\rfloor
\label{eq:step-packing-count}
\end{equation}
edge-disjoint spanning trees, such that every nonempty proper
$S\subset V(H)$ satisfies
\begin{equation}
|\delta_{H'}(S)|\leq
\left(\frac12+3\tau\right)|\delta_H(S)|.
\label{eq:step-cut-bound}
\end{equation}
The cutoff may be chosen so that, in addition,
\begin{equation}
\frac5{16}\leq\frac{r'}r\leq\frac12,
\qquad
\frac{\frac12+3\tau}{r'/r}\leq1+15u.
\label{eq:step-ratio-bound}
\end{equation}
\end{proposition}
\begin{proof}
Write $n=|V(H)|$. Choose the cutoff large enough for
Theorem~\ref{thm:extraction}, and
also require $r\geq16^{16}$, so $u\leq1/16$.
The extraction theorem supplies a positive definite matrix $X$ with
\[
X\succeq L_H,
\qquad
\mathbf1_S^{\mathsf T}X\mathbf1_S
\leq3\mathbf1_S^{\mathsf T}L_H\mathbf1_S
\quad(\varnothing\ne S\ne V),
\]
and $q$ edge-disjoint spanning trees all of whose edges satisfy
$b_e^{\mathsf T}X^{-1}b_e\leq4r^{-1/2}$.
Let $B$ be precisely the union of these trees. Apply
Lemma~\ref{lem:auxiliary-representation} to $B$ with $\rho=u$, and put
\[
a_e=X^{-1/2}b_e,\qquad w_e=(a_e,z_e),
\qquad\Sigma=\sum_{e\in B}w_ew_e^{\mathsf T}.
\]
The covariance includes cross blocks:
\[
\Sigma=\begin{pmatrix}
X^{-1/2}L_BX^{-1/2}&\displaystyle\sum_{e\in B}a_ez_e^{\mathsf T}\\
\displaystyle\sum_{e\in B}z_ea_e^{\mathsf T}&I_{n-1}
\end{pmatrix}.
\]
They need not vanish. Nevertheless, for any vectors $x,y$ in the two
coordinate spaces,
\begin{align*}
(x,y)^{\mathsf T}\Sigma(x,y)
&=\sum_{e\in B}\bigl(\langle x,a_e\rangle+
\langle y,z_e\rangle\bigr)^2\\
&\leq2x^{\mathsf T}X^{-1/2}L_BX^{-1/2}x+2\|y\|^2\\
&\leq2(\|x\|^2+\|y\|^2),
\end{align*}
because $L_B\preceq L_H\preceq X$. Hence
$0\preceq\Sigma\preceq2I$ without any invertibility assumption on
$\Sigma$.
Since $q\geq(1-u)r-1\geq r/2$, and $r\geq4$,
\[
\frac{1+u}{q}\leq\frac{17}{8r}\leq2r^{-1/2}.
\]
Thus every $w_e$ has squared norm at most
$4r^{-1/2}+(1+u)/q\leq\epsilon$.
Choose the subset $A\subseteq E(B)$ supplied by
Lemma~\ref{lemma:two-system-split}. The two principal blocks of the
\emph{same} inequality \eqref{eq:two-sided-split} give
\begin{equation}
\sum_{e\in A}z_ez_e^{\mathsf T}\succeq(1/2-\tau)I_{n-1},
\qquad
X^{-1/2}L_AX^{-1/2}
\preceq\tfrac12X^{-1/2}L_BX^{-1/2}+\tau I_n.
\label{eq:same-subset-two-constraints}
\end{equation}
Congruence by $X^{1/2}$ in the second inequality yields
\[
L_A\preceq\tfrac12L_B+\tau X
\preceq\tfrac12L_H+\tau X.
\]
Testing on $\mathbf1_S$ proves \eqref{eq:step-cut-bound} for
$H'=(V,A)$, simultaneously for all cuts.
For the packing assertion, write the errors in terms of $u$:
\[
\epsilon=6u^8,\qquad\tau=2\sqrt6\,u^4+6u^8\leq u/2
\quad(00$, so the first inequality in
\eqref{eq:same-subset-two-constraints} and
Lemma~\ref{lem:projected-trace-packing} give at least
$\lfloor(1/2-\tau)q/(1+u)\rfloor$ trees.
The rounding margin is explicit:
\begin{align*}
&(1-2\tau)\bigl((1-u)r-1\bigr)
-(1+u)(1-4u)r\\
&\quad\geq(1-u)\bigl((1-u)r-1\bigr)
-(1+u)(1-4u)r\\
&\quad=r(u+5u^2)-(1-u)\geq0,
\end{align*}
where $ru=r^{15/16}\geq1$. Consequently
\[
\frac{(1/2-\tau)q}{1+u}\geq\frac{(1-4u)r}{2}.
\]
Taking floors proves \eqref{eq:step-packing-count}.
Finally, the floor in that formula and $1/r\leq u$ give
\[
\frac{r'}r\geq\frac12-2u-\frac1r
\geq\frac12-3u\geq\frac5{16},
\qquad\frac{r'}r\leq\frac12.
\]
Using $\tau\leq u/2$ once more, we obtain
\[
\frac{\frac12+3\tau}{r'/r}
\leq\frac{1+3u}{1-6u}
=1+\frac{9u}{1-6u}\leq1+15u,
\]
which proves \eqref{eq:step-ratio-bound}.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/sparsification.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/references.bib ====
@inproceedings{AOG,
author = {Anari, Nima and Oveis Gharan, Shayan},
title = {\href{https://arxiv.org/abs/1411.4613v4}{Effective-Resistance-Reducing Flows, Spectrally Thin Trees,
and Asymmetric {TSP}}},
booktitle = {2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)},
year = {2015},
pages = {20--39},
publisher = {IEEE},
doi = {10.1109/FOCS.2015.11},
eprint = {1411.4613v4},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
url = {https://arxiv.org/abs/1411.4613v4},
note = {Theorem numbers refer to the full version,
arXiv:1411.4613v4, revised 1 September 2015}
}
@article{MSS,
author = {Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil},
title = {\href{https://annals.math.princeton.edu/2015/182-1/p08}{Interlacing Families {II}: Mixed Characteristic Polynomials
and the {Kadison--Singer} Problem}},
journal = {Annals of Mathematics},
volume = {182},
number = {1},
year = {2015},
pages = {327--350},
doi = {10.4007/annals.2015.182.1.8},
url = {https://annals.math.princeton.edu/2015/182-1/p08}
}
@article{NashWilliams,
author = {Nash-Williams, C. St. J. A.},
title = {\href{https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/jlms/s1-36.1.445}{Edge-Disjoint Spanning Trees of Finite Graphs}},
journal = {Journal of the London Mathematical Society},
volume = {s1-36},
number = {1},
year = {1961},
pages = {445--450},
doi = {10.1112/jlms/s1-36.1.445},
url = {https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/jlms/s1-36.1.445}
}
@article{Tutte,
author = {Tutte, W. T.},
title = {\href{https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/jlms/s1-36.1.221}{On the Problem of Decomposing a Graph into {$n$} Connected Factors}},
journal = {Journal of the London Mathematical Society},
volume = {s1-36},
number = {1},
year = {1961},
pages = {221--230},
doi = {10.1112/jlms/s1-36.1.221},
url = {https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/jlms/s1-36.1.221}
}
@article{Edmonds1965,
author = {Edmonds, Jack},
title = {\href{https://doi.org/10.6028/jres.069B.004}{Minimum Partition of a Matroid Into Independent Subsets}},
journal = {Journal of Research of the National Bureau of Standards--B.
Mathematics and Mathematical Physics},
volume = {69B},
number = {1--2},
year = {1965},
pages = {67--72},
doi = {10.6028/jres.069B.004},
url = {https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p67_A1b.pdf}
}
@article{Brouwer,
author = {Brouwer, L. E. J.},
title = {\href{https://link.springer.com/article/10.1007/BF01456931}{{\"U}ber Abbildung von Mannigfaltigkeiten}},
journal = {Mathematische Annalen},
volume = {71},
number = {1},
year = {1911},
pages = {97--115},
doi = {10.1007/BF01456931},
url = {https://link.springer.com/article/10.1007/BF01456931}
}
@misc{Goddyn,
author = {Goddyn, Luis A.},
title = {\href{https://web.archive.org/web/20211025204852/https://www.sfu.ca/~goddyn/Problems/problems.html}{Some Open Problems {I} Like}},
howpublished = {Online problem list, Problem 4},
year = {2004},
url = {https://web.archive.org/web/20211025204852/https://www.sfu.ca/~goddyn/Problems/problems.html},
note = {Webpage modified 17 March 2004.
Archived 25 October 2021; accessed 23 September 2026}
}
@article{Asadpour,
author = {Asadpour, Arash and Goemans, Michel X. and M{\k{a}}dry, Aleksander
and Oveis Gharan, Shayan and Saberi, Amin},
title = {\href{https://pubsonline.informs.org/doi/10.1287/opre.2017.1603}{An {$O(\log n/\log\log n)$}-Approximation Algorithm for the
Asymmetric Traveling Salesman Problem}},
journal = {Operations Research},
volume = {65},
number = {4},
year = {2017},
pages = {1043--1061},
doi = {10.1287/opre.2017.1603},
url = {https://pubsonline.informs.org/doi/10.1287/opre.2017.1603},
note = {An earlier version appeared in SODA 2010}
}
@inproceedings{AsadpourSODA,
author = {Asadpour, Arash and Goemans, Michel X. and M{\k{a}}dry, Aleksander
and Oveis Gharan, Shayan and Saberi, Amin},
title = {\href{https://epubs.siam.org/doi/abs/10.1137/1.9781611973075.32}{An {$O(\log n/\log\log n)$}-Approximation Algorithm for the
Asymmetric Traveling Salesman Problem}},
booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium
on Discrete Algorithms},
year = {2010},
editor = {Charikar, Moses},
pages = {379--389},
publisher = {Society for Industrial and Applied Mathematics},
doi = {10.1137/1.9781611973075.32},
url = {https://epubs.siam.org/doi/abs/10.1137/1.9781611973075.32}
}
@inproceedings{KleinOlverYeoh,
author = {Klein, Nathan and Olver, Neil and Yeoh, Zi Song},
title = {\href{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.129}{Thin Trees for near Minimum Cuts}},
booktitle = {53rd International Colloquium on Automata, Languages,
and Programming (ICALP 2026)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {374},
pages = {129:1--129:18},
year = {2026},
editor = {Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael
and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ICALP.2026.129},
url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.129}
}
@inproceedings{OveisGharanSaberi2011,
author = {{Oveis Gharan}, Shayan and Saberi, Amin},
title = {\href{https://arxiv.org/abs/0909.2849}{The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus}},
booktitle = {Proceedings of the Twenty-Second Annual ACM--SIAM Symposium on Discrete Algorithms},
pages = {967--975},
year = {2011},
publisher = {SIAM},
doi = {10.1137/1.9781611973082.75},
eprint = {0909.2849},
archivePrefix = {arXiv},
note = {Theorem numbers refer to the full preprint, arXiv:0909.2849}
}
@inproceedings{KleinOlver2023,
author = {Klein, Nathan and Olver, Neil},
title = {\href{https://arxiv.org/abs/2304.07674}{Thin Trees for Laminar Families}},
booktitle = {2023 IEEE 64th Annual Symposium on Foundations of Computer Science},
pages = {50--59},
year = {2023},
publisher = {IEEE},
doi = {10.1109/FOCS57990.2023.00011},
eprint = {2304.07674},
archivePrefix = {arXiv}
}
@article{SvenssonTarnawskiVegh2020,
author = {Svensson, Ola and Tarnawski, Jakub and V{\'e}gh, L{\'a}szl{\'o} A.},
title = {\href{https://doi.org/10.1145/3424306}{A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem}},
journal = {Journal of the ACM},
volume = {67},
number = {6},
pages = {37:1--37:53},
year = {2020},
doi = {10.1145/3424306},
note = {An earlier version appeared in STOC 2018}
}
@article{TraubVygen2022,
author = {Traub, Vera and Vygen, Jens},
title = {\href{https://doi.org/10.1137/20M1339313}{An Improved Approximation Algorithm for the Asymmetric Traveling Salesman Problem}},
journal = {SIAM Journal on Computing},
volume = {51},
number = {1},
pages = {139--173},
year = {2022},
doi = {10.1137/20M1339313},
note = {An earlier version appeared in STOC 2020}
}
@article{Barthe1998,
author = {Barthe, Franck},
title = {\href{https://arxiv.org/abs/math/9705210}{On a reverse form of the {Brascamp--Lieb} inequality}},
journal = {Inventiones Mathematicae},
volume = {134},
number = {2},
pages = {335--361},
year = {1998},
doi = {10.1007/s002220050267},
eprint = {math/9705210},
archivePrefix = {arXiv},
note = {Section locators refer to the full preprint, arXiv:math/9705210}
}
@article{Sperner1928,
author = {Sperner, Emanuel},
title = {\href{https://doi.org/10.1007/BF02940617}{Neuer Beweis f{\"u}r die Invarianz der Dimensionszahl und des Gebietes}},
journal = {Abhandlungen aus dem Mathematischen Seminar der Universit{\"a}t Hamburg},
volume = {6},
pages = {265--272},
year = {1928},
doi = {10.1007/BF02940617}
}
@article{SpielmanSrivastava2011,
author = {Spielman, Daniel A. and Srivastava, Nikhil},
title = {\href{https://doi.org/10.1137/080734029}{Graph Sparsification by Effective Resistances}},
journal = {SIAM Journal on Computing},
volume = {40},
number = {6},
pages = {1913--1926},
year = {2011},
doi = {10.1137/080734029}
}
@article{BatsonSpielmanSrivastava2012,
author = {Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil},
title = {\href{https://doi.org/10.1137/090772873}{Twice-{Ramanujan} Sparsifiers}},
journal = {SIAM Journal on Computing},
volume = {41},
number = {6},
pages = {1704--1721},
year = {2012},
doi = {10.1137/090772873}
}
@misc{ConstructiveThinTreesCompanion,
author = {{OpenAI}},
title = {{A polynomial-time construction of strong thin trees}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/paper.pdf}{OAI:A-polynomial-time-construction-of-strong-thin-trees-September-23-2026}},
year = {2026}
}
@inproceedings{HarveyOlver2014,
author = {Harvey, Nicholas J. A. and Olver, Neil},
title = {\href{https://arxiv.org/abs/1307.2274v1}{Pipage Rounding, Pessimistic Estimators and Matrix Concentration}},
booktitle = {Proceedings of the Twenty-Fifth Annual ACM--SIAM Symposium on Discrete Algorithms},
editor = {Chekuri, Chandra},
pages = {926--945},
publisher = {Society for Industrial and Applied Mathematics},
year = {2014},
doi = {10.1137/1.9781611973402.69},
eprint = {1307.2274v1},
archivePrefix = {arXiv},
note = {Appendix locators refer to the full version,
arXiv:1307.2274v1, 8 July 2013}
}
==== END The-strong-thin-tree-conjecture//source/references.bib ====