\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{booktabs}
\geometry{margin=1in}

\title{Chain half of the loose conjecture: tree DP and where it gates}
\author{}
\date{}

\newtheorem*{prop}{Proposition}
\newtheorem*{lem}{Lemma}
\newtheorem*{conj}{Conjecture}
\newtheorem*{obs}{Observation}

\begin{document}
\maketitle

\section*{Recap}

The loose chain pigeonhole conjecture (k$\ge 2$ form,
\texttt{cut\_depth\_label.tex}) has two halves:

\paragraph{Per-tire half.}  For every cut tire $T$ with $\ge 2$
in/out spokes total, the joint projection $\pi(T) \subseteq
\{1,2,3\}^k$ is non-empty, $S_3$-closed, and contains a full $S_3$
orbit of size $6$.  Proven for spoke-only cut tires
($T'_{\mathrm{ann}}$ = simple cycle $C_n$, $n \ge 3$) via Prop 1.13
of \texttt{paper.tex}.

\paragraph{Chain half.}  Composing per-tire projections through the
cut-tire forest (\texttt{cut\_tire\_tree\_structure.tex}, rigorously
proved) yields $\mathcal{R}_i \ne \emptyset$ on each side $i$ of the
cut, with $\mathcal{R}_0 \cap \mathcal{R}_1 \ne \emptyset$ containing
a common $S_3$-orbit at the cut.

\section*{Tree DP formulation of the chain half}

The high-side cut tires of $G'_i$ form a forest (rigorously proved).
Process tires bottom-up:

\paragraph{(1) Leaves.}  A leaf cut tire $T_{d_{\max}}^{(f)}$ has
no children.  Its ``achievable projection'' onto its out spokes
(depth-$(d_{\max} - 1)$ direction) is
\[
   A(T) := \pi_{\mathrm{out}}(T),
\]
the projection of the per-tire projection $\pi(T)$ onto the out
spokes alone (in spokes are unconstrained at leaves).  By per-tire,
$|A(T)| \ge 6$ with full $S_3$-orbit.

\paragraph{(2) Internal nodes.}  For a cut tire $T_p = T_d^{(f)}$
with children $T_{c_1}, \dots, T_{c_r}$, define:
\[
   A(T_p) := \left\{\sigma_{\mathrm{out}}(T_p) : \exists\, \chi
      \text{ proper edge $3$-coloring of } T_p \text{ such that}
      \atop \forall\, j : \chi|_{\text{in-spokes corresponding to }
      T_{c_j}} \in A(T_{c_j})'\right\},
\]
where $A(T_{c_j})'$ is the ``transferred-back'' achievable
projection of child $T_{c_j}$ onto the corresponding parent in-spoke
positions.

The transfer back: an in spoke of $T_p$ at parent boundary vertex
$v$ corresponds to a depth-$(d+1)$ edge $e^{**}$ in $G'_i$.  This
$e^{**}$ is a face-boundary edge of $T_{c_j}$ (the unique child
whose face contains $v$ as a boundary endpoint of $e^{**}$).  So the
parent's in-spoke color at $v$ = child's face-boundary-edge color at
$e^{**}$.

For the projection $A(T_{c_j})$ to constrain parent's in spokes,
we'd need to know how child's spoke colors determine cycle edge
colors at specific positions.  In the spoke-only case (Prop 1.13),
each spoke color at $u$ equals the ``third color'' = the unique
color not appearing on the two cycle edges incident at $u$.  So
spoke colors determine the constraint set on cycle colors at each
vertex.

\paragraph{(3) Roots and the cut.}  $T_1^{(\cdot)}$ are roots.  Their
out spokes are the pendant edges $=$ the cut configuration $\sigma_i$.
The achievable cut configurations:
\[
   \mathcal{R}_i := \bigcup_{\text{roots } T_1^{(f)}} A(T_1^{(f)})
   \quad (\text{or restricted, depending on how root constraints compose}).
\]

\paragraph{(4) Cross-cut.}  $G'$ is properly $3$-edge-colourable iff
$\mathcal{R}_0 \cap \mathcal{R}_1 \ne \emptyset$ (under the
bijection between the two sides' cut edges).

\section*{What's preserved through the tree DP}

\subsection*{$S_3$-closure: preserved}

\begin{lem}[$S_3$-equivariance of tree DP]
If every $A(T_{c_j})$ is $S_3$-closed (under diagonal action on
colours), then $A(T_p)$ is $S_3$-closed.
\end{lem}

\begin{proof}
The proper-edge-coloring constraint at every vertex is preserved by
$S_3$ acting on colours uniformly.  Applying $\pi \in S_3$ to a
valid $\chi$ for $T_p$ gives another valid $\chi$.  Compatibility
with children: parent's in spokes are uniformly $\pi$-shifted, and
each child's $A(T_{c_j})$ is $S_3$-closed by hypothesis, so the
shifted parent in spokes still hit $A(T_{c_j})$.  Hence $\pi(\sigma)
\in A(T_p)$ for any $\sigma \in A(T_p)$.
\end{proof}

By induction from leaves (where $A = \pi$ is $S_3$-closed by
per-tire half), every $A(T)$ is $S_3$-closed.  This is the easy
half.

\subsection*{Non-emptiness: open, but constrained}

\begin{conj}[Non-emptiness preservation]
\label{conj:non-empty-prop}
If every $A(T_{c_j})$ contains a full $S_3$-orbit of size $6$, then
$A(T_p)$ also contains a full $S_3$-orbit.
\end{conj}

This is the genuine open piece of the chain half.

\paragraph{Why it isn't trivial.}  Two $S_3$-closed subsets of
$\{1, 2, 3\}^k$ can have empty intersection even if both contain
$S_3$-orbits.  Example: orbit of $(1, 2, 3)$ vs orbit of $(1, 1, 2)$
in $\{1,2,3\}^3$ are disjoint.

So the conjecture would require a structural reason that parent +
children combined always have at least one common assignment with
all 3 colours present (= a full $S_3$-orbit).

\paragraph{Why it's plausible.}  Empirical data from the partial-
tire-dual chain pigeonhole (\texttt{tire\_fiber\_step2.tex}):
$23/23$ pairwise compatibility tests succeeded, with the
intersections containing $S_3$-orbits and structured by ``rainbow''
or similar canonical orbits
(\texttt{orbit\_decomposition.tex}).  These results suggest a
structural reason for non-emptiness; we just don't have a clean
proof.

\paragraph{What would close the proof.}  Show that for spoke-only
cut tires, the per-tire projection $\pi(T)$ has the property:
\emph{for any specified colours on the in spokes that come from
$S_3$-orbits, there is a compatible parent coloring}.  Specifically:

\begin{conj}[Strong per-tire extendibility]
Let $T$ be a spoke-only cut tire with face boundary a simple cycle
$C_n$ ($n \ge 3$).  For any $\sigma_{\mathrm{in}} \in \{1, 2, 3\}^{n_{\mathrm{in}}}$
such that $\sigma_{\mathrm{in}}$ lies in a non-trivial $S_3$-orbit
(i.e.\ uses $\ge 2$ colours and is in $\pi(T)$'s $S_3$-symmetric
support), there exists a proper edge $3$-coloring $\chi$ of $T$ with
$\chi|_{\mathrm{in-spokes}} = \sigma_{\mathrm{in}}$ and
$\chi|_{\mathrm{out-spokes}}$ a non-trivial $S_3$-orbit on the
out-spoke side.
\end{conj}

If this conjecture holds, the chain DP preserves non-emptiness: for
each non-trivial parent $\sigma_{\mathrm{in}}$ (= child's face
boundary edges) provided by children, parent has a coloring with
out spokes in a non-trivial $S_3$-orbit, hence $A(T_p)$ contains a
full $S_3$-orbit.

\section*{Empirical next step}

Cut-tire tree DP empirical test:
\begin{enumerate}
  \item For each test graph (HM \#0 through \#5, dodecahedron,
        BuckyBall), build the cut tire forest on each side.
  \item For each leaf, compute $A(T_{\mathrm{leaf}})$.
  \item Bottom-up propagate $A(\cdot)$ to roots.
  \item Compare $\mathcal{R}_0 \cap \mathcal{R}_1$ at the cut.
\end{enumerate}

This is the analogue of \texttt{tire\_fiber\_step2.tex} for the
cut-tire setting.  If empirically $\mathcal{R}_0 \cap \mathcal{R}_1
\ne \emptyset$ universally, the chain half is on firm empirical
ground; the proof would still need Conjecture~\ref{conj:non-empty-prop}
or a structural shortcut.

\section*{Caveat discovered empirically: cut tires are not spoke-only}

A first-pass empirical test
(\texttt{experiments/chain\_dp\_test.py}) on the dodecahedron and
Holton--McKay \#0 revealed a structural complication: \emph{cut
tires are not in general spoke-only}.

\paragraph{What goes wrong.}  $H_d$ may have vertices of degree $3$
(all three incident edges have depth $d$).  In a cubic ambient
graph $G'_i$, this happens when three depth-$d$ edges meet at a
single vertex.  At such a vertex:
\begin{itemize}
\item There is no third edge available to be a spoke.
\item The face boundary walk of $H_d$ visits the vertex
      \emph{twice} (as a branch point).
\end{itemize}
For example, in the dodecahedron, a $6$-edge cut produces $H_1$
with $1$ face whose boundary has length $20$ but only $11$ distinct
vertices --- $9$ branch-point visits.

\paragraph{Consequence for Prop 1.13.}  The per-tire half (proven
via Prop 1.13) covers \emph{spoke-only} cut tires (face boundary =
simple cycle $C_n$, $n \ge 3$).  It does \emph{not} cover branched
cut tires.

\paragraph{Two ways forward.}
\begin{enumerate}
\item \emph{Restrict.}  Identify which graphs $G$ have the property
      that every cut tire of every $6$-edge cut is spoke-only.  This
      is a genuine \emph{a priori} restriction.
\item \emph{Generalise.}  Extend the per-tire half to branched cut
      tires.  Proper edge $3$-coloring on such a structure is
      well-defined and probably has a non-empty $S_3$-closed
      projection by similar arguments, but the explicit count
      $2^n + 2(-1)^n$ no longer applies.
\end{enumerate}

\paragraph{What this changes in the chain DP.}  The chain DP is
still well-formed: enumerate proper $3$-edge-colorings of each cut
tire (now allowing branches), project to out spokes, restrict via
children.  The per-tire half just needs the generalized form.

\paragraph{Second issue: out-spoke projection loses S$_3$ orbit.}
The per-tire half guarantees a full $S_3$ orbit on the \emph{joint}
in+out spoke projection $\pi(T)$.  After restricting to OUT spokes
only (which is what the parent uses), the projection $A(T)$ may
contain fewer than $6$ elements --- e.g.\ all out spokes might be
forced to a constant tuple by some structural symmetry, giving
$|A(T)| = 3$ (= $\{(0,0,\dots), (1,1,\dots), (2,2,\dots)\}$).
Initial empirical runs on the dodecahedron and HM \#0 see exactly
this happen at $\sim 20\%$ of cut tires.  This is \emph{not} a bug
in the per-tire half; it is a genuine limitation of the OUT-only
projection.

The correct chain DP formulation should track the joint (in + out)
projection, not just OUT.  This is the analogue of
\texttt{tire\_fiber\_step2.tex}'s joint-support tracking.

\paragraph{Third issue: heuristic parent-finding.}  The current
\texttt{cut\_tire\_tree.find\_parent\_face} uses a vertex-overlap
heuristic (smallest face among overlapping candidates).  Per the
high-side proposition (\texttt{cut\_tire\_tree\_structure.tex}),
the geometrically-correct parent is unique, but the empirical
script does not enforce this --- it picks by smallest-face
heuristic, which can mis-attribute children to wrong parents.
For a rigorous empirical test, parent assignment should use the
planar embedding's face-in-face containment, not vertex overlap.

\paragraph{Fourth issue: when $H_d$ is a tree, the high-side
forest is empty.}  The level-set lemma forces each face of $H_d$
to be entirely low-side or entirely high-side.  If $H_d$ has no
cycles (= tree/forest), it has a single face containing all
non-$H_d$ edges of $G'_i$, and that face must be one or the other
(low or high), not both.  In the small-side regime (e.g.\
dodecahedron $6$-edge cut with $|S_0| = 4$, side $0$), the BFS
only reaches depth $1$ and $H_1$ is a tree (5 edges, 6 vertices,
$1$ face containing the $6$ pendants).  This single face is
low-side --- so the high-side cut tire forest of $G'_0$ is
\emph{empty}.

\medskip

In this case, the framework gives no high-side cut tires on
$G'_0$, hence $\mathcal{R}_0 = \emptyset$ by the framework's
projection to root out-spokes.  But $G$ is $3$-edge-colorable
(dodecahedron is Hamiltonian, hence Tait colorable), so the
\emph{true} $\mathcal{R}_0$ is non-empty (= the cut-projection of
$G$'s $60$ colorings, giving $|R_{\mathrm{ground}}| = 36$).

\medskip

So the framework's high-side cut tire forest \emph{loses coverage}
for thin (small-$|S_i|$) cuts.  The low-side face also carries
coloring information --- it contains the pendants and the
depth-$1$ subgraph --- but it isn't included as a "cut tire" in
the high-side formulation.

This isn't strictly a bug in any proof so far; it's a coverage
gap in the framework's scope.  To handle these cases, one of:
\begin{itemize}
\item Restrict the conjecture to cuts where both sides have
      ``deep'' BFS (e.g.\ $\min(|S_0|, |S_1|) \ge k$ for some
      $k$ ensuring high-side faces exist).
\item Extend the framework to include the low-side face as a
      special ``boundary cut tire'' connecting pendants to the
      $H_1$ structure.
\end{itemize}

\section*{Net status of the loose conjecture}

\begin{center}
\small
\begin{tabular}{lll}
\toprule
component & status & note \\
\midrule
Per-tire half (spoke-only $n \ge 3$) & proven & Prop 1.13 \\
Per-tire half (branched) & open & non-cycle face boundaries \\
Tree structure (forest, high-side) & proven & \texttt{cut\_tire\_tree\_structure.tex} \\
Chain DP $S_3$-equivariance & proven & this note, Lemma \\
Joint projection DP & implemented, buggy & \texttt{chain\_dp\_joint.py} \\
Coverage when $H_d$ is a tree & gap & low-side face carries info \\
Chain DP non-emptiness preservation & open & Conj.\ \ref{conj:non-empty-prop} \\
Bottom-line $\mathcal{R}_0 \cap \mathcal{R}_1 \ne \emptyset$ & open & $G$-colorability gives it \\
\bottomrule
\end{tabular}
\end{center}

The chain half reduces to multiple structural claims:
\begin{itemize}
\item per-tire half for branched cut tires;
\item joint-support DP (track $\pi(T)$, not just OUT projection);
\item handling cases where $H_d$ is a tree (no high-side faces);
\item non-emptiness preservation (Conj.\ \ref{conj:non-empty-prop}
      or Strong per-tire extendibility).
\end{itemize}
The $S_3$-equivariance and forest structure (with high-side
restriction) are in hand.  The full chain half is genuinely open
and the framework has coverage gaps not previously identified.

\paragraph{Empirical baseline for ground-truth comparison.}
\texttt{chain\_dp\_joint.py} compares the chain DP output
against a brute-force enumeration of $G'_i$'s proper $3$-edge
colorings projected to the cut.  On the dodecahedron, ground
truth shows $|R_{\mathrm{ground}}| \in \{36, 42, 48\}$ across
the first few cuts, but DP outputs $0$ for any side where
$H_1$ is a tree (= no high-side cut tires).  This isn't a DP
bug per se --- it's the framework lacking coverage.

\paragraph{Path forward.}  The cleanest next step is probably
the \emph{boundary cut tire} extension: define an additional
``cut tire'' $T_0$ that represents the low-side face of $H_1$
+ its incident pendants.  $T_0$'s spokes are the cut edges;
its cycle structure is the boundary of the low-side face.
The high-side forest then sits ``inside'' $T_0$, and the chain
DP runs from leaves up through $T_0$ to the cut.  This recovers
the missing coverage and gives a more uniform formulation.

\end{document}
