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}<s<4r^{-1/2}
\]
distinct from every \(R_X(e)\), \(e\in E(H)\).
This is possible because the graph is finite.
If \(\phi_{p,j}(X_p)>0\), then
\[
\|C_{p,j}-X\|<p^{-1}+\|X_p-X\|\longrightarrow0
\]
uniformly over these centers. The resistance of each edge is
continuous on \(\mathcal K\). Since all resistances at \(X\) avoid
\(s\), for all sufficiently large \(p\) every contributing center
has exactly the same threshold graph, packing partition, and
crossing set as \(X\).
Write \(B=B_s(X)\), \(M=|B|\), and
\(\delta=C_0r^{-1/4}\). If \(M=0\), connectedness of \(H\) implies
that its partition is \(\{V\}\), and the conclusion already follows.
Otherwise, for large \(p\), each contributing \(Y_{p,j}\) has at
most \(\delta M\) bad edges in this same set \(B\).
Summing their bad indicators with weights \(\phi_{p,j}(X_p)\)
shows that at most \(2\delta M\) edges receive bad weight greater
than one half.
For every other edge \(e\in B\), at least half the total weight is
on matrices satisfying
\[
Y_{p,j}\succeq r^{1/2}b_eb_e^{\mathsf T},
\]
by Lemma~\ref{lem:resistance-order}. All remaining matrices are
positive semidefinite. Hence their convex combination satisfies
\[
X_p\succeq\tfrac12r^{1/2}b_eb_e^{\mathsf T},
\qquad R_{X_p}(e)\le2r^{-1/2}.
\]
Thus at least \(N=\lceil(1-2\delta)M\rceil\) edges satisfy this
closed inequality. The condition that at least \(N\) edges of the
finite set \(B\) obey it is closed: it is a finite union, over
\(N\)-element subsets of \(B\), of finite intersections of closed
conditions.
The same count therefore holds at the limit \(X\).
Since \(2r^{-1/2}<s\), these edges belong to \(F_s(X)\).
Suppose \(\mathcal P_s(X)\) has \(d>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}<u\). Then
\[
|E_{F_s(X)}(\mathcal P_s(X))|
\ge(1-2C_0r^{-1/4})M
>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 \(i<d\), since then none of its vertices could
receive label \(i\). Hence these are exactly the fully labeled
top-dimensional simplices in the induced triangulation of
\(x_d=0\). The labels there satisfy the same rule in dimension
\(d-1\), and induction makes their number odd.
\end{proof}
\subsection{From a simplex to a compact convex set}
\begin{proof}[Proof of Theorem~\ref{thm:fixedpoint}]
First let \(F:\Delta_d\to\Delta_d\) be continuous. The case
\(d=0\) is immediate. In each of the successive barycentric
subdivisions, a vertex fixed by \(F\) already proves the claim.
Otherwise label each vertex \(v\) by an index \(i\) for which
\(v_i>F_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 $a<b$:
\begin{equation}
\operatorname{tok}_\ell(A)=
\begin{cases}
\delta_\ell-C_4\delta_{\ell+1},
&A\text{ is an original ball of the current family }\mathcal F_\ell,\\
[b-a-C_4\delta_\ell]_+,
&A\text{ is nonavoiding and is not such an original ball},\\
[b-a-C_4\delta_\ell]_+/\bigl(2(C_4+2)\bigr),
&A\text{ is avoiding}.
\end{cases}
\label{ha:potential}
\end{equation}
Here and below, membership in a family refers to one of its original
balls, with its original record, rather than to a newly created shell
that happens to have the same support. The first line satisfies
\begin{equation}
\delta_\ell-C_4\delta_{\ell+1}\geq\frac56\delta_\ell.
\label{ha:fresh-potential}
\end{equation}
Every potential is at most the width of its record. An empty shell,
including a proposed shell whose outer radius is at most its inner
radius, is discarded and contributes zero.
We describe the processing of a fixed bag $\operatorname{Bag}_t$ in
phase $\ell$. Put $\delta=\delta_\ell$. Initially partition its balls
into the interior balls $\operatorname{Int}_t$ and the border balls
$\operatorname{Bor}_t$. The sets contain only balls still awaiting
treatment. Repeatedly perform one of the three operations below while
\begin{equation}
|\operatorname{Int}_t|\geq\frac12|\operatorname{Bag}_t|.
\label{ha:interior-loop}
\end{equation}
After an operation, remove the balls explicitly treated by it from
$\operatorname{Int}_t$, and transfer every remaining ball that has
ceased to be interior to $\operatorname{Bor}_t$. Lemma~\ref{ha:border-monotone}
ensures that this transfer is permanent. A ball removed in one of the
three operations is counted as treated even in the third operation,
where a pair of new shells pays for it without inserting that ball.
The subscript $s$ denotes the state after $s$ operations for this bag;
the subscript $\infty$ denotes the final state. In particular, set
\[
n_{t,s}=|\operatorname{Bag}_t|
-|\operatorname{Bor}_{t,s}|-|\operatorname{Int}_{t,s}|.
\]
Moving a ball from the interior set to the border set does not change
$n_{t,s}$. Treating $m$ balls increases it by exactly $m$.
\begin{lemma}[Potential preserved during interior processing]
\label{ha:construction}
Suppose phase $\ell$ starts with a valid arrangement whose potentials
can pay each earlier node $v\in T_i$, $i<\ell$, at least
$(\theta/2)|\operatorname{Bag}_v|\delta_i$. Interior processing preserves
validity and these allocations. At every intermediate state it also
pays each completed node $v\in T_\ell$ at least
$\theta n_{v,\infty}\delta_\ell$, and the node currently being processed
at least $\theta n_{t,s}\delta_\ell$.
Each bag finishes with
$|\operatorname{Int}_{t,\infty}|<|\operatorname{Bag}_t|/2$.
\end{lemma}
\begin{proof}
We maintain actual allocations of the potentials, so that an operation
must preserve all amounts already allocated. If an old record $B$ is
removed, it suffices to set aside at least
$\operatorname{tok}_\ell(B)$ from its replacements: those funds can
then be distributed exactly as the old potential was. Any additional
funds assigned to $t$ increase its allocation. Untouched records retain
their allocations.
Shrinking a record about its existing center and retaining its labels
preserves all its individual validity conditions. Indeed, its old
inner witness remains inside the new inner radius, its old crossing
paths still cross the smaller radial interval, and all excluded
boundary endpoints remain beyond the new outer radius. Pairwise
validity is inherited by Lemma~\ref{ha:heredity}. These observations
apply to every residual shell below. Original current-family balls
are never carved: their width is $\delta$, whereas a record containing
an interior ball must have width greater than $2C_3\delta$.
\paragraph{\textbf{Operation 1: carving an avoiding shell.}}
If some $A=B(X_u,\delta)\in\operatorname{Int}_t$ lies in an avoiding
shell $B=B(x,r_1\Vert r_2)$, put $q=\|X_u-x\|_1$ and replace $B$ by
\[
B_1=B(x,r_1\Vert q-\delta),\qquad
B_2=B(x,q+\delta\Vert r_2),
\]
both with the labels of $B$. Insert the original ball $A$, with its
original labels, and treat it. The two residual shells are disjoint
from $A$. The original ball satisfies its individual validity
conditions, and Lemma~\ref{ha:unique-interior} shows that its labels
are compatible with every other existing record. This proves validity
of the new arrangement.
Write $R=r_2-r_1$. Since $R>2C_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<r_2$, containing in its interior a ball with center $u_0\in U_i$.
Such a record exists because
every ball still under consideration is interior and operation 1 is
unavailable. Write $\rho(z)=\|X_z-x\|_1$ and put
\begin{equation}
a=\max\{r_1,\min_{v\in V_i}\rho(v)\},\qquad
b=\min\{r_2,\max_{v\in V_i}\rho(v)\},\qquad L=b-a.
\label{ha:radial-endpoints}
\end{equation}
The neighbor of $u_0$ in $V_i$ has radius strictly between
$r_1+(C_3-1)\delta$ and $r_2-(C_3-1)\delta$. In particular $a\leq b$.
Define
\[
\mathcal A=
\{B(X_u,\delta)\in\operatorname{Int}_t:
a-\delta<\rho(u)<b+\delta\},
\qquad U_{\mathcal A}=\{u:B(X_u,\delta)\in\mathcal A\},
\qquad m=|\mathcal A|.
\]
The set $\mathcal A$ is nonempty, since it contains the ball centered
at $u_0$.
Every ball $A\in\mathcal A$ is in the interior of $B$. To check this
carefully, the radial inequalities defining $\mathcal A$ imply that
$A$ meets the support of $B$: its center is less than $\delta$ in
radial distance from $[r_1,r_2]$. This assertion also holds for supports
restricted to the cube. To decrease radius, move towards the binary
center $x$; to increase it, move towards the opposite cube vertex.
Along either segment, the change of radius equals the distance moved.
Since $B$ is nonempty, one can therefore reach a point of $B$ within
distance strictly less than $\delta$. All balls of $\operatorname{Bag}_t$
have the same labels, so $C(A)$ intersects $C(B)$. Also $A$ is
interior to some existing record $B'$. If $B'\ne B$, then $B$ meets
$B'$ at a point of $A$, since the interior margin implies $A\subseteq
B'$. Lemma~\ref{ha:unique-interior} contradicts
$C(A)\cap C(B)\ne\varnothing$. Therefore $B'=B$, as claimed.
We need one more radial estimate:
\begin{equation}
U_i\not\subseteq U_{\mathcal A}
\quad\Longrightarrow\quad L\geq(C_3-1)\delta.
\label{ha:radial-range}
\end{equation}
If every $v\in V_i$ had $r_1<\rho(v)<r_2$, then all their radii would
lie in $[a,b]$. Each $u\in U_i$ has a neighbor $v\in V_i$ with
$|\rho(u)-\rho(v)|<\delta$, so it would lie in $U_{\mathcal A}$.
Hence the premise of \eqref{ha:radial-range} supplies some $v\in V_i$
with $\rho(v)\geq r_2$ or $\rho(v)\leq r_1$. Let $w\in V_i$ be a
neighbor of the chosen interior center $u_0$.
If $\rho(v)\geq r_2$, then $b=r_2$, while
\[
a\leq\rho(w)<\rho(u_0)+\delta
<r_2-(C_3-1)\delta.
\]
If $\rho(v)\leq r_1$, then $a=r_1$, while
\[
b\geq\rho(w)>\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},
$L<m\delta/3$, \eqref{ha:dense-count}, and
\eqref{ha:constant-consequences}. Each inserted ball retains at least
$(1/4)(5/6)\delta=5\delta/24\geq\theta\delta$ to give to $t$.
Thus this operation supplies at least $\theta m\delta$ new credit.
\paragraph{\textbf{Operation 3: a sparse group in the radial interval.}}
Suppose $m\delta\leq3L$. We first record that
\begin{equation}
L\geq(C_3-1)\delta.
\label{ha:sparse-width}
\end{equation}
If $U_i\not\subseteq U_{\mathcal A}$ this follows from
\eqref{ha:radial-range}; otherwise
$L\geq m\delta/3\geq|U_i|\delta/3\geq C_3\delta$.
In particular, all the central shells defined next have positive width.
Replace $B$ by the two residual shells
\[
B_1=B(x,r_1\Vert a),\qquad B_2=B(x,b\Vert r_2),
\]
with its labels. Insert two additional shells
\[
B_3=B(x,a+\delta\Vert b-\delta),\qquad
B_4=B(x,a\Vert b).
\]
The shell $B_3$ is nonavoiding and $B_4$ is avoiding. Give them labels
\begin{equation}
\begin{array}{c|ccc}
&t(\,\cdot\,)&t_d(\,\cdot\,)&t_P(\,\cdot\,)\\ \hline
B_3&t&\text{none}&
\{v\in t_P(B):v\text{ is a proper descendant of }t\}\\
B_4&t(B)&t&t_P(B).
\end{array}
\label{ha:central-labels}
\end{equation}
Treat all the balls of $\mathcal A$, removing them from
$\operatorname{Int}_t$ without inserting them.
We verify every new labeling condition. Lemma~\ref{ha:ancestor}
implies that $t(B)$ is a weak ancestor of $t$ and that $t\in C(B)$.
In fact $t(B)\ne t$. An original ball with owner $t$ cannot meet an
unprocessed ball of the same family, since that family is disjoint.
A synthetic shell with owner $t$ could only have been created by an
earlier occurrence of this operation while processing this very bag:
the sets $T_i$ are disjoint, and new nonavoiding owners are assigned
only to the node being processed. At that earlier occurrence every
remaining interior ball meeting the new central shell was in its
expanded radial interval and was treated. Subsequent changes only
restrict that shell, and Lemma~\ref{ha:border-monotone} prohibits the
return of a border ball to the interior set. Hence neither that shell
nor any of its residual pieces can now contain an unprocessed
interior ball. This proves $t(B)\ne t$. Thus $t$ is a proper
descendant of $t(B)$, as required for $B_4$ to be avoiding.
Using $\mathcal T[t]$ for the subtree rooted at $t$, the labels give
\begin{equation}
C(B_3)=C(B)\cap\mathcal T[t],
\qquad C(B_4)=C(B)\setminus\mathcal T[t].
\label{ha:conflict-partition}
\end{equation}
Indeed, no member of $t_P(B)$ is a weak ancestor of $t$, since
$t\in C(B)$; every remaining excluded subtree either lies below $t$
or is disjoint from its subtree. Both new conflict domains have the
prescribed connected form and are subsets of $C(B)$. All four shells
are subsets of $B$. The pairwise validity with old records follows
from Lemma~\ref{ha:heredity}; the residual shells are disjoint from
the central shells, and \eqref{ha:conflict-partition} proves validity
of the overlapping pair $B_3,B_4$. Finally, both new excluded-node
sets are subsets of $t_P(B)$ and both new outer radii are at most
$r_2$. Thus the excluded-boundary-endpoint condition is preserved.
It remains to prove the crossing-path condition, which does not follow
merely from shrinking the geometric support when labels change.
Choose vertices $v_1,v_2\in V_i$ minimizing and maximizing $\rho$, and
choose their respective neighbors $u_1,u_2\in U_i$ along edges of
$O'(t)$. Clipping in \eqref{ha:radial-endpoints} gives
\begin{equation}
\rho(v_1)\leq a,\quad \rho(v_2)\geq b,
\qquad \rho(u_1)<a+\delta,\quad \rho(u_2)>b-\delta.
\label{ha:radial-witnesses}
\end{equation}
By \eqref{ha:sparse-width}, $a+\delta<b\leq r_2$. Hence
$\rho(u_1)<r_2$ and $\rho(v_1)<r_2$; these strict inequalities will
exclude membership in the forbidden subtrees.
For $B_3$, the $k$-edge-connectivity of $G[V(t)]$ and
Lemma~\ref{ha:edge-paths} supply $k$ edge-disjoint $u_1$--$u_2$ paths.
The radial inequalities show that
each crosses $B_3$. To see that the initial vertex is in $C(B_3)$,
fix $z\in t_P(B_3)$. If $u_1\in V(z)$, the edge
$\{u_1,v_1\}\in O'(t)$ would belong to $P(z)$ because $z$ is below
$t$ and $v_1\notin V(t)$. This contradicts the endpoint condition of
$B$, since $z\in t_P(B)$ but $\rho(u_1)<r_2$. Thus $u_1$ avoids
every excluded subtree and lies in $C(B_3)$. These paths and this
initial vertex prove the required crossing condition for $B_3$.
For $B_4$, every cut separating $v_1$ from $v_2$ in $G[S_i]$ has
at least $\lceil k/4\rceil$ edges. Lemma~\ref{ha:edge-paths}
therefore supplies at least $k/4$ edge-disjoint $v_1$--$v_2$ paths.
Since $t(B)$ is a proper
ancestor of $t$, $V(t^*)\subseteq V(t(B))$. The paths therefore lie
in $V(t(B))\setminus V(t)$ and cross $B_4$. Fix $z\in t_P(B_4)$.
The edge $\{u_1,v_1\}$ cannot belong to $P(z)$ because
$\rho(v_1)<r_2$. If $v_1\in V(z)$, it follows that $u_1\in V(z)$
also. A hierarchy set containing both $u_1\in V(t)$ and
$v_1\notin V(t)$ must be a proper ancestor of $t$, by laminarity.
This would make $z$ a weak ancestor of $t$, contrary to $t\in C(B)$.
Hence $v_1$ lies in none of the excluded subtrees; also
$v_1\notin V(t)$, so $v_1\in C(B_4)$. This verifies the crossing
condition for $B_4$ and completes the proof of validity.
For later use, every still-unprocessed interior ball is disjoint from
$B_3$ and $B_4$: its center is outside the expanded interval
$(a-\delta,b+\delta)$. Such a ball can remain interior to $B_1$ or
$B_2$, which is harmless. This establishes the property of new
central shells used above to prove that $t(B)$ is a proper ancestor.
We now distribute the new potentials. The shell $B_3$, although
created in the current phase, is not an original current-family ball;
it uses the second line of \eqref{ha:potential}. Give $B$ all the
potential of $B_1,B_2,B_3$ and $(2C_4+2)\delta$ from $B_4$.
The sum of the three formal nonavoiding widths is $R-2\delta$,
where $R=r_2-r_1$. Consequently
\begin{align*}
\sum_{j=1}^3\operatorname{tok}_\ell(B_j)+(2C_4+2)\delta
&\geq R-2\delta-3C_4\delta+(2C_4+2)\delta\\
&=R-C_4\delta=\operatorname{tok}_\ell(B).
\end{align*}
The following estimate proves both that $B_4$ has the amount just
promised and that it can additionally pay for all $m$ treated balls:
\begin{align*}
\operatorname{tok}_\ell(B_4)-(2C_4+2)\delta
&=\frac{L-C_4\delta-4(C_4+1)(C_4+2)\delta}{2(C_4+2)}\\
&\geq\frac{L-\{C_4+4(C_4+2)^2\}\delta}{2(C_4+2)}\\
&\geq\frac{L-(C_3-1)\delta/2}{2(C_4+2)}\\
&\geq\frac{L}{4(C_4+2)}
\geq\frac{m\delta}{12(C_4+2)}
\geq\theta m\delta.
\end{align*}
The first equality is valid because \eqref{ha:sparse-width} makes
$L-C_4\delta$ positive. The other steps use
$C_4+1\leq C_4+2$, \eqref{ha:constant-consequences},
\eqref{ha:sparse-width}, the case assumption $m\delta\leq3L$, and
$C_3\geq2C_4(C_4+2)$, respectively. Give the remaining amount to $t$.
This completes the allocation for operation 3.
Each operation treats at least one interior ball, preserves all old
allocations, and gives $t$ at least $\theta\delta$ for each ball it
treats. Border transfers change neither this count nor any allocation.
Induction on the number of operations proves the stated bound for
$t$, and induction on the bags already processed in the phase proves
the bounds for the other current-phase nodes. The loop terminates
after at most $|\operatorname{Bag}_t|$ operations; its negated stopping
condition gives the asserted strict half-bag bound. This proves the
lemma. The first phase starts with an empty arrangement and no old
allocations; the transfer of these allocations between phases is
verified in the next subsection.
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_construction.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_assigned_order.tex ====
\subsubsection{The order and invariants of the construction}
\label{ha:order}
We now prove Lemma~\ref{ha:insertable-arrangement}. Thus every remaining
bag is $(12C_3/k)$-assigned and every input ball is insertable. There
are finitely many nonempty families; put $\delta_{m+1}=0$ for the final
accounting step. The evolving collection $Z$ consists of labeled
records: different records may have the same geometric support.
It starts empty. Phase $\ell$ handles $\mathcal F_\ell$, processing
its bags in increasing depth of their nodes in $\mathcal T$.
For equal depths choose any order.
For a candidate $A=B(X_u,\delta_\ell)\in\operatorname{Bag}_t$ and
a current record $B\in Z$ with center $x$ and numerical inner and
outer radii $r_1<r_2$, say that $A$ is
\emph{interior to $B$} if
\begin{equation}\label{ha:interior}
C(A)\cap C(B)\ne\varnothing,\qquad
r_1+C_3\delta_\ell<\|X_u-x\|_1<r_2-C_3\delta_\ell.
\end{equation}
A ball interior to some record is an interior ball; every other
candidate is a border ball. In particular, an interior ball is
contained in $B$, by the triangle inequality and $C_3>1$.
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_1<r_2$, by the
concentric restriction
\[
S(B)=B\bigl(x,r_1+(C_3+1)\delta_\ell\ \Vert\
r_2-(C_3+1)\delta_\ell\bigr),
\]
discarding it if the displayed interval has nonpositive width.
Use the same labels on each surviving restriction, and assign a
discarded record token value zero. Finally insert all balls of
$\bigcup_{t\in T_\ell}\operatorname{Bor}_t$ with their original
labels.
Here is a direct verification of separation, including the role
of conflict domains. For a border ball $A=B(X_u,\delta_\ell)$,
consider an old record $B$ whose conflict domain meets $C(A)$.
Lemma~\ref{ha:border-monotone} says that $A$ is still border, so
\[
\|X_u-x\|_1\le r_1+C_3\delta_\ell
\quad\hbox{or}\quad
\|X_u-x\|_1\ge r_2-C_3\delta_\ell.
\]
In the first case every point of $A$ has distance strictly less
than the new inner radius; in the second it has distance strictly
greater than the new outer radius. Thus $A$ does not meet $S(B)$.
If the conflict domains are disjoint no geometric separation is needed.
The original balls in the current family are pairwise disjoint,
so no conflict arises either with an unchanged current-phase ball
or with another newly inserted border ball. The other validity
conditions follow from Lemmas~\ref{ha:input-valid} and
\ref{ha:heredity}. Hence the new collection is valid.
\begin{lemma}[The cost of shrinking]\label{ha:shrink-cost}
Under \eqref{ha:small-excess}, the total token deficit created by
the restrictions satisfies
\[
\mathsf D:=\sum_{B\in Z}\bigl(p(B)-q(S(B))\bigr)
\le\frac12 b\delta_\ell.
\]
Every summand defining $\mathsf D$ is nonnegative.
\end{lemma}
\begin{proof}
For unchanged original balls both the deficit and $q(B)-p(B)$
are zero. For any other record the decrease of width is
$2(C_3+1)\delta_\ell$, unless the record disappears entirely.
This exceeds the decrease of the threshold, so the deficit is
nonnegative. We prove, record by record,
\begin{equation}\label{ha:shrink-comparison}
q(B)-p(B)\ge\frac{C_4}{3C_3}
\bigl(p(B)-q(S(B))\bigr).
\end{equation}
If $p(B)=0$, its deficit is zero and the inequality is immediate.
Otherwise, first take a nonavoiding record of width $w$.
Since $w>C_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<r\},\qquad
B(x,a\Vert b)=\{y\in Q:a<\|x-y\|_1<b\}
\quad(0\le a<b).
\]
An ordinary ball includes its center; a hollow ball has strict inner
and outer boundaries. Its width is $b-a$, and the width of $B(x,r)$
is $r$. When a statement uses inner and outer radii for an ordinary
ball, they mean $0$ and $r$. The sets $B(x,r)$ and
$B(x,0\Vert r)$ differ only at $x$; we keep this distinction when
testing membership. In particular, every test below for an endpoint
in an input ball includes endpoints mapped to its center.
All centers used in the construction are centers of input balls, hence
belong to $\{0,1\}^d$: new hollow balls inherit an existing center.
Consequently, for each such center $x$, the map $y\mapsto\|x-y\|_1$
is affine on $Q$. Intersections here mean intersections in the
continuous cube, not merely intersections on the finite set $X(V)$.
\begin{lemma}[Edge-disjoint paths from cut bounds]\label{ha:edge-paths}
If every cut separating distinct vertices $u,v$ of an undirected
multigraph has at least $q$ edges, where $q$ is a positive integer,
then the graph has $q$ pairwise edge-disjoint $u$--$v$ paths.
\end{lemma}
\begin{proof}
Give each edge an arbitrary orientation and maintain an integral
antisymmetric flow whose value on an oriented edge is in
$\{-1,0,1\}$. Start with zero flow. A directed traversal of an edge
is available when its signed flow in that direction is less than
$1$. As long as the current flow value is less than $q$, augment
by one along an available directed $u$--$v$ path if one exists.
The edge bounds and flow conservation at all other vertices remain
valid, and the value increases by one.
If no such path exists, let $S$ be the vertices reachable from $u$
by available traversals. Then $v\notin S$, and every edge leaving
$S$ has signed outward flow $1$. Summing flow conservation over
$S$ says that the current flow value equals the number of those
edges, at least $q$, a contradiction. Thus the procedure reaches
value $q$ after $q$ augmentations.
An integral flow of positive value contains a directed positive-flow
$u$--$v$ path: otherwise the vertices reachable on positive-flow
edges would have no positive outward flow, contradicting their
positive net flow. Extract such a path and subtract one on its
edges. Repeating extracts $q$ paths. Each used edge had flow $1$
in its traversal direction and then has flow zero, so the extracted
paths are edge-disjoint. Parallel edges are separate edges
throughout the argument.
\end{proof}
Let $\mathcal T[t]$ denote the set of hierarchy nodes in the subtree
rooted at $t$, including $t$. Its leaves are identified with $V(t)$.
Recall that
\[
P(t)=E(V(t),V\setminus V(t)),\qquad
O(t)=E(V(t),V(t^*)\setminus V(t)).
\]
A ball record consists of its geometric ball and its labels; two
records may have the same geometric set. Its owner $t(B)$ is a
hierarchy node. A nonavoiding record will route in $G[V(t(B))]$.
An avoiding record also has a label $t_d(B)$, a strict descendant of
$t(B)$, and will route in
$G[V(t(B))\setminus V(t_d(B))]$. In either case a further label
$t_P(B)$ is a set of strict descendants of $t(B)$. Define the
\emph{conflict domain} and its leaf set by
\begin{align*}
C(B)&=\mathcal T[t(B)]\setminus
\bigcup_{s\in t_P(B)}\mathcal T[s]
&&\text{if $B$ is nonavoiding},\\
C(B)&=\mathcal T[t(B)]\setminus
\left(\mathcal T[t_d(B)]\cup
\bigcup_{s\in t_P(B)}\mathcal T[s]\right)
&&\text{if $B$ is avoiding},\\
L(B)&=C(B)\cap V.
\end{align*}
Thus $C(B)$ is a connected set of hierarchy nodes containing its root
$t(B)$. The set $L(B)$, rather than the geometric points of $B$,
specifies the graph vertices available for charging.
\Needspace{13\baselineskip}
\begin{definition}[Valid labeling]\label{ha:valid-labeling}
A collection $Z$ of labeled ordinary and hollow balls is valid if the
following four conditions hold for every record $B$ with center $x$
and radii $a<b$.
\begin{enumerate}
\renewcommand{\theenumi}{L\arabic{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\item\label{ha:L1} The labels and conflict domain have the form just
described; in particular $t(B)\in C(B)$.
\item\label{ha:L2} For $s\in t_P(B)$ and $\{v,w\}\in P(s)$,
\[
\|x-X_v\|_1\ge b,\qquad \|x-X_w\|_1\ge b.
\]
\item\label{ha:L3} There is $u\in L(B)$ with $\|x-X_u\|_1\le a$
and at least $k/4$ pairwise edge-disjoint paths starting at $u$ and
ending at vertices of distance at least $b$ from $x$. The paths lie
in $G[V(t(B))]$ if $B$ is nonavoiding, and in
$G[V(t(B))\setminus V(t_d(B))]$ if it is avoiding.
\item\label{ha:L4} Distinct records whose geometric balls intersect
have disjoint conflict domains.
\end{enumerate}
\end{definition}
The paths in \ref{ha:L3} may initially visit predecessor subtrees;
condition~\ref{ha:L2} will allow their relevant prefixes to avoid all
of them. Also, the shape of the domains gives the useful equivalence
\begin{equation}\label{ha:domain-root-test}
C(B)\cap C(B')\ne\varnothing
\quad\Longleftrightarrow\quad
t(B)\in C(B')\ \hbox{or}\ t(B')\in C(B).
\end{equation}
Indeed, a common node lies below both roots. The roots are therefore
comparable, and the path from the higher root to that common node
contains the lower root and stays in the higher root's domain.
The converse follows since each root belongs to its own domain.
\paragraph{Predecessors and insertability.}
For $t\in T_i$ define
\[
\operatorname{Pred}(t)=
\{s:\ s\text{ is a strict descendant of }t,
\ s\in T_j\text{ for some }j<i\}.
\]
For $B=B(X_u,\delta_i)\in\operatorname{Bag}_t$, say that $B$ is
\emph{noninsertable by $s$} if $s\in\operatorname{Pred}(t)$ and an
endpoint $w$ of an edge of $P(s)$ satisfies
$\|X_u-X_w\|_1<\delta_i$. A ball is \emph{insertable} if no
predecessor makes it noninsertable. Every insertable input ball is
labeled nonavoiding, with
\[
t(B)=t,\qquad t_P(B)=\operatorname{Pred}(t).
\]
Its center vertex $u$ belongs to $L(B)$. To verify this, use the
assigned-bag property to choose an edge $\{u,v\}\in O(t)$ with
$v\notin V(t)$. If $u\in V(s)$ for a predecessor $s$ of $t$, then
$\{u,v\}\in P(s)$. Its endpoint $u$ is in the center-inclusive
ball $B$, contrary to insertability. This argument also covers
distinct graph vertices having the same image under $X$.
\begin{lemma}[Cost of one predecessor]\label{ha:pruning}
Suppose $\delta_{i+1}\le\lambda\delta_i$ with $\lambda\le1/2$,
$|O(t)|\ge k\lambda|P(t)|$ for the selected hierarchy nodes, and each
bag is at least $C_3/k$-assigned. For $s\in T_\ell$,
\[
\sum_i\delta_i
|\{B\in\mathcal B_i:B\text{ is noninsertable by }s\}|
\le \frac{4}{C_3}\delta_\ell|\operatorname{Bag}_s|.
\]
\end{lemma}
\begin{proof}
The set being counted is empty for $i\le\ell$. For each $i>\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 $a<b$. Take the paths in
\ref{ha:L3}, and stop each at its first vertex $z$ satisfying
$\|x-X_z\|_1\ge b$. Every vertex in each resulting graph path
belongs to $L(B)$. Avoidance of $V(t_d(B))$ already follows from
\ref{ha:L3}. To check avoidance of $V(s)$ for $s\in t_P(B)$,
suppose the path first enters $V(s)$ along $\{v,w\}\in P(s)$.
The start vertex is outside $V(s)$, so this entering edge exists.
Its preceding endpoint $v$ occurs before the stopping vertex and
therefore has $\|x-X_v\|_1<b$. This contradicts \ref{ha:L2}.
In particular, both graph endpoints of every edge of the stopped
path are in $L(B)$, including the edge containing its geometric
exit point.
On each of the resulting continuous curves, keep the portion between
the last point at radius $a$ preceding its first point at radius $b$
and that first point at radius $b$. Those points exist by continuity.
The retained curve, apart from its endpoints, is in the open shell
$a<\|x-y\|_1<b$. The function $y\mapsto\|x-y\|_1$ is
$1$-Lipschitz, so its length is at least $b-a$. This also applies to
an ordinary ball by taking $a=0$; removing its center changes no
charged length. Charge each retained portion to its underlying
graph edge. The paths for one record are edge-disjoint, so this
record charges no portion of a graph edge twice.
Now fix a graph edge $e=\{v,w\}$. If two distinct records charge
portions of $e$, the preceding paragraph gives
$v,w\in L(B)\cap L(B')$, so their conflict domains meet.
Condition~\ref{ha:L4} forces their geometric balls to be disjoint.
Hence their charged open portions of the fixed segment of $e$ are
disjoint. Summing over all records charges $e$ at most $\ell_e$.
This reasoning uses edge portions, not the whole length of every
edge on a witness path. It also handles zero-length edges, which
contribute no charge. Each record receives at least
$(k/4)(b-a)$, and summing the edge budgets proves the claim.
\end{proof}
\begin{lemma}[Arrangement of insertable bags]\label{ha:insertable-arrangement}
Let $\mathcal T$ be a locally $k$-connected hierarchy, with selected
nonroot nodes $T$ satisfying $|O(t)|\ge k\lambda|P(t)|$ for $t\in T$.
Let $\mathcal F_i$ be a $\lambda$-geometric sequence of families
of $12C_3/k$-assigned bags of type $(\delta_i,T_i)$, where the
$T_i\subseteq T$ are pairwise disjoint. Suppose all input balls are
insertable and
\[
C_4\ge3,\qquad \lambda\le\frac{1}{6C_4},\qquad
C_3\ge2\bigl((C_4+1)+4(C_4+2)^2\bigr).
\]
Then there is a finite valid collection $Z$ of labeled ordinary and
hollow balls, with centers inherited from the input balls, such that
\begin{equation}\label{ha:arrangement-width}
\sum_{B\in Z}\operatorname{width}(B)
\ge \frac{C_4}{12C_3}
\sum_i\delta_i\sum_{t\in T_i}|\operatorname{Bag}_t|.
\end{equation}
\end{lemma}
The next parts prove Lemma~\ref{ha:insertable-arrangement}. First we
show that it suffices for the assigned-bag proposition.
\begin{proof}[Reduction of Proposition~\ref{prop:hierarchy-assigned}
to Lemma~\ref{ha:insertable-arrangement}]
Let
$M=\sum_i\delta_i\sum_{t\in T_i}|\operatorname{Bag}_t|$
be the original total radius. A ball can be noninsertable by several
predecessors; summing Lemma~\ref{ha:pruning} over all selected nodes
therefore bounds the total radius $N$ of noninsertable balls from
above, without needing a unique predecessor charge:
\begin{equation}\label{ha:preprocess-mass}
N\le\frac{4}{C_3}M\le\frac14M.
\end{equation}
Here the original $24C_3/k$ assignment implies the weaker assignment
needed in that lemma, and the displayed condition on $C_3$ implies
$C_3\ge16$.
Delete all noninsertable balls. If a bag retains at least half its
original balls, keep the remaining bag; otherwise delete the bag and
its node from the corresponding $T_i$. A kept bag is
$12C_3/k$-assigned. In a deleted bag more than half the original
balls were noninsertable, so its entire radius is at most twice its
noninsertable radius. The same upper bound holds for the radius
removed from a kept bag. The resulting sequence consequently has
total radius
\[
M'\ge M-2N\ge M/2.
\]
Discard empty families, retaining the remaining scales in their
original order. The sequence retains disjointness at each scale
and the geometric scale condition. Deleting selected nodes can only remove predecessors,
so all surviving balls are still insertable after recomputing their
labels. The hypotheses of Lemma~\ref{ha:insertable-arrangement}
therefore hold. Combining that lemma with
Lemma~\ref{ha:labeled-energy} gives
\[
\sum_{\{v,w\}\in E}\|X_v-X_w\|_1
\ge\frac{k}{4}\frac{C_4}{12C_3}M'
\ge\frac{k}{8}\frac{C_4}{12C_3}M,
\]
as required.
\end{proof}
\begin{lemma}[Validity of an insertable input ball]\label{ha:input-valid}
An insertable ball $B=B(X_u,\delta_i)\in\operatorname{Bag}_t$
with the input labels above satisfies \ref{ha:L1}--\ref{ha:L3}.
\end{lemma}
\begin{proof}
The definition gives \ref{ha:L1}, and insertability says exactly that
every endpoint in \ref{ha:L2} has distance at least $\delta_i$ from
$X_u$. We have already proved that $u\in L(B)$.
Every selected node is nonroot, so $|O(t)|\ge k$ by the cut bound
in its parent's induced graph. Moreover,
$|\operatorname{Bag}_t|\ge12C_3|O(t)|/k\ge12C_3>1$.
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\|_1<r\}\qquad(r>0).
\]
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|<w/(12\beta D)$, assign every small ball to its closest
chosen center, breaking ties consistently. The balls assigned to one
center have center diameter at most $6D$. Keep a resulting bag
precisely when it contains at least $6\beta D/\delta$ balls.
The discarded bags contain fewer than
$|\mathcal B|6\beta D/\delta<b/2$ balls. Each retained bag is
$\beta$-compact of type $(\delta,6D)$; the numerical threshold is
larger than $2$ because $D\ge\delta$ and $\beta>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_2<D$. Furthermore
\begin{equation}\label{hb:assignment-size}
\frac{|\mathrm{Bag}_t|}{m_t}
\ge\frac{w}{24\beta DN}.
\end{equation}
If $D=\delta$, the right side is $b/(24\beta N)$, at least
$s/(24\beta C)$ by the bound on $b$. If $D=2c_2$, it is at least
$s^{1+\epsilon}/(48\beta C)$ by
\eqref{hb:density} and~\eqref{hb:normalized-mass}.
In either case~\eqref{hb:smallness} makes it at least
$s^{1+2\epsilon}$. These bags are therefore assigned as asserted.
Their mass is at least $D|\mathcal B|/2\ge w/(24\beta)$;
\eqref{hb:numerator-mass} gives~\eqref{hb:one-mass}.
In both cases~\eqref{hb:density} gives $c_2\le c_1/s$ and therefore
$D\le2c_1/s$. Together with~\eqref{hb:radius-range}, this places all
radii, and the compact diameter $6D$, in $[sc_1,12c_1/s]$.
\end{proof}
\Needspace{18\baselineskip}
\subsubsection{Selecting separated scales}
\begin{proposition}[Geometric bag extraction]\label{prop:hierarchy-bags}
Let $T$ be a nonempty finite set of $\alpha$-bad nodes with positive boundary
sums, where $0<\alpha\le1$. Define
\[
\begin{aligned}
J&=1+\lceil\log_2(256/\alpha^2)\rceil,
&C_2(\alpha)&=128J^4,
&s&=\alpha/C_2(\alpha),\\
L&=2+\lceil\log_2(1/s)\rceil,
&H&=1+\lceil\log_2(24/(\lambda s^2))\rceil,
&C_1(\epsilon)&=1024\epsilon^{-2}.
\end{aligned}
\]
Suppose $\beta>1$, $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<p_0}\sigma_i
\le\sqrt{(p_0-1)\sum_i\sigma_i^2}
\le\frac\tau4.
\]
The sum is zero when \(p_0=1\), so this also covers arbitrarily small
\(am\). It follows that
\begin{equation}\label{hb:spectral-surviving-sum}
\sum_{i=p_0}^m\sigma_i\ge\frac{3\tau}{4}.
\end{equation}
Partition the integer interval \([p_0,m]\) into the nonempty blocks
\[
I_j=\{2^jp_0,\ldots,\min(2^{j+1}p_0-1,m)\},
\qquad 0\le j<L,
\]
where
\[
L=1+\left\lfloor\log_2\frac m{p_0}\right\rfloor
\le 5+\log_2(1/a).
\]
For the first index \(p=2^jp_0\) of a block, its cardinality is at
most \(p\). Cauchy--Schwarz therefore gives
\[
\sum_{i\in I_j}\sigma_i\le\sqrt{pT_p}.
\]
Summing this inequality and using
\eqref{hb:spectral-surviving-sum}, one of these first indices \(p\)
satisfies
\begin{equation}\label{hb:spectral-large-tail}
p\ge p_0>\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\|_1<r\}\), including
its center. A hollowed ball is the strict shell
\[
B_Q(x;a,b)=\{y\in Q:a<\|y-x\|_1<b\},
\qquad 0\le a<b.
\]
We call \(b-a\) its width. For numerical formulas an ordinary ball of
radius \(b\) has inner radius \(a=0\) and width \(b\); it remains an
ordinary ball, rather than a shell punctured at its center. A shell of
zero width is discarded.
\begin{lemma}[Length bound for disjoint hollowed balls]
\label{hc:length}
Let \(G=(V,E)\) be a finite \(k\)-edge-connected multigraph, where
\(k>0\), 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_H<t<b_H\), the set
\(S_{H,t}=\{v:\|X_v-x_H\|_1<t\}\) is nonempty and proper, by
\eqref{hc:witness}. Its edge boundary therefore has at least \(k\)
edges, with multiplicity. Integrating this finite step function gives
\begin{equation}
\label{hc:cut-integral}
k(b_H-a_H)
\le \int_{a_H}^{b_H}|E(S_{H,t},V\setminus S_{H,t})|\,dt
=\sum_{\{u,v\}\in E}|f_H(X_u)-f_H(X_v)|.
\end{equation}
Indeed, the contribution of an edge to the integral is exactly the
length of the interval of thresholds lying between its two endpoint
distances, intersected with \((a_H,b_H)\).
Fix an edge \(e=\{u,v\}\), put \(L_e=\|X_u-X_v\|_1\), and let
\(\gamma(s)=(1-s)X_u+sX_v\), \(0\le s\le1\). The segment lies in
the convex set \(Q\). Every \(g_H=f_H\circ\gamma\) is a continuous,
finitely piecewise affine function: each coordinate in its defining
norm is an absolute value of an affine function, and clamping adds
only finitely many breakpoints. The reverse triangle inequality and
the fact that clamping does not increase distances show that
\(g_H\) is \(L_e\)-Lipschitz.
Take a common finite subdivision \(0=s_0<\cdots<s_m=1\) on which all
the \(g_H\) are affine. If \(g_H\) is nonconstant on one of these
intervals, its value in the interval's interior lies strictly between
\(a_H\) and \(b_H\). The corresponding points of \(\gamma\) belong
to \(H\). Pairwise disjointness permits at most one such nonconstant
function on each interval. Hence
\begin{align*}
\sum_{H\in\mathcal Z}|g_H(1)-g_H(0)|
&\le \sum_{j=1}^m\sum_{H\in\mathcal Z}
|g_H(s_j)-g_H(s_{j-1})|\\
&\le \sum_{j=1}^m L_e(s_j-s_{j-1})=L_e.
\end{align*}
This also handles a segment lying along a shell boundary: its clamped
radial function is constant there. Summing
\eqref{hc:cut-integral} over \(H\) and then applying the last bound to
each edge proves \eqref{hc:length-bound}.
\end{proof}
\begin{proof}[Proof of Proposition~\ref{prop:hierarchy-compact}]
It suffices to prove the claim for each finite initial sequence
\(\mathcal F_1,\ldots,\mathcal F_q\). For this proof only, set
\(\Delta_{q+1}=0\). Each family is finite because its positive-radius
balls are disjoint and their centers are drawn from the finite set
\(\{X_v:v\in V\}\).
We first record the scale inequalities. Two disjoint balls of radius
\(\delta_i\), with centers \(z,z'\in Q\), satisfy
\(\|z-z'\|_1\ge2\delta_i\): otherwise their midpoint, which belongs
to \(Q\), would lie in both balls. A compact bag contains two such
balls. Consequently
\begin{equation}
\label{hc:scales}
2\delta_i\le\Delta_i,
\qquad
6\Delta_{i+1}\le\frac{\delta_i}{2},
\qquad
|D|\delta_i\ge \beta\Delta_i
\quad(D\in\mathcal F_i).
\end{equation}
\paragraph{The invariant and the order of processing.}
We construct a finite collection \(\mathcal Z\), initially empty,
and process the families in the order \(1,\ldots,q\).
During phase \(i\), call an original ball inserted from
\(\mathcal F_i\) \emph{fresh}. Every other live object is called
\emph{old}, including any shell produced by splitting an old object
during this phase. A fresh ball is kept intact until the phase ends.
Write \([s]_+=\max\{s,0\}\). Assign capacities
\begin{equation}
\label{hc:capacity}
p_i(H)=
\begin{cases}
\delta_i-6\Delta_{i+1},&H\text{ is fresh},\\
[w(H)-6\Delta_i]_+,&H\text{ is old},
\end{cases}
\qquad P_i(\mathcal Z)=\sum_{H\in\mathcal Z}p_i(H),
\end{equation}
where \(w(H)\) denotes width. All capacities are nonnegative and
at most the object's width. At every step we maintain:
\begin{enumerate}[label=(\roman*),leftmargin=*]
\item the live objects are pairwise disjoint;
\item their centers are embedded vertices, and every live object has
the two witnesses in \eqref{hc:witness};
\item
\begin{equation}
\label{hc:potential-invariant}
P_i(\mathcal Z)\ge
\frac14\sum_{D\text{ already processed}}|D|\delta(D),
\end{equation}
where \(\delta(D)\) is the radius of the balls of \(D\).
\end{enumerate}
These assertions hold initially. We verify them for each operation
and for each change of phase.
\paragraph{Processing a bag with an interior ball.}
For an unprocessed ball \(B_Q(z,\delta_i)\) and a live object \(H\)
with center \(x\) and numerical radii \(a,b\), say that the ball is
\emph{interior to \(H\)} if
\begin{equation}
\label{hc:interior}
a+\delta_i+\Delta_i\le\|z-x\|_1
\le b-\delta_i-\Delta_i.
\end{equation}
An interior ball is contained in \(H\), by the triangle inequality.
It is nonempty, so disjointness of \(\mathcal Z\) makes its containing
object unique. Moreover, this object cannot be fresh: an unprocessed
ball and a fresh ball belong to the same family, whose balls are
disjoint.
While some unprocessed bag has an interior ball, choose such a bag
\(D=\{B_Q(z_j,\delta_i):1\le j\le n\}\). Let \(H\) be the old
object containing an interior ball of \(D\), and set
\[
L=\min_j\|z_j-x\|_1,
\qquad R=\max_j\|z_j-x\|_1.
\]
The function \(z\mapsto\|z-x\|_1\) is 1-Lipschitz. The diameter
bound on the centers, applied first to the interior center and then
to the extremal pair, gives
\begin{equation}
\label{hc:radial-span}
a+\delta_i\le L\le R\le b-\delta_i,
\qquad R-L\le\Delta_i.
\end{equation}
Thus every ball of \(D\) lies in \(H\).
Replace \(H\) by the two old shells
\begin{equation}
\label{hc:split}
H_-=B_Q(x;a,L-\delta_i),
\qquad H_+=B_Q(x;R+\delta_i,b),
\end{equation}
discarding any zero-width shell, and insert all \(n\) balls of \(D\)
as fresh balls. Mark \(D\) processed.
Here are the geometric invariant checks. The shells in
\eqref{hc:split} are subsets of \(H\) and are disjoint from each other.
For \(y\in B_Q(z_j,\delta_i)\), strictness of the ordinary ball gives
\[
L-\delta_i<\|y-x\|_1<R+\delta_i.
\]
It therefore lies in neither shell. The inserted balls are mutually
disjoint by the family assumption; all replacements are subsets of
\(H\), so they also avoid every other live object.
For \(H_-\), an old inner witness remains an inner witness, and a
center achieving \(L\) is an outer witness. For \(H_+\), a center
achieving \(R\) is an inner witness, and an old outer witness remains
an outer witness. Every inserted ordinary ball has its own center
as inner witness and the center of another ball of \(D\) as outer
witness; their distance is at least \(2\delta_i\).
All centers of new objects are either \(x\) or a \(z_j\), hence are
embedded vertices. This proves (i) and (ii), and also proves that
fresh objects have not been altered.
For the potential calculation, write \(w=b-a\) and
\(t=[w-6\Delta_i]_+\), the old capacity being replaced. The new
ordinary balls have total capacity
\(n(\delta_i-6\Delta_{i+1})\ge n\delta_i/2\).
If \(t=0\), they alone pay the new requirement \(n\delta_i/4\),
and no previous capacity is lost. If \(t>0\), 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\|_1<a+\delta_i+\Delta_i,
\qquad
\|z-x\|_1>b-\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)-r<a_t\quad(t\in\mathcal M),\qquad
g_S(D)<b_S\quad(S\in\mathcal C),\qquad r<s.
\]
The point $(0,0,p_*)$ is outside this set, since membership would give a
feasible $D$ with every $f_t(D)<p_*$. The separation fact just proved
therefore supplies nonzero coefficients $(\lambda,y,\alpha)$ such that
\[
\lambda\cdot a+y\cdot b+\alpha s\geq\alpha p_*
\]
throughout the set. Each coefficient is nonnegative, because any one
coordinate of a point in the set can be increased arbitrarily.
Moreover $\alpha>0$. 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 $h<m$ and an $m\times h$ matrix has
orthonormal columns, complete its columns to an $m\times m$ orthogonal
matrix and append $m-h$ zero rows to $X$. Every edge inner product
and the denominator are preserved. More generally, any matrix with
$UU^{\mathsf T}\preceq I_m$ can be enlarged to the row semiorthogonal
matrix
\[
\bigl[\,U\quad (I_m-UU^{\mathsf T})^{1/2}\,\bigr]
\]
by appending $m$ zero rows to $X$, again preserving the ratio.
==== END The-strong-thin-tree-conjecture//source/sections/hierarchy_dual.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/hierarchy_proof.tex ====
\section{Proof of the polynomial hierarchy bound}
\label{app:hierarchy-proof}
We prove Theorem~\ref{thm:hierarchy-power} by the dual and geometric
method of Anari and Oveis Gharan~\cite{AOG}.
Lemma~\ref{lem:hierarchy-dual} reduces the matrix bound to an inequality
for binary embeddings. Proposition~\ref{prop:hierarchy-bags} captures
the relevant boundary sums in geometric families of balls;
Propositions~\ref{prop:hierarchy-compact} and~\ref{prop:hierarchy-assigned}
bound their total radii by graph length.
Section~\ref{hp:endpoint} then chooses the parameters.
In this appendix, $X$ denotes a vertex embedding, with columns $X_v$,
so $Xb_e=X_u-X_v$ for an oriented edge $e=uv$.
We index hierarchy nodes by $t$, write $V(t)$ for the corresponding
vertex set, and write $t^*$ for the parent of a nonroot node.
Thus $P(t)=\delta_G(V(t))$ and
$O(t)=E_G(V(t),V(t^*)\setminus V(t))$.
\input{sections/hierarchy_dual}
\input{sections/hierarchy_bags}
\input{sections/hierarchy_compact}
\input{sections/hierarchy_assigned}
\subsection{The parameter choice and the shortcut matrix}
\label{hp:endpoint}
\begin{proof}[Proof of Theorem~\ref{thm:hierarchy-power}]
All cut constraints in this proof are for nonempty proper subsets of
the vertex set. If the marked set $\mathcal M$ is empty, a sufficiently
small positive multiple of the identity is a shortcut, so suppose it
is nonempty. Write $q$ for the connectivity parameter of the
theorem. We may require $q$ to exceed an absolute cutoff, which will
be increased finitely many times below.
Fix an arbitrary binary embedding $X:V\to\{0,1\}^d$ and an arbitrary
row semiorthogonal matrix $U\in\mathbb R^{E\times d}$ as in
Lemma~\ref{lem:hierarchy-dual}, and suppose that
\[
\mathcal E=\sum_{e\in E}\|Xb_e\|_2^2>0.
\]
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_j<r_*\).
This happens after finitely many steps because
\(r_{i+1}\le r_i/2\). Every \(r_i\) is positive.
If \(j\ge1\), reading the halving inequality backwards gives
\[
r_i\ge2^{j-1-i}r_{j-1}
\ge2^{j-1-i}r_*
\qquad(0\le i<j).
\]
Consequently
\[
\sum_{i=0}^{j-1}r_i^{-1/16}
\le\frac{r_*^{-1/16}}{1-2^{-1/16}}.
\]
Set
\begin{equation}\label{eq:constant-C2}
C_{\mathrm{it}}=\exp\left(
\frac{15r_*^{-1/16}}{1-2^{-1/16}}
\right)\ge1.
\end{equation}
For every cut \(S\), multiplication of the step inequalities and
\eqref{eq:step-ratio-bound} gives
\[
\begin{aligned}
|\delta_{H_j}(S)|
&\le\frac{r_j}{r_0}
\prod_{i=0}^{j-1}(1+15r_i^{-1/16})
|\delta_{H_0}(S)|\\
&\le C_{\mathrm{it}}\frac{r_j}{r_0}|\delta_{H_0}(S)|.
\end{aligned}
\]
For \(j=0\) the same inequality holds with an empty product.
All these estimates concern the same sequence of subgraphs and
hold for every cut simultaneously.
Since \(r_j\ge1\), the final graph \(H_j\) is connected.
Any spanning tree \(T\) of \(H_j\) satisfies
\begin{equation}\label{eq:packing-thinness}
|\delta_T(S)|\le\frac{C_{\mathrm{it}}r_*}{r_0}|\delta_{H_0}(S)|
\qquad(\varnothing\ne S\subsetneq V).
\end{equation}
This includes \(r_0<r_*\): there are then zero rounds, and any
spanning tree works because \(C_{\mathrm{it}}r_*/r_0\ge1\).
Finally take \(H_0=G\). If \(k\ge2\), summing the cut lower bounds
over a partition into \(d\ge2\) parts shows that
\[
|E_G(\mathcal P)|\ge\frac{kd}{2}
\ge\lfloor k/2\rfloor(d-1).
\]
Theorem~\ref{thm:packing} supplies \(\lfloor k/2\rfloor\) packed
trees. If \(k=1\), connectedness supplies one tree.
Thus in all cases we may choose
\[
r_0=\max\{1,\lfloor k/2\rfloor\}\ge k/3.
\]
Substitution in \eqref{eq:packing-thinness} proves the theorem with
the universal constant
\[
C=3C_{\mathrm{it}}r_*.
\]
\end{proof}
==== END The-strong-thin-tree-conjecture//source/sections/iteration.tex ====
==== BEGIN The-strong-thin-tree-conjecture//source/sections/mss.tex ====
\section{The isotropic random-vector theorem}
\label{sec:mss}
This appendix proves the precise form of the Marcus--Spielman--Srivastava
theorem used in Section~\ref{sec:sparsification}. The proof proceeds
through expected characteristic polynomials, an elementary interlacing
argument, and a barrier estimate. In particular, the barrier estimate
below is proved directly from partial fractions; no representation
theorem for bivariate stable polynomials is required.
\begin{theorem}[Marcus--Spielman--Srivastava, {\cite[Theorem~1.4]{MSS}}]
\label{thm:mss}
Let $\epsilon>0$, 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_{k<d}a_kz^k$ has absolute value at most
$1+\max_k|a_k|$, as is seen by summing a geometric series when the
opposite strict inequality holds. Any convergent subsequence of
ordered root tuples factors the limiting polynomial. Its limiting
tuple must therefore be the unique ordered root tuple of that
polynomial. This proves continuity.
\end{proof}
\begin{lemma}[Elementary stability operations]
\label{lem:mss-stability}
The following assertions hold.
\begin{enumerate}
\item If $A_1,\ldots,A_m$ are Hermitian positive-semidefinite matrices
and $C$ is Hermitian, then
\[
\det\left(xI+C+\sum_{i=1}^m z_iA_i\right)
\]
is real stable in $x,z_1,\ldots,z_m$.
If $\sum_iA_i$ is positive definite, then
$\det(\sum_i z_iA_i)$ is also real stable.
\item If $p$ is real stable, then $(1-\partial_i)p$ is real stable.
\item A nonzero univariate polynomial obtained by setting all but one
variable of a real stable polynomial to real constants is real-rooted.
\end{enumerate}
\end{lemma}
\begin{proof}
For the first assertion, when all variables are in $\mathbb H$,
the imaginary part of the matrix is
\[
(\operatorname{Im}x)I+\sum_i(\operatorname{Im}z_i)A_i\succ0.
\]
Such a matrix is nonsingular: a nonzero kernel vector would have a
strictly positive imaginary part in its quadratic form, a
contradiction. The same argument applies to the second determinant
because $\sum_iA_i\succ0$. For real arguments the matrices are
Hermitian and their determinants are real; consequently the
polynomial coefficients are real.
For the second assertion, fix all arguments of $p$ in $\mathbb H$,
and regard $p$ as a polynomial in argument $i$ alone. This slice is
nonzero, and its roots $\alpha_k$ have nonpositive imaginary parts.
If it is nonconstant, factorization gives
\begin{equation}
\frac{\partial_i p}{p}
=\sum_k\frac1{z_i-\alpha_k},
\qquad
\operatorname{Im}\frac{\partial_i p}{p}<0.
\label{eq:mss-log-derivative-upper}
\end{equation}
If the slice is constant, the quotient is zero. In either case it
cannot equal $1$, so $(1-\partial_i)p$ is nonzero at this point.
The operation preserves real coefficients.
For the last assertion, replace each fixed real constant $a$ by
$a+\mathrm i\eta$, $\eta>0$. 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 k<d)
\]
for every polynomial in the collection.
\begin{lemma}[An elementary interlacing criterion]
\label{lem:mss-common-interlacing}
If every convex combination of finitely many monic degree-$d$
polynomials is real-rooted, they have a common interlacing.
Consequently, for any probability weights on this collection, some
polynomial of positive weight has largest root at most the largest
root of the weighted average.
\end{lemma}
\begin{proof}
First consider two members $p,q$ and
$r_t=(1-t)p+tq$, $0\leq t\leq1$.
Fix a real $x$ that is not a root of either $p$ or $q$, and let $N(t)$
count the roots of $r_t$ strictly below $x$, with multiplicity.
By ordered-root continuity, $N$ is locally constant wherever
$r_t(x)\ne0$. The affine function $r_t(x)$ vanishes at most once.
If it vanishes at $t_0\in(0,1)$, then
$b=q(x)-p(x)\ne0$.
We claim that $x$ is a simple root of $r_{t_0}$. Otherwise let its
multiplicity be $\ell\geq2$ and write
\[
r_{t_0}(x+w)=aw^\ell+O(w^{\ell+1}),\qquad a\ne0.
\]
For $h$ tending to zero with fixed sign $\sigma\in\{-1,1\}$,
\[
|h|^{-1}r_{t_0+h}\bigl(x+|h|^{1/\ell}z\bigr)
\longrightarrow az^\ell+\sigma b
\]
coefficientwise. Every polynomial on the left is real-rooted; hence
so is its nonzero limit by Lemma~\ref{lem:mss-polynomial-limits}.
For $\ell=2$, choose the sign so that $\sigma b/a>0$, 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<d$, one can choose
$x$ strictly between these roots and avoiding all endpoint roots.
Then $N(0)\leq k-1$ and $N(1)\geq k+1$, a contradiction.
Applying this reasoning to every pair gives
\[
\lambda_k(p_i)\leq\lambda_{k+1}(p_j)
\quad\hbox{for all }i,j\hbox{ and }k<d.
\]
Therefore $c_k=\max_i\lambda_k(p_i)$ is a common interlacing.
This proof includes repeated roots because all interlacing
inequalities are weak.
For the last assertion discard zero-weight polynomials and denote
the weighted average by $P$, with largest root $\rho$.
If $d=1$, $\rho$ is the weighted average of the individual roots,
which proves the assertion. Otherwise put $c=c_{d-1}$.
Every $p_i(c)\leq0$, since its first $d-1$ roots are at most $c$
and its last root is at least $c$. Thus $P(c)\leq0$, and, since
$P$ is monic, $\rho\geq c$.
For each $x>\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)<x$. Taking the minimum over the finite collection
and letting $x\downarrow\rho$ proves
$\min_i\lambda_d(p_i)\leq\rho$.
\end{proof}
\begin{lemma}[Selection from independent supports]
\label{lem:mss-selection}
For independent finitely supported vectors $v_1,\ldots,v_m$, some
outcome of positive probability has largest eigenvalue of
$\sum_i v_iv_i^*$ at most the largest root of
$\mu[\mathbb E v_1v_1^*,\ldots,\mathbb E v_mv_m^*]$.
\end{lemma}
\begin{proof}
Delete zero-probability support points. For a fixed choice of the
first $k$ vectors, consider the expected characteristic polynomial
over the remaining vectors. It is monic of degree $d$ and
real-rooted by Lemma~\ref{lem:mss-expectation}, treating the first
$k$ vectors as deterministic. Its children are the conditional
polynomials formed by fixing one further vector to each of its
possible values.
Every convex combination of these children is again real-rooted:
it is the expected characteristic polynomial for the same family,
with the next vector assigned the probabilities of that convex
combination. Lemma~\ref{lem:mss-common-interlacing} therefore lets
us choose a positive-probability child whose largest root does not
increase. Repeating for $k=0,\ldots,m-1$ yields a complete outcome.
The probability of that outcome is a product of finitely many
positive support probabilities, so is positive. At the leaf, the
polynomial is the characteristic polynomial of
$\sum_i v_iv_i^*$ and its largest root is the largest eigenvalue.
\end{proof}
\subsection{Barrier functions: a direct proof}
For a real stable polynomial $p$, let
\[
\operatorname{Ab}_p
=\{z\in\mathbb R^m:p(z+s)>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 \(m<r(n-1)\), this is smaller than \(r(d-1)\), contrary to the
partition hypothesis. Thus \(m=r(n-1)\); each of the \(r\) forests
has \(n-1\) edges and is a spanning tree.
\end{proof}
\begin{lemma}[Union and quotient properties]\label{lem:packing-parts}
Fix a positive integer \(q\) and a graph \(F\).
\begin{enumerate}[label=\textup{(\roman*)}]
\item If \(F[A]\) and \(F[B]\) are \(q\)-tree-packable and
\(A\cap B\ne\varnothing\), then \(F[A\cup B]\) is
\(q\)-tree-packable.
\item The inclusion-maximal \(q\)-tree-packable vertex sets form a
partition \(\mathcal P(F)\). If \(F\subseteq F'\), then
\(\mathcal P(F')\) coarsens \(\mathcal P(F)\).
\item If \(|\mathcal P(F)|>1\), then
\[
|E_F(\mathcal P(F))|<q(|\mathcal P(F)|-1).
\]
\end{enumerate}
\end{lemma}
\begin{proof}
For (i), enumerate the \(q\) trees on each of \(A\) and \(B\).
In the \(i\)-th tree on \(B\), contract all vertices of \(A\cap B\)
to a single vertex, discard loops, and choose a spanning tree of
the resulting connected multigraph. Its selected edges, together
with the \(i\)-th tree on \(A\), form a tree on \(A\cup B\).
Every selected edge has an endpoint outside \(A\), so no such edge
lies in any tree on \(A\). The selections in different colors
remain disjoint. This proves (i).
Every singleton is packable, and finiteness gives maximal sets.
Part (i) shows that two maximal sets cannot intersect unless equal.
Every previously packable set remains packable when edges are added,
which proves (ii).
For (iii), contract the parts and remove loops.
If its crossing count were at least \(q(d-1)\), where
\(d=|\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(0<u\leq1/16).
\]
For example, dividing by $u$ and using $\sqrt6<3$ bounds the left
ratio by $6(16^{-3}+16^{-7})<1/2$.
In particular $c=1/2-\tau>0$, 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 ====