This question is about Main Tridiagonal Birkhoff Faces (or MTBFs), defined in this question. (One goal of this question - to be addressed in a corollary question - is to establish that MTBFs constitute the rectangular prime Tridiagonal Birkhoff faces.)
What are the combinatorial types of the facets of a MTBF?
We consider 21 disjoint, exhaustive cases in all. Several pairs of cases are bilaterally symmetric to each other (i.e., Cases: 1a & 1c, 1b & 1d, 2a & 2b, 3a & 3c, 3b & 3d, 4b & 4d, 4c & 4e, 4g & 4h); a proof is only presented for one of each pair because the proofs are very similar. Cases 0 through 2c cover MTBF facets associated with main diagonal entries (i.e., of the form $a_{m,m} = 0$). Case 0 addresses main diagonal entries in the interior of a part of the composition. Cases 1a through 1d address the first and last main diagonal entries of the composition $a_{2,2}$ and $a_{d+k-1,d+k-1}$. Cases 2a through 2c address main diagonal entries that are either the first or last entry of a part of the composition (or both) (other than those addressed by Cases 1a through 1d). Cases 3a through 4i cover MTBF facets associated with superdiagonal entries (i.e., of the form $a_{m,m+1} = 0$).
We begin with the MTBF facets associated with main diagonal entries (i.e., of the form $a_{m,m} = 0$). First, observe that the potential number of facets of MTBF ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ associated with main diagonal entries is $d - 1$ - i.e., corresponding to the unconstrained main diagonal elements from $a_{2,2}$ to $a_{d+k-1,d+k-1}$. We identify the parts of the composition: $c_k(d - 1)$ = $(p_1, p_2, ... p_k)$, where $\sum_{i=1}^k p_i = d - 1$.
Case $0$: A facet associated with a main diagonal entry $a_{m,m}$ in the interior of a part of $c_k(d - 1)$ - i.e., neither the first nor last entry in the part. (Note that this implies that the part containing $a_{m,m}$ has length at least three.) Let's count these (potential) facets. From the $d - 1$ unconstrained entries, subtract $2k$ entries, representing the first and last entry in each part of $c_k(d - 1)$. If there are parts of $c_k(d - 1)$ equal to $1$, we have over-subtracted, as the first and last entries in these parts are not distinct. Say there are $k_1$ parts of $c_k(d - 1)$ equal to $1$; we arrive at a count of $d - 1 - 2k + k_1$. The combinatorial type of a Case $0$ facet meets the definition of a MTBF. Specifically, it is the face ${}^f_{d-1}\Omega^t_{d+k} (d-1;c_{k+1}(d - 2))$, where $c_{k+1}(d - 2)$ is formed from $c_k(d - 1)$ by replacing the part containing $a_{m,m}$ with two parts - the number of entries in the part preceding $a_{m,m}$, and the number of entries in the part following $a_{m,m}$.
To address the remaining cases, we recall that Dahl [1] has pointed out that the vertices of the tridiagonal Birkhoff polytope can be written as direct sums of J and K, where:
$J$ = $\begin{bmatrix} 1 \\ \end{bmatrix}$
$K$ = $\begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix}$
To represent such a direct sum, we'll use a string of $J$'s & $K$'s - e.g., $JKJ$ represents the direct sum of $J$, $K$ and $J$. We'll say that $J$ has length $1$ and $K$ has length $2$ - i.e., the number of positions taken on the main diagonal. Thus, the vertices of $\Omega^t_{n}$ are represented by all strings of $J$ and $K$ of length $n$. As discussed here, the constraints $a_{n_i,n_i} = 0$ for $2 \lt n_i \lt d + k - 1$ associated with ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ imply that a vertex of this MTBF cannot have $J$ in position $n_i$ - in that case $a_{n_i,n_i} = 1$. Equivalently, it must be the case that either $K$ occupies positions $n_i - 1$ and $n_i$, or $K$ occupies positions $n_i$ and $n_i + 1$ (for i = 1 to k - 1).
$\mathbf Case 1a:$ The facet $a_{2,2} = 0$, where the first part $p_1$ of $c_k(d - 1)$ is greater than $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-1} (d - 1;c'_k(d - 2))$, where $c'_k(d - 2) = (p_1 - 1, p_2, ... p_k)$.
We have $n_1 \gt 2$, and we add a constraint for the vertices of this facet that they must begin with either K or JK (as $a_{2,2} = 0$). The vertex set of this facet is isomorphic to the vertex set obtained by replacing each initial JK with K, and each initial K with J from each vertex; this is the vertex set of ${}^f_{d-1}\Omega^t_{d+k-1} (d - 1;c'_k(d - 2))$, with the first part of the composition reduced by 1.
$\mathbf Case 1b:$ The facet $a_{2,2} = 0$, where the first part $p_1$ of $c_k(d - 1)$ equals $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where $c'_{k-1}(d - 2) = (p_2, ... p_k)$.
We have $n_1 = 2$, and we add a constraint for the vertices of this facet that they must begin with either K or JK (as $a_{2,2} = 0$). Vertices of the Case $1b$ MTBF begin either with JJK, KK, or JK. Vertices of the facet therefore begin either with KK or JK. The vertex set of this facet is isomorphic to the vertex set obtained by replacing each initial KK with K, and each initial JK with J from each vertex; this is the vertex set of ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, with the first part of the composition omitted.
$\mathbf Case 1c:$ The facet $a_{d+k-1,d+k-1} = 0$, where the last part $p_k$ of $c_k(d - 1)$ is greater than $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-1} (d - 1;c'_k(d - 2))$, where $c'_k(d - 2) = (p_1, p_2, ... p_k - 1)$.
Proof omitted due to similarity to Case $1a$.
$\mathbf Case 1d:$ The facet $a_{d+k-1,d+k-1} = 0$, where the last part $p_k$ of $c_k(d - 1)$ equals $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where $c'_{k-1}(d - 2) = (p_1, p_2, ... p_{k-1})$.
Proof omitted due to similarity to Case $1b$.
$\mathbf Case 2a:$ The facet $a_{n_i+1,n_i+1} = 0$; i. e., $a_{n_i+1,n_i+1}$ is the first entry of the $(i+1)$st part of $c_k(d - 1)$ (which part $p_{i+1}$ is greater than $1$); $1 \le i \lt k$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where the $i$th part of $c'_{k-1}(d - 2)$ equals $p_i + p_{i+1} - 1$, and the other parts of $c'_{k-1}(d - 2)$ correspond to the other parts of $c_k(d - 1)$.
Vertices of the Case $2a$ MTBF have K occupying positions $n_i - 1$ through $n_i$, or K occupying positions $n_i$ through $n_i+ 1$. We add a constraint for the vertices of this facet that we have K occupying positions $n_i$ through $n_i + 1$, or K occupying positions $n_i + 1$ through $n_i + 2$. Vertices of the facet therefore must have either KK occupying positions $n_i - 1$ through $n_i + 2$ or K occupying positions $n_i$ through $n_i + 1$. The vertex set of this facet is isomorphic to the vertex set obtained by replacing each KK at positions $n_i - 1$ through $n_i + 2$ with K, and by deleting each K at positions $n_i$ through $n_i + 1$ from each vertex; we notice that the constraint associated with position $n_i$ has been removed. So, this is the vertex set of ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where the $i$th part of $c'_{k-1}(d - 2)$ equals $p_i + p_{i+1} - 1$, and the other parts of $c'_{k-1}(d - 2)$ correspond to the other parts of $c_k(d - 1)$.
$\mathbf Case 2b:$ The facet $a_{n_i-1,n_i-1} = 0$; i. e., $a_{n_i-1,n_i-1}$ is the last entry of the $i$th part of $c_k(d - 1)$ (which part $p_i$ is greater than $1$); $1 \le i \lt k$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where the $i$th part of $c'_{k-1}(d - 2)$ equals $p_i + p_{i+1} - 1$, and the other parts of $c'_{k-1}(d - 2)$ correspond to the other parts of $c_k(d - 1)$.
Proof omitted due to similarity to Case $2a$.
$\mathbf Case 2c:$ The facet $a_{n_i-1,n_i-1} = 0$, where $n_i = n_{i-1} + 2$, i.e., $a_{n_i-1,n_i-1}$ is the entry representing the $i$th part of $c_k(d - 1)$ (which part $p_i$ equals $1$); $1 \lt i \lt k$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where $c'_{k-1}(d - 2) = (p_1, ..., p_{i-1}, p_{i+1}, ... p_k)$.
Vertices of the Case $2c$ MTBF have K occupying positions $n_{i-1} - 1$ through $n_{i-1}$, or K occupying positions $n_{i-1}$ through $j$, and also K occupying positions $j$ through $n_i$, or K occupying positions $n_i$ through $n_i+ 1$. We add a constraint for the vertices of this facet that we have K occupying positions $n_{i-1}$ through $n_i - 1$, or K occupying positions $n_i - 1$ through $n_i$. Vertices of the facet therefore must have either KK occupying positions $n_{i-1} - 1$ through $n_i$ or KK occupying positions $n_{i-1}$ through $n_i + 1$. The vertex set of this facet is isomorphic to the vertex set obtained by replacing each KK at positions $n_{i-1} - 1$ through $n_i$ with K, and by replacing each KK at positions $n_{i-1}$ through $n_i + 1$ with K from each vertex; we notice that from the two constraints associated with positions $n_{i-1}$ and $n_i$, one has been removed. So, this is the vertex set of ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where $c'_{k-1}(d - 2) = (p_1, ..., p_{i-1}, p_{i+1}, ... p_k)$.
We count the facets considered thus far: It's clear that Cases $1a$ through $1d$ cover two facets. Case $2a$ facets relate to a part greater than one starting in position $n_i + 1$, of which there are $k - 1 - k_1$ if $p_k \gt 1$, and $k - k_1$ if $p_k = 1$. Similarly, the facet count for Case $2b$ is $k - 1 - k_1$ if $p_1 \gt 1$, and $k - k_1$ if $p_1 = 1$. The facet count for Case $2c$ is $k_1$ if neither $p_1$ nor $p_k$ equal $1$, $k_1 - 2$ if both $p_1$ and $p_k$ equal $1$, and $k_1 - 1$ if exactly one of $p_1$ and $p_k$ equals $1$. The total facets considered in Cases $1a$ through $2c$, therefore, are $2k - k_1$. Adding the $d - 1 - 2k + k_1$ facets from Case $0$, we have considered $d - 1$ facets thus far.
Next, we consider facets associated with superdiagonal matrix entries (of the form $a_{j,j+1} = 0$). (As tridiagonal doubly stochastic matrices are symmetric, $a_{j,j+1} = 0$ if and only if the corresponding subdiagonal entry $a_{j+1,j} = 0$ as well.) To review, ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ is the intersection of $k - 1$ facets of $\Omega^t_{d+k}$ with equations: $$a_{n_i,n_i} = 0$ for $i = 1, ... k - 1$$, where $$n_1 \gt 2; n_{i+1} \gt n_i + 1$ for $i = 1, ... k - 2; n_{k-1} \lt d + k - 1$$ If $k \gt 1$, we have one or more constrained main diagonal elements $a_{n_i,n_i} = 0$. We will show that $a_{n_{i} - 1,n_i} = 0$ and $a_{n_i,n_{i} + 1} = 0$ are lower-dimensional faces (not facets) of ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$. Case A: $a_{n_{i} - 1,n_i} = 0$ (we already have $a_{n_i,n_i} = 0$). Because all matrices within $\Omega^t_{d+k}$ are tridiagonal doubly stochastic, we conclude that $a_{n_{i} + 1,n_i} = 1$. Again, because all matrices within $\Omega^t_{d+k}$ are tridiagonal doubly stochastic (with all non-negative entries), we conclude that $a_{n_{i} + 1,n_{i} + 1} = 0$ and $a_{n_{i} + 1,n_{i} + 2} = 0$. However, $a_{n_{i} + 1,n_{i} + 1}$ is an unconstrained main diagonal entry included in Case 1 or 2 above; thus we know that $a_{n_{i} + 1,n_{i} + 1} = 0$ is a facet of ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$. Case B: $a_{n_{i} + 1,n_{i} + 2} = 0$ (and $a_{n_i,n_i} = 0$) is similar to Case A and will be omitted.
Cases $3a$ through $3d$ will address the first and last superdiagonal entries $a_{1,2}$ and $a_{d+k-1,d+k}$.
$\mathbf Case 3a:$ The facet $a_{1,2} = 0$, where the first part $p_1$ of $c_k(d - 1)$ is greater than $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-1} (d - 1;c'_k(d - 2))$, where $c'_k(d - 2) = (p_1 - 1, p_2, ... p_k)$.
We have $n_1 \gt 2$, and we add a constraint for the vertices of this facet that they must begin with J (as $a_{1,1} = 1$). The vertex set of this facet is isomorphic to the vertex set obtained by removing the initial J from each vertex; this is the vertex set of ${}^f_{d-1}\Omega^t_{d+k-1} (d - 1;c'_k(d - 2))$, with the first part of the composition reduced by 1.
$\mathbf Case 3b:$ The facet $a_{1,2} = 0$, where the first part $p_1$ of $c_k(d - 1)$ equals $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where $c'_{k-1}(d - 2) = (p_2, ... p_k)$.
We have $n_1 = 2$, and we add a constraint for the vertices of this facet that they must begin with J (as $a_{1,1} = 1$). Vertices of this MTBF begin either with JJK, KK, or JK. Vertices of the facet therefore begin either with JJK or JK. The vertex set of this facet is isomorphic to the vertex set obtained by replacing each initial JJK with K, and each initial JK with J from each vertex; this is the vertex set of ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, with the first part of the composition omitted.
$\mathbf Case 3c:$ The facet $a_{d+k-1,d+k} = 0$, where the last part $p_k$ of $c_k(d - 1)$ is greater than $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-1} (d - 1;c'_k(d - 2))$, where $c'_k(d - 2) = (p_1, p_2, ... p_k - 1)$.
Proof omitted due to similarity to Case $3a$.
$\mathbf Case 3d:$ The facet $a_{d+k-1,d+k} = 0$, where the last part $p_k$ of $c_k(d - 1)$ equals $1$.
This facet has combinatorial type ${}^f_{d-1}\Omega^t_{d+k-2} (d - 1;c'_{k-1}(d - 2))$, where $c'_{k-1}(d - 2) = (p_1, p_2, ... p_{k-1})$.
Proof omitted due to similarity to Case $3b$.
Case $4a$ addresses superdiagonal entries (other than $a_{1,2}$ and $a_{d+k-1,d+k}$) where $k = 1$ and $d \gt 2$.
$\mathbf Case 4a:$ The facet $a_{m,m+1} = 0$, where $1 \lt m \lt d$, $d \gt 2$, and $k = 1$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{m-1}\Omega^t_m (m - 1;(m - 2))$ $\times$ ${}^f_{d-m}\Omega^t_{d-m+1} (d - m;(d - m - 1))$ = $\Omega^t_m$ $\times$ $\Omega^t_{d-m+1}$.
The Case 4a MTBF is $\Omega^t_{d+1}$. We add a constraint for the vertices of this facet that positions $m$ through $m + 1$ are not occupied by K; hence, (J,K) vertex strings of this facet can be divided into substrings of positions $1$ through $m$, and positions $m + 1$ through $d + 1$, with no constraints on either substring. Hence, the vertices of this facet are represented by all combinations of a (J,K) vertex string of length $m$, and a (J,K) vertex string of length $d - m + 1$; this is the vertex set of $\Omega^t_m$ $\times$ $\Omega^t_{d-m+1}$.
Cases $4b$ through $4e$ address superdiagonal entries within part $1$ and within part $k$ other than $a_{1,2}$ and $a_{d+k-1,d+k}$, where $k \ge 2$.
$\mathbf Case 4b:$ The facet $a_{n_1 - 2,n_1 - 1} = 0$, where $n_1 \ge 4$ (equivalently, $p_1 \ge 2$).
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{p_1-1}\Omega^t_{p_1} (p_1-1;(p_1 - 2))$ $\times$ ${}^f_{d-p_1}\Omega^t_{d-p_1+k-1} (d - p_1;c'_{k-1}(d - p_1 - 1))$, where $c'_{k-1}(d - p_1 - 1) = (p_2, ..., p_k)$.
The first part $p_1$ of $c_k(d - 1)$ equals $n_1 - 2$ (which is greater than $1$). Vertices of this Case $4b$ MTBF have K occupying positions $n_i - 1$ through $n_i$, or K occupying positions $n_i$ through $n_i+ 1$, for $i = 1$ though $k - 1$. We add a constraint for the vertices of this facet that positions $n_1 - 2$ through $n_1 - 1$ are not occupied by K. Hence, (J,K) vertex strings of this facet can be divided into substrings of positions $1$ through $n_1 - 2$ (with no constraints), and positions $n_1 - 1$ through $d + k$ (with the previously mentioned $k - 1$ constraints). The second substring set is identical to the vertex set of the facet $a_{2,2} = 0$ of ${}^f_{d-p_1+1}\Omega^t_{d-p_1+k} (d - p_1 + 1;c'_{k-1}(d - p_1))$, where $c'_{k-1}(d - p_1) = (p_2+1, ...p_k)$. By Case 1a, this vertex set is isometric to the vertex set of ${}^f_{d-p_1}\Omega^t_{d-p_1+k-1} (d - p_1;(p_2, ...p_k))$ Therefore the facet vertex set is isometric to the vertex set of of ${}^f_{p_1-1}\Omega^t_{p_1} (p_1-1;(p_1 - 2))$ $\times$ ${}^f_{d-p_1}\Omega^t_{d-p_1+k-1} (d - p_1;c'_{k-1}(d - p_1 - 1))$, where $c'_{k-1}(d - p_1 - 1) = (p_2, ..., p_k)$.
$\mathbf Case 4c:$ The facet $a_{m,m+1} = 0$, where $1 \lt m \lt m + 2 \lt n_1$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{m-1}\Omega^t_m (m - 1;(m - 2))$ $\times$ ${}^f_{d-m}\Omega^t_{d-m+k} (d-m;c'_k(d - m - 1))$, where $c'_k(d - m - 1) = (p_1 - m, ..., p_k)$.
Vertices of this Case $4c$ MTBF have K occupying positions $n_i - 1$ through $n_i$, or K occupying positions $n_i$ through $n_i+ 1$, for $i = 1$ though $k - 1$. We add a constraint for the vertices of this facet that positions $m$ through $m + 1$ are not occupied by K. Hence, (J,K) vertex strings of this facet can be divided into substrings of positions $1$ through $m$ (with no constraints), and positions $m + 1$ through $d + k$ (with the previously mentioned $k - 1$ constraints). The second substring set is identical to the vertex set of the MTBF ${}^f_{d-m}\Omega^t_{d-m+k} (d-m;c'_k(d - m - 1))$, where $c'_k(d - m - 1) = (p_1 - m, ..., p_k)$. Therefore the vertex set of this facet is the vertex set of ${}^f_{m-1}\Omega^t_m (m - 1;(m - 2))$ $\times$ ${}^f_{d-m}\Omega^t_{d-m+k} (d-m;c'_k(d - m - 1))$, where $c'_k(d - m - 1) = (p_1 - m, ..., p_k)$.
$\mathbf Case 4d:$ The facet $a_{n_{k-1} + 1,n_{k-1} + 2} = 0$, where $n_{k-1} \le d + k - 3$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{d-p_k}\Omega^t_{d-p_k+k-1} (d - p_k;c'_{k-1}(d - p_k - 1))$ $\times$ ${}^f_{p_k-1}\Omega^t_{p_k} (p_k-1;(p_k - 2))$ , where $c'_{k-1}(d - p_k - 1) = (p_1, ..., p_{k-1})$.
Proof omitted due to similarity to Case $4b$.
$\mathbf Case 4e:$ The facet $a_{m,m+1} = 0$, where $n_{k-1} + 1 \lt m \lt m + 1 \lt d + k$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{m-k}\Omega^t_{m} (m - k;c'_k(m - k - 1))$ $\times$ ${}^f_{d+k-m-1}\Omega^t_{d+k-m} (d + k - m - 1;(d + k - m - 2))$, where $c'_k(m - k - 1) = (p_1, ..., p_{k-1}, m - n_{k-1} - 1)$.
Proof omitted due to similarity to Case $4c$.
Cases $4f$ through $4i$ address superdiagonal entries within an internal part $i$ of $(d;c_k(d - 1))$, where $1 \lt i \lt k$.
$\mathbf Case 4f:$ The facet $a_{n_{i-1} + 1,n_{i-1} + 2} = 0$, where $n_i = n_{i-1} + 3$, so that the entries $a_{n_{i-1} + 1,n_{i-1} + 1}$ and $a_{n_{i-1} + 2,n_{i-1} + 2}$ represent part $i$ of $c_k(d - 1) = 2$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{d'}\Omega^t_{d'+i-1} (d';c'_{i-1}(d' - 1))$ $\times$ ${}^f_{d-d'-1}\Omega^t_{d-d'+k-i-1} (d-d'-1;c'_{k-i}(d - d' - 2))$, where $d' - 1 = \sum_{j=1}^{i-1} p_j = n_{i-1} - i$, $c'_{i-1}(d' - 1) = (p_1, ..., p_{i-1})$, and $c'_{k-i}(d - d' - 2)) = (p_{i+1}, ..., p_k)$.
Vertices of this MTBF have K occupying positions $n_i - 1$ through $n_i$, or K occupying positions $n_i$ through $n_i+ 1$, for $i = 1$ though $k - 1$. We add a constraint for the vertices of this facet that positions $n_{i-1} + 1$ through $n_{i-1} + 2$ are not occupied by K. Hence, (J,K) vertex strings of this facet can be divided into substrings of positions $1$ through $n_{i-1} + 1$ (with the first $i - 1$ of the previously mentioned $k - 1$ constraints), and positions $n_{i-1} + 2$ through $d + k$ (with the last $k - i$ of the previously mentioned $k - 1$ constraints). The first substring set is identical to the vertex set of the facet $a_{n_{i-1},n_{i-1}} = 0$ of the MTBF of $\Omega^t_{n_{i-1}+1}$ having the same $i - 2$ constraints as the first $i - 2$ constraints of the Case 4f MTBF. (The final part of the composition representing this MTBF is $p_{i-1} + 1 \ge 2$, with the "$+ 1$" representing position $n_{i-1}$.) Therefore, by Case $1c$, the vertex set of this first substring is isomorphic to the vertex set of ${}^f_{d'}\Omega^t_{d'+i-1} (d';c'_{i-1}(d' - 1))$, where $c'_i(d' - 1) = (p_1, ..., p_{i-1})$. The second substring set is identical to the vertex set of the facet $a_{1,1} = 0$ of the MTBF of $\Omega^t_{d+k-n_i+2}$ having the same $k - i - 1$ constraints as the last $k - i - 1$ constraints of the Case 4f MTBF. (The first part of the composition representing this MTBF is $p_{i+1} + 1 \ge 2$, with the "$+ 1$" representing position $n_i$.) Therefore, by Case $1a$, the vertex set of this second substring is isomorphic to the vertex set of ${}^f_{d-d'-1}\Omega^t_{d-d'+k-i-1} (d-d'-1;c'_{k-i}(d - d' - 2))$, where $c'_{k-i}(d - d' - 2) = (p_{i+1}, ..., p_k)$. Because the vertices of the Case $4f$ facet are represented by all combinations of vertices from the two aforementioned vertex sets, we conclude that the vertex set of this facet is the vertex set of ${}^f_{d'}\Omega^t_{d'+i-1} (d';c'_{i-1}(d' - 1))$ $\times$ ${}^f_{d-d'-1}\Omega^t_{d-d'+k-i-1} (d-d'-1;c'_{k-i}(d - d' - 2))$, where $d' - 1 = \sum_{j=1}^{i-1} p_j = n_{i-1} - i$, $c'_{i-1}(d' - 1) = (p_1, ..., p_{i-1})$, and $c'_{k-i}(d - d' - 2)) = (p_{i+1}, ..., p_k)$.
$\mathbf Case 4g:$ The facet $a_{n_{i-1} + 1,n_{i-1} + 2} = 0$, where $a_{n_{i-1} + 1,n_{i-1} + 1}$ is the first entry of part $i$ of $c_k(d - 1) \gt 2$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{d'}\Omega^t_{d'+i-1} (d';c'_{i-1}(d' - 1))$ $\times$ ${}^f_{d-d'-1}\Omega^t_{d-d'+k-i} (d-d'-1;c'_{k-i+1}(d - d' - 2))$, where $d' - 1 = \sum_{j=1}^{i-1} p_j = n_{i-1} - i$, $c'_{i-1}(d' - 1) = (p_1, ..., p_{i-1})$, and $c'_{k-i+1}(d - d' - 2)) = (p_i - 2, p_{i+1},..., p_k)$.
Vertices of this MTBF have K occupying positions $n_i - 1$ through $n_i$, or K occupying positions $n_i$ through $n_i+ 1$. We add a constraint for the vertices of this facet that positions $n_{i-1} + 1$ through $n_{i-1} + 2$ are not occupied by K. Hence, (J,K) vertex strings of this facet can be divided into substrings of positions $1$ through $n_{i-1} + 1$ (with the first $i - 1$ of the previously mentioned $k - 1$ constraints), and positions $n_{i-1} + 2$ through $d + k$ (with the last $k - i$ of the previously mentioned $k - 1$ constraints). The first substring set is identical to the vertex set of the facet $a_{n_{i-1},n_{i-1}} = 0$ of the MTBF of $\Omega^t_{n_{i-1}+1}$ having the same $i - 2$ constraints as the first $i - 2$ constraints of the Case 4f MTBF. (The final part of the composition representing this MTBF is $p_{i-1} + 1 \ge 2$, with the "$+ 1$" representing position $n_{i-1}$.) Therefore, by Case $1c$, the vertex set of this first substring is isomorphic to the vertex set of ${}^f_{d'}\Omega^t_{d'+i-1} (d';c'_{i-1}(d' - 1))$, where $c'_i(d' - 1) = (p_1, ..., p_{i-1})$. The second substring set is identical to the vertex set of the MTBF of $\Omega^t_{d-d'+k-i}$ having the same $k - i$ constraints as the last $k - i$ constraints of the Case 4g MTBF. Therefore, the vertex set of this second substring is the vertex set of ${}^f_{d-d'-1}\Omega^t_{d-d'+k-i} (d-d'-1;c'_{k-i+1}(d - d' - 2))$, where $c'_{k-i+1}(d - d' - 2)) = (p_i - 2, p_{i+1},..., p_k)$. Because the vertices of the Case $4g$ facet are represented by all combinations of vertices from the two aforementioned vertex sets, we conclude that the vertex set of this facet is the vertex set of ${}^f_{d'}\Omega^t_{d'+i-1} (d';c'_{i-1}(d' - 1))$ $\times$ ${}^f_{d-d'-1}\Omega^t_{d-d'+k-i} (d-d'-1;c'_{k-i+1}(d - d' - 2))$, where $d' - 1 = \sum_{j=1}^{i-1} p_j = n_{i-1} - i$, $c'_{i-1}(d' - 1) = (p_1, ..., p_{i-1})$, and $c'_{k-i+1}(d - d' - 2)) = (p_i - 2, p_{i+1},..., p_k)$.
$\mathbf Case 4h:$ The facet $a_{n_{i} - 2,n_{i} - 1} = 0$, where $a_{n_{i} - 1,n_{i} - 1}$ is the last entry of a part of $c_k(d - 1) \gt 2$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{d'}\Omega^t_{d'+i} (d';c'_i(d' - 1))$ $\times$ ${}^f_{d-d'-1}\Omega^t_{d-d'+k-i-1} (d-d'-1;c'_{k-i}(d - d' - 2))$, where $d' - 1 = \sum_{j=1}^{i} p_j - 2 = n_i - i - 3$, $c'_i(d' - 1) = (p_1, ..., p_i-2)$, and $c'_{k-i}(d - d' - 2)) = (p_{i+1}-2, ..., p_k)$.
Proof omitted due to similarity to Case $4g$.
$\mathbf Case 4i:$ The facet $a_{m,m+1} = 0$, where $n_{i-1} + 1 \lt m \lt m + 2 \lt n_i$.
This facet has combinatorial type of the rectangular product of MTBFs: ${}^f_{m-i}\Omega^t_{m} (m - i;c'_i(m - i - 1))$ $\times$ ${}^f_{d+i-m-1}\Omega^t_{d+k-m} (d + i - m - 1;c'_{k-i+1}(d + i - m - 2))$, where $c'_i(m - i - 1) = (p_1, ..., p_{i-1}, m - n_{i-1} - 1)$ and $c'_{k-i+1}(d + i - m - 2) = (n_i - m - 2, p_{i+1} ..., p_{k})$.
Vertices of this MTBF have K occupying positions $n_i - 1$ through $n_i$, or K occupying positions $n_i$ through $n_i+ 1$, for $i = 1$ though $k - 1$. We add a constraint for the vertices of this facet that positions $m$ through $m + 1$ are not occupied by K. Hence, (J,K) vertex strings of this facet can be divided into substrings of positions $1$ through $m$ (with the previously mentioned $k - 1$ constraints), and positions $m + 1$ through $d + k$ (with no constraints). The first substring set is identical to the vertex set of the MTBF of $\Omega^t_{m}$ having the same $i - 1$ constraints as the first $i - 1$ constraints of the Case 4i MTBF. Therefore, the vertex set of this first substring is the vertex set of ${}^f_{m-i}\Omega^t_{m} (m - i;c'_i(m - i - 1))$, where $c'_i(m - i - 1) = (p_1, ..., p_{i-1}, m - n_{i-1} - 1)$. The second substring set is identical to the vertex set of the MTBF of $\Omega^t_{d+k-m}$ having the same $k - i + 1$ constraints as the last $k - i + 1$ constraints of the Case 4i MTBF. Therefore, the vertex set of this second substring is the vertex set of ${}^f_{d+i-m-1}\Omega^t_{d+k-m} (d + i - m - 1;c'_{k-i+1}(d + i - m - 2))$, where $c'_{k-i+1}(d + i - m - 2) = (n_i - m - 2, p_{i+1} ..., p_{k})$. Because the vertices of the Case $4i$ facet are represented by all combinations of vertices from the two aforementioned vertex sets, we conclude that the vertex set of this facet is the vertex set of ${}^f_{m-i}\Omega^t_{m} (m - i;c'_i(m - i - 1))$ $\times$ ${}^f_{d+i-m-1}\Omega^t_{d+k-m} (d + i - m - 1;c'_{k-i+1}(d + i - m - 2))$, where $c'_i(m - i - 1) = (p_1, ..., p_{i-1}, m - n_{i-1} - 1)$ and $c'_{k-i+1}(d + i - m - 2) = (n_i - m - 2, p_{i+1} ..., p_{k})$.
To summarize the facet counts:
The $d - 1$ MTBF facets represented by Cases $0$ through $2c$ are MTBFs.
The $2$ MTBF facets represented by Cases $3a$ through $3d$ are also MTBFs (for a total of $d + 1$ facets that are MTBFs).
To count the MTBF facets represented by Cases $4a$ through $4i$, which are rectangular products of two MTBFs: Case $4a$ (where $k = 1$) comprises $d - 2$ ($= d - 1 - k$) facets. Cases $4b$ abd $4c$ comprise $p_1 - 1$ facets, and Cases $4d$ abd $4e$ comprise $p_k - 1$ facets, for a total of $d - 1 - k$ facets in the case $k = 2$. For each part $p_i$ from $i = 2$ to $k - 1$, Cases $4f$ through $4i$ comprise $p_i - 1$ facets, for a total of $\sum_{i=2}^{k-1}(p_i - 1)$. Hence, in the case $k \ge 3$, Cases $4b$ through $4i$ comprise $d - 1 - k$ facets.
The total number of facets is $2d - k$.
[1] Geir Dahl, Tridiagonal doubly stochastic matrices, Linear Algebra and its Applications 390 (2004) pp. 197-208.