\documentclass[11pt,a4paper,reqno]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs} \usepackage[a4paper,left=2.5cm,right=2.5cm,top=2.8cm,bottom=2.8cm]{geometry} \usepackage{microtype,setspace,enumitem,booktabs,array,longtable} \usepackage{tikz} \usetikzlibrary{arrows.meta} \usepackage[hidelinks]{hyperref} \setstretch{1.13} \setlist[enumerate]{label=\textup{(\roman*)},leftmargin=*} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\TP}{\operatorname{TP}} \newcommand{\NN}{\mathbb Z_{\geq0}} \newcommand{\ee}{\mathbf e} \newcommand{\one}{\mathbf1} \newcommand{\dd}{\mathsf D} \newcommand{\cc}{\mathsf C} \DeclareMathOperator{\diag}{diag} \title[A counterexample to the subtraction-free conjecture]{A counterexample to the subtraction-free conjecture\protect\\ for bounded ratios of minors} \author{Qiyue Tang} \address{Zhili College, Tsinghua University, Beijing 100084, China} \email{tangqy24@mails.tsinghua.edu.cn} \date{November 10, 2026} \subjclass[2020]{Primary 15B48; Secondary 15A15, 05C70, 52B20} \keywords{Totally positive matrix, minor inequality, subtraction-free polynomial, planar network, Newton polytope} \begin{document} \raggedbottom \begin{abstract} We disprove the subtraction-free conjecture of Boocher and Froehle for bounded ratios of minors of totally positive matrices. We construct products $P,M,Q$ of ordinary minors of a matrix of order $3207$ such that $0

b$. For equally sized subsets $I,J\subseteq[1,n]$, let $A[I,J]$ have its rows and columns in increasing order, and write \[ \Delta_{I,J}(A)=\det A[I,J],\qquad \Delta_{\varnothing,\varnothing}(A)=1. \] A minor is \emph{principal} when $I=J$. We consider ratios \begin{equation}\label{eq:generalratio} R(A)=\frac{\prod_{\nu=1}^{r}\Delta_{I_\nu,J_\nu}(A)} {\prod_{\nu=1}^{s}\Delta_{K_\nu,L_\nu}(A)}, \end{equation} with repetitions allowed. Such a ratio is \emph{bounded} if there is a constant $C>0$ such that $R(A)\leq C$ for every $A\in\TP_n$. Describing these ratios is a multiplicative form of the problem of classifying determinantal inequalities. The coordinate methods for this problem originate in the structural theory of total positivity. The factorization theorem of Loewner and Whitney \cite{Loewner,Whitney} expresses every invertible totally nonnegative matrix as a product of a positive diagonal matrix and nonnegative elementary bidiagonal factors. Their parameters also have a planar-network interpretation. The determinant formula for disjoint paths has its origins in Karlin and McGregor \cite{KM} and Lindstr\"om \cite{Lindstrom}, and was developed in enumerative form by Gessel and Viennot \cite{GV}. It expresses each minor as a sum of path weights with nonnegative coefficients. Fomin and Zelevinsky \cite{FZ} organized these factorizations, positivity tests and chamber-minor coordinates in a common framework. These coordinates make it possible to compare polynomial coefficients as well as values on the positive locus. Fallat and Johnson \cite{FJ} posed the bounded-ratio classification problem in their 2000 account of determinantal inequalities. Fallat, Gekhtman and Johnson \cite{FGJ} then studied products of principal minors. They obtained a complete classification through order five and a characterization of ratios involving two principal minors in each product in arbitrary order. Their arguments use bidiagonal factorizations, index-balance conditions and operations preserving inequalities. In \cite[\S6]{FGJ} they proposed two conclusions suggested by these classifications: every bounded ratio should be bounded by $1$, and the difference between its denominator and numerator should have nonnegative coefficients in the bidiagonal parameters. Skandera \cite[Theorem~4.2]{Skandera} extended the two-factor classification to ordinary minors, using planar paths and the order of the row and column indices. His Problem~5.3 asks for the corresponding classification with more factors. Boocher and Froehle \cite{BF} subsequently factored every bounded two-factor ratio into elementary bounded ratios arising from short Pl\"ucker relations. They also formulated the subtraction-free conjecture for arbitrary products of ordinary minors in a fixed standard network. Precisely, let $\mathbf t$ be the independent positive edge parameters of that network, and let $p(\mathbf t),q(\mathbf t)$ be the numerator and denominator of \eqref{eq:generalratio} after path expansion. The coefficient condition in \cite[Conjecture~37]{BF} is \begin{equation}\label{eq:BFconjecture} R\text{ is bounded on }\TP_n \quad\Longleftrightarrow\quad q-p\in\mathbb R_{\geq0}[\mathbf t], \end{equation} where $\mathbb R_{\geq0}[\mathbf t]$ denotes the polynomials with nonnegative coefficients. The reverse implication gives the bound $R\leq1$. The proposed forward implication is the subject of this paper. The factorization problem has since been resolved negatively. Soskin and Gekhtman \cite{SG}, in work first circulated in 2022 and published in 2025, proved that bounded exponent vectors form a polyhedral cone and produced ratios of minors of order-four matrices outside the cone generated by primitive ratios. Their counterexamples satisfy the subtraction-free condition. Thus the failure of primitive factorization left the coefficient condition as a separate problem. Gekhtman, Greenberg and Soskin \cite{GGS} studied the corresponding cones for full-rank cluster algebras of finite type. They identified their extreme rays with the $u$-variables and proved that every bounded cluster-variable ratio is bounded by $1$. Their Theorem~1.11 establishes subtraction-freeness in face weights and primitive factorization for Pl\"ucker ratios on $\mathrm{Gr}(2,n)$, $\mathrm{Gr}(3,6)$, $\mathrm{Gr}(3,7)$ and $\mathrm{Gr}(3,8)$. The same paper gives a type-$C_2$ counterexample to the analogous condition that a denominator-minus-numerator can be expressed as a polynomial with nonnegative coefficients in the full set of cluster variables \cite[Example~3.20]{GGS}. Its ordinary-minor statement appears separately as Conjecture~1.4. The construction below realizes a coefficient obstruction using ordinary minors on the entire matrix locus $\TP_{3207}$ and the standard bidiagonal coordinates. Bounded ratios also admit a broader convex-geometric description. Huang, Huh, Soskin and Wang \cite{HHSW} identified the bounded-ratio cone of Lorentzian matrices with a dual cut cone. Baldi and Kummer \cite[Theorem~1.1]{BK} proved that the bounded-ratio cone of a semialgebraic subset of a positive orthant is dual to its tropicalization. Such descriptions govern growth of monomials. The coefficient question additionally depends on the support of the denominator polynomial, namely the set of exponent vectors of its nonzero monomials. Our main result is the following. \begin{theorem}\label{thm:main} There are products $P,M$ of ordinary minors and six ordinary minors $Q_1,\ldots,Q_6$ of a matrix of order $N=3207$ such that, with $Q=Q_1\cdots Q_6$, \begin{equation}\label{eq:mainbound} 0<\frac{P(A)}{M(A)Q(A)}\leq\frac1{64}\qquad(A\in\TP_N). \end{equation} In the standard bidiagonal network parameters, the polynomial $MQ-P$ has a coefficient equal to $-1$. \end{theorem} Theorem~\ref{thm:main} disproves the forward implication in \eqref{eq:BFconjecture}. The products $P,M$ are defined by the chamber-exponent formula in Section~\ref{sec:explicit}, and the six factors of $Q$ are listed in Table~\ref{tab:Q}. The proof starts with six matching polynomials whose product has an integral midpoint hole in its support. Two disjoint triangles prevent a decomposition of this midpoint into six matching vectors. A reference matching and adjacent boundary bridges convert the matchings to directed paths. We embed the resulting network into the standard matrix network while preserving vertex capacities and integral edge flows. The unweighted edges of the latter network form a forest, which makes the weighted-edge exponents determine the complete flow and preserves the missing monomial. Chamber-minor inversion and six applications of the arithmetic--geometric mean inequality then give the ratio in Theorem~\ref{thm:main}. \section{Standard coordinates and chamber minors}\label{sec:chambers} For $1\leq i0 \quad(a,k\geq1,\ a+k-1\leq n). \] Set $F_{a,0}(V)=1$ for $1\leq a\leq n+1$. Triangularity gives $F_{a,k}(V)=1$ when $a+k-1=n$. Define positive numbers \[ t_{s,i}=\frac{F_{i,s}(V)F_{i+2,s-1}(V)} {F_{i+1,s}(V)F_{i+1,s-1}(V)}. \] Lemma~\ref{lem:chamber}, with all diagonal parameters equal to $1$, gives the same ratios for $U(t)$. Starting with $F_{a,0}=1$, recover all $F_{i,s}$ in the order $s=1,\ldots,n-1$ and $i=n-s,\ldots,1$ from \[ F_{i,s}=t_{s,i}\frac{F_{i+1,s}F_{i+1,s-1}}{F_{i+2,s-1}}, \qquad F_{n-s+1,s}=1. \] Thus $V$ and $U(t)$ have the same $F$-values. These values determine $V$. Process columns $j=n,n-1,\ldots,2$ and, within column $j$, rows $a=j-1,j-2,\ldots,1$. Put $k=n-j+1$ and expand $F_{a,k}(V)$ along its first column, of index $j$. The coefficient of $V_{a,j}$ is $F_{a+1,k-1}(V)>0$. Every other term uses entries in columns greater than $j$ and entries of column $j$ in rows greater than $a$. Those entries have already been determined, or are fixed by unit triangularity. Hence $V_{a,j}$ is determined. It follows that $V=U(t)$, and the displayed ratios give uniqueness of the parameters. Now take $A\in\TP_n$. Nonzero leading minors give unit triangular Gaussian elimination, so $A=LDU$ with $d_r=\dd_r(A)/\dd_{r-1}(A)>0$. Indeed, the first step factors off $A_{11}>0$ and leaves its Schur complement, whose leading minor of order $r$ is $\dd_{r+1}(A)/A_{11}>0$; induction proves the factorization and the diagonal formula. For $r=a+k-1$, Cauchy--Binet and triangularity give \[ \cc_{a,k}(A)=(d_1\cdots d_r)F_{a,k}(U). \] All these $F$-values are positive, so the preceding reconstruction gives the required positive upper parameters. Applying the same argument to $A^{\mathsf T}=U^{\mathsf T}DL^{\mathsf T}$ gives the positive parameters of $L^{\mathsf T}$. Uniqueness follows from uniqueness of unit triangular Gaussian elimination and of the two reconstructions. Conversely, take positive parameters. The path formula makes every minor of $U(t)$ and $U(\ell)$ nonnegative. For $1\leq kr$, the path from $r'$ moves first while the other path is still on rail $rj_r$. Thus the paths are disjoint and $\Delta_{[1,k],J}(U)>0$. For $k=n$ the determinant is $1$. In the Cauchy--Binet expansion of $\Delta_{I,J}(LDU)$, all summands are nonnegative, and the summand with intermediate set $[1,k]$ is \[ \Delta_{[1,k],I}\bigl(U(\ell)\bigr) (d_1\cdots d_k)\Delta_{[1,k],J}\bigl(U(t)\bigr)>0. \] Therefore $LDU\in\TP_n$. \end{proof} \begin{lemma}\label{lem:holecriterion} Let $Q=\prod_{j=1}^{r}Q_j$ be a product of ordinary minors in the standard chart. Suppose each $Q_j$ contains two distinct path monomials $B_j,T_j$, and suppose \begin{equation}\label{eq:holehyp} u=\frac12\sum_{j=1}^{r}\bigl(\nu(B_j)+\nu(T_j)\bigr)\in\NN^{n^2}, \qquad [\mathbf t^u]Q=0. \end{equation} Assume that every lower-parameter coordinate of $u$ is zero. Then there are products $P,M$ of the chamber minors in \eqref{eq:chamberdef} such that \[ \frac{P}{M}=\mathbf t^u,\qquad 0<\frac{P(A)}{M(A)Q(A)}\leq2^{-r}\quad(A\in\TP_n), \] and $[\mathbf t^{\nu(P)}](MQ-P)=-1$. \end{lemma} \begin{proof} Apply \eqref{eq:inverse} to the monomial $\mathbf t^u$, collect exponents of equal chamber minors, and place positive exponents in $P$ and negative exponents in $M$. These are finite products of ordinary minors, and $P=M\mathbf t^u$ as an identity in the chart. For positive parameters, the path expansion and the arithmetic--geometric mean inequality give \[ Q\geq\prod_{j=1}^{r}(B_j+T_j) \geq2^r\sqrt{\prod_{j=1}^{r}B_jT_j} =2^r\mathbf t^u. \] This proves the bound on the whole of $\TP_n$. Finally $M$ is a coefficient-one monomial, so \[ [\mathbf t^{\nu(P)}](MQ-P)=[\mathbf t^u]Q-1=-1.\qedhere \] \end{proof} \section{A matching hole from two odd cycles}\label{sec:flower} Sector subscripts on the vertices and edges are taken modulo $12$ throughout the construction; boundary labels lie in $[0,23]$. Form a bipartite graph in a disk with internal vertices \[ V_i,W_i,X_i,Y_i\quad(0\leq i<12) \] and boundary vertices $b_0,\ldots,b_{23}$ in cyclic order. Its internal edges are \begin{equation}\label{eq:floweredges} C_i=V_iV_{i+1},\quad R_i=V_iW_i,\quad A_i=W_iX_i,\quad B_i=X_iY_i,\quad D_i=Y_iW_{i+1}. \end{equation} The boundary edges are $\xi_i=X_ib_{2i}$ and $\eta_i=Y_ib_{2i+1}$. Embed the $V_i$ on an inner circle, the $W_i$ radially outside them, and the paths $W_iX_iY_iW_{i+1}$ in successive outer sectors. This describes a planar graph consisting of a central twelve-cycle and twelve surrounding hexagons. It has $48$ internal vertices and $84$ edges. Color $V_i,X_i$ white for even $i$, and $W_i,Y_i$ white for odd $i$; the other vertices have the opposite color, extended to the boundary leaves. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=.86] \foreach \i in {0,...,11}{ \pgfmathtruncatemacro{\j}{mod(\i+1,12)} \coordinate (V\i) at (90-30*\i:1.28); \coordinate (W\i) at (90-30*\i:2.05); \coordinate (X\i) at (80-30*\i:2.7); \coordinate (Y\i) at (70-30*\i:2.7); \coordinate (PX\i) at (80-30*\i:3.12); \coordinate (PY\i) at (70-30*\i:3.12); } \foreach \i in {0,...,11}{ \pgfmathtruncatemacro{\j}{mod(\i+1,12)} \draw (V\i)--(V\j) (V\i)--(W\i) (W\i)--(X\i)--(Y\i)--(W\j); \draw (X\i)--(PX\i) (Y\i)--(PY\i); \pgfmathtruncatemacro{\parity}{mod(\i,2)} \ifnum\parity=0 \foreach \v in {V,X,PY}{\filldraw[fill=white] (\v\i) circle (1.5pt);} \foreach \v in {W,Y,PX}{\fill (\v\i) circle (1.5pt);} \else \foreach \v in {W,Y,PX}{\filldraw[fill=white] (\v\i) circle (1.5pt);} \foreach \v in {V,X,PY}{\fill (\v\i) circle (1.5pt);} \fi \node[font=\scriptsize] at (90-30*\i:.92) {$\i$}; } \node[font=\small] at (0,-3.65) {central vertices $V_0,\ldots,V_{11}$}; \end{tikzpicture} \caption{The common graph for the six matching polynomials. The boundary leaves are ordered $b_0,b_1,\ldots,b_{23}$ around the outer circle. Filled and open vertices are black and white, respectively.}\label{fig:flower} \end{figure} A matching is required to cover every internal vertex exactly once; boundary vertices may be covered or uncovered. For two distinct even sectors $a,b$, prescribe boundary bits $00$ at sectors $a,b$, bits $11$ at their predecessors, and bits $10$ at all other sectors. The two bits at sector $i$ record whether $\xi_i,\eta_i$ are selected. For any edge $e$ let $\ee_e$ be its unit coordinate in $\mathbb Z^{84}$. For even $i$, set \begin{equation}\label{eq:directions} \alpha_i=\ee_{A_i}+\ee_{D_i}+\ee_{C_i} -\ee_{B_i}-\ee_{R_i}-\ee_{R_{i+1}}, \qquad \zeta=\sum_{i\text{ odd}}\ee_{C_i}-\sum_{i\text{ even}}\ee_{C_i}. \end{equation} Let $\beta_{ab}$ be the incidence vector of the following matching, where $S=\{a,b\}$: \begin{equation}\label{eq:baseline} \begin{split} &\bigcup_{i\in S}\{B_i,R_i,R_{i+1},\xi_{i-1},\eta_{i-1}\}\\ &\quad\cup\bigcup_{\substack{i\text{ even}\\ i\notin S}} \{D_{i-1},D_i,\xi_{i-1},\xi_i\} \quad\cup\{C_i:i\text{ even},\ i\notin S\}. \end{split} \end{equation} This set has $30$ edges. \begin{lemma}\label{lem:fivestates} For the prescribed boundary bits, the matching incidence vectors are exactly \begin{equation}\label{eq:fivestates} \beta_{ab},\quad \beta_{ab}+\alpha_a,\quad \beta_{ab}+\alpha_b,\quad \beta_{ab}+\alpha_a+\alpha_b,\quad \beta_{ab}+\alpha_a+\alpha_b+\zeta. \end{equation} \end{lemma} \begin{proof} For every unselected even sector $i$, sectors $i-1$ and $i$ have boundary bits $10$. Their $X$-vertices are matched to boundary leaves, which forces $D_{i-1}$ and $D_i$. For a selected even sector $i$, the preceding sector has bits $11$. After its occupied leaves are removed, the remaining outer path $W_iX_iY_iW_{i+1}$ has two possible matchings: use its middle edge $B_i$ and the radial edges $R_i,R_{i+1}$, or use its outside edges $A_i,D_i$. The first choice covers the central pair $V_i,V_{i+1}$, and the second leaves that pair to the central cycle. The selected pairs are disjoint. Removing any nonempty collection of them leaves paths with even numbers of vertices, uniquely matched by the remaining even-indexed $C$-edges. If neither pair is removed, the whole twelve-cycle remains and has two alternating perfect matchings. The four outer choices therefore give five matchings. Replacing the first choice at $i$ by the second contributes $\alpha_i$; exchanging the two central matchings contributes $\zeta$. \end{proof} Use the ordered list of six pairs \begin{equation}\label{eq:pairs} \mathcal E=((0,2),(2,4),(0,4),(6,8),(8,10),(6,10)). \end{equation} They form two disjoint triangles on the six even sectors. For each pair choose the first and last vectors in \eqref{eq:fivestates} as its bottom and top endpoints. Their aggregate midpoint is \begin{equation}\label{eq:matchingmid} m=\sum_{(a,b)\in\mathcal E}\beta_{ab} +\sum_{i\text{ even}}\alpha_i+3\zeta. \end{equation} Every even sector occurs in two pairs, so twice this vector is the sum of the twelve endpoint incidence vectors. In particular, $m$ is integral and nonnegative. \begin{lemma}\label{lem:matchinghole} The vector $m$ is not a sum of six matching incidence vectors, one with each of the prescribed boundary conditions. \end{lemma} \begin{proof} The six $\alpha_i$ and $\zeta$ are linearly independent: their coefficients are recovered first from the six coordinates $A_i$ and then from $C_1$. A sum equal to \eqref{eq:matchingmid} would therefore use the last state of \eqref{eq:fivestates} in exactly three factors. Each such state contributes both incident $\alpha$-directions. All contributions to the $\alpha_i$ coefficients are nonnegative, and each total must be $1$. The three selected pairs would therefore have to be pairwise disjoint. Each triangle contains at most one edge in such a matching, so their union contains at most two. \end{proof} \section{From matchings to a network with separated terminals}\label{sec:bridges} \subsection{Acyclic orientation} Choose the reference matching \begin{equation}\label{eq:reference} \begin{split} M_0=\{&C_2,C_4,C_6,C_8,C_{11},R_1,R_{10},A_0,D_1,B_2,\\ &A_3,D_3,B_4,A_5,D_5,B_6,A_7,D_7,B_8,A_9,B_{10},A_{11},\\ &\eta_0,\xi_1,\eta_9,\eta_{11}\}. \end{split} \end{equation} It is the unique matching occupying exactly the boundary vertices $b_1,b_2,b_{19},b_{23}$. Remove these four occupied leaf edges and their endpoints and forbid all other leaf edges. The following forced deletions exhaust the remaining internal vertices; in each entry the vertex on the left has only the indicated available matching edge: \begin{equation}\label{eq:forced} \begin{gathered} (W_1,R_1),(X_0,A_0),(V_0,C_{11}),(X_9,A_9),(X_{11},A_{11}),(Y_1,D_1),\\ (V_2,C_2),(X_2,B_2),(W_3,A_3),(Y_3,D_3),(V_4,C_4),(X_4,B_4),\\ (W_5,A_5),(Y_5,D_5),(V_6,C_6),(X_6,B_6),(W_7,A_7),(Y_7,D_7),\\ (V_8,C_8),(V_{10},R_{10}),(X_8,B_8),(X_{10},B_{10}). \end{gathered} \end{equation} Orient the edges of $M_0$ from white to black and the other edges from black to white. A directed cycle would alternate between reference and nonreference edges; flipping it would contradict the uniqueness just proved. Thus the orientation is acyclic. Its boundary source labels are \begin{equation}\label{eq:I0} I_0=\{0,1,2,3,4,7,8,11,12,15,16,20\}. \end{equation} Every internal vertex has both an incoming and an outgoing arc. For a matching $M$, define $J(M)\subseteq[0,23]$ to consist of the labels $j$ for which $b_j$ is white with its leaf edge selected, or black with its leaf edge unselected. There are $24$ internal vertices and $12$ boundary vertices of each color. Since every internal vertex is matched, the numbers of occupied boundary vertices of the two colors are equal; hence $|J(M)|=12$. At an internal white vertex, the reference edge is the unique outgoing edge; at an internal black vertex it is the unique incoming edge. The symmetric difference $M\mathbin\triangle M_0$ therefore has degree zero or two at each internal vertex, and its nontrivial components follow the orientation. Acyclicity makes them paths. Their source labels are $I_0\setminus J(M)$ and their sink labels are $J(M)\setminus I_0$. Conversely, each directed path uses one reference and one nonreference edge at every internal vertex. Flipping its edges replaces one selected incident edge by one selected incident edge. This recovers a matching, and the two operations are inverse. On all $84$ coordinates the correspondence is \begin{equation}\label{eq:affinematching} f_e=\begin{cases}\chi_M(e),&e\notin M_0,\\1-\chi_M(e),&e\in M_0,\end{cases} \end{equation} where $\chi_M(e)\in\{0,1\}$ records whether $e\in M$. This is an invertible integral affine map. For any of the directed graphs below, a \emph{flow} is a nonnegative real vector on its arcs whose total incoming and outgoing values agree at each internal vertex. The flow of a path family records its arc use and has total incoming value at most $1$ at every internal vertex. When the boundary source set is $I$ and $J\subseteq[0,23]$ has size $12$, a \emph{path family for $J$} uses exactly the sources $I\setminus J$ and sinks $J\setminus I$. \subsection{Boundary bridges} Suppose that the current boundary labels have source set $I$. Choose $1\leq j\leq23$ with $j\in I$ and $p=j-1\notin I$. Replace the ports at labels $p,j$ by new ports with the same boundary labels, and add \begin{equation}\label{eq:bridge} \text{new }p\longrightarrow\text{old }p \longrightarrow\text{old }j\longrightarrow\text{new }j. \end{equation} The middle arc is called the bridge. Draw these arcs in a thin outer collar between the adjacent ports. The new source set is $I'=(I\setminus\{j\})\cup\{p\}$, and the embedding remains planar. Always choose the least possible $j$. If no such $j$ exists, membership in $I$ is closed under predecessors, so the $12$-element set $I$ equals $[0,11]$. Each step decreases the sum of its labels by one. The initial sum is $99$, and the minimum is $0+\cdots+11=66$; thus the procedure terminates after exactly $33$ steps. Each step adds two vertices and three arcs, giving a graph $G$ with $138$ vertices and $183$ arcs. Assign $\phi(b_j)=j$ and assign the internal values in Table~\ref{tab:potential}. The edge definitions and \eqref{eq:reference} give $\phi(\operatorname{head}e)\geq\phi(\operatorname{tail}e)$ on every original arc. Give each new port its boundary-label value. The two short arcs in \eqref{eq:bridge} have constant potential and the middle arc increases it by one, excluding a cycle containing a bridge. After all middle bridges are deleted, the new arcs only extend the boundary ports of the original acyclic graph by chains. Thus every stage is acyclic. \begin{table}[ht] \centering\small \begin{tabular}{c*{12}{r}}\toprule $i$&0&1&2&3&4&5&6&7&8&9&10&11\\\midrule $\phi(V_i)$&19&6&6&6&10&10&14&14&18&18&19&19\\ $\phi(W_i)$&19&6&5&6&9&10&13&14&17&18&19&22\\ $\phi(X_i)$&19&5&5&6&9&10&13&14&17&18&21&22\\ $\phi(Y_i)$&6&5&5&9&9&13&13&17&17&19&21&23\\\bottomrule \end{tabular} \caption{An integer potential for the original arcs and all boundary bridges.}\label{tab:potential} \end{table} \begin{lemma}\label{lem:bridge} For a fixed boundary set $J$, the operation \eqref{eq:bridge} gives a bijection from the old path families for $J$ to the new path families for $J$ that use the middle bridge. \end{lemma} \begin{proof} Let $\one_J(i)$ equal $1$ for $i\in J$ and $0$ otherwise. Write $\varepsilon_p=\one_J(p)$ and $\varepsilon_j=\one_J(j)$. The old sink $p$ receives flow $\varepsilon_p$, and the old source $j$ emits flow $1-\varepsilon_j$. Assign to the three new arcs, in the order in \eqref{eq:bridge}, the values \begin{equation}\label{eq:bridgeflow} (1-\varepsilon_p,\ 1,\ \varepsilon_j). \end{equation} At the old port $p$, the incoming total becomes $\varepsilon_p+(1-\varepsilon_p)=1$; at the old port $j$, the outgoing total becomes $(1-\varepsilon_j)+\varepsilon_j=1$. Thus both converted ports have unit incoming and outgoing flow, and every other internal capacity is unchanged. The new boundary values are those for $I'\setminus J$ and $J\setminus I'$. Acyclicity and unit vertex capacities give a unique decomposition into vertex-disjoint paths. Conversely, a new family using the middle bridge has value $1$ there. Its boundary values force the two short-arc values in \eqref{eq:bridgeflow}. Conservation then leaves incoming value $\varepsilon_p$ at the old sink and outgoing value $1-\varepsilon_j$ at the old source. Deleting the three new arcs and the two new ports recovers the old family. These operations are inverse. \end{proof} Let $J_{ab}$ be the boundary set $J(M)$ common to the five matchings associated with the pair $(a,b)$. Apply the lemma successively to each of these matchings for every pair in \eqref{eq:pairs}. Let $f^0_{ab},f^1_{ab}\in\{0,1\}^{183}$ be the flows obtained from its bottom and top matchings. Define \begin{equation}\label{eq:fullmid} h=\frac12\sum_{(a,b)\in\mathcal E}(f^0_{ab}+f^1_{ab}). \end{equation} This is integral on all $183$ arcs. On the original arcs it equals $m_e$ off $M_0$ and $6-m_e$ on $M_0$, with $m$ from \eqref{eq:matchingmid}. On every bridge it equals $6$. On the adjacent short arcs it equals, respectively, \[ \sum_{(a,b)\in\mathcal E}(1-\one_{J_{ab}}(p)), \qquad \sum_{(a,b)\in\mathcal E}\one_{J_{ab}}(j). \] Bottom and top in one factor have the same $J_{ab}$, so these are their midpoint values. Nonnegativity follows from \eqref{eq:fullmid}. \begin{proposition}\label{prop:pathhole} There is no decomposition of $h$ as a sum of six path-family incidence vectors in $G$, one with each boundary condition $J_{ab}$. \end{proposition} \begin{proof} An individual path family uses each bridge at most once. Since $h$ has value $6$ on every bridge, any putative decomposition must use every bridge in every factor. Apply Lemma~\ref{lem:bridge} in reverse order. Then invert \eqref{eq:affinematching} on the six factors. This gives a decomposition of $m$ by the six prescribed matchings, contradicting Lemma~\ref{lem:matchinghole}. \end{proof} \section{A grid construction preserving vertex capacities}\label{sec:grid} Construct a directed grid network from $G$ as follows. Every edge points rightwards or upwards; a segment is the union of its unit lattice edges. \subsection{Vertex numbers and arc labels} Give $V_i,W_i,X_i,Y_i,b_j$ the respective vertex numbers \begin{equation}\label{eq:vertexlabels} i,\quad12+i,\quad24+i,\quad36+i,\quad48+j. \end{equation} Number the original edges, starting with zero, in the following order: \begin{equation}\label{eq:arclabels} C_0,\ldots,C_{11};\quad R_0,\ldots,R_{11};\quad (A_i,B_i,D_i)_{i=0}^{11};\quad(\xi_i,\eta_i)_{i=0}^{11}. \end{equation} Keep these labels after orientation. At bridge step $k$, starting with $k=0$, give the new source and sink the vertex numbers $72+2k,73+2k$ and give the three arcs in \eqref{eq:bridge} the labels $84+3k,85+3k,86+3k$ in that order. The new ports retain the boundary labels $p,j$. The least-$j$ rule above determines all ports and incidences. Process the $114$ nonboundary vertices of $G$ in the following order: \begin{equation}\label{eq:order} \begin{gathered} 25,37,14,26,38,53,72,75,76,79,84,87,92,95,104,107,116,119,134,\\ 36,13,1,2,3,15,27,54,55,73,56,77,82,85,90,93,102,105,114,117,132,\\ 39,16,28,40,57,80,83,88,91,100,103,112,115,130,4,5,17,29,58,59,81,\\ 60,89,98,101,110,113,128,41,18,30,42,61,96,99,108,111,126,6,7,19,\\ 31,62,63,97,64,109,124,43,20,32,44,65,122,8,9,21,33,66,120,24,12,\\ 0,11,10,22,45,67,68,34,46,23,35,47. \end{gathered} \end{equation} The initial ordered active arcs, one from each final source port, are \begin{equation}\label{eq:active} (60,61,62,63,64,87,93,105,117,135,153,180). \end{equation} At a processed vertex list its outgoing arcs increasingly, except at vertices $11,12,22$, where the order is reversed. Its incoming arcs form a consecutive block in the active list. Replace that block by the outgoing list. Table~\ref{tab:processing-certificate} records all $114$ replacements. Starting from \eqref{eq:active}, each row lists the consecutive incoming block at the stated position and its replacement. Thus every incoming arc is present when its vertex is processed, and the last active list is \begin{equation}\label{eq:finalactive} (83,82,81,158,161,164,167,170,173,176,179,182). \end{equation} Its heads are the final sink ports with boundary labels $23,22,\ldots,12$. In particular, \eqref{eq:order} is a topological ordering of the internal vertices. \subsection{The tile rule} At the beginning set the horizontal position $x=0$ and put the twelve active arcs in rows $1,\ldots,12$, in their order. Suppose a vertex is to be processed. Replace its incoming block as above to form the new active list. If the largest old row is $R$, give the new list consecutive rows starting at $R+2$. Partition the transition into ordered components: each unchanged active arc is a component with one input and one output, and the processed vertex is the single component containing its incoming and outgoing blocks. Suppose there are $c$ components. The new horizontal boundary is $x'=x+c+1$. Number components $j=1,\ldots,c$ in active-list order, and place the vertical segment of component $j$ in column \begin{equation}\label{eq:tilecol} x+c-j+1. \end{equation} For this component let $a_1<\cdots0}F^{a_F},\qquad M=\prod_{a_F<0}F^{-a_F}. \end{equation} To see directly why \eqref{eq:formalE} gives the required exponents, multiply \eqref{eq:inverse} over $l\leq i\leq r$ in one sweep. The factors telescope to \begin{equation}\label{eq:runinverse} \prod_{i=l}^{r}t_{s,i}^{v} =\left(\frac{\cc_{l,s}\cc_{r+2,s-1}} {\cc_{r+1,s}\cc_{l+1,s-1}}\right)^v. \end{equation} Thus $P/M=\mathbf t^u$. \begin{proof}[Proof of Theorem~\ref{thm:main}] Proposition~\ref{prop:LW_hole} gives all hypotheses of Lemma~\ref{lem:holecriterion} with $r=6$. The products defined by \eqref{eq:PMexplicit} are exactly those obtained by its chamber clearing. Therefore \[ 0