2026-06-02

Let ${\mathcal{B}}_1,\dots ,{\mathcal{B}}_L$ be the set of basic variables during the simplex method starting at Phase 2. Define a $p$-simplex $\sigma$ as active at step $i$ if the $x_{\sigma }^{+}-x_{\sigma }^{-}\ne 0$. Likewise, a $(p+1)$-simplex $\tau$ is active if $y_{\tau }^{+}-y_{\tau }^{-}\ne 0$. Define the following functions

$$f(\sigma )=\{\begin{array}{ll}i& \text{σ transistions from inactive to active at step i}\\ \infty & \text{otherwise}\end{array}$$

and

$$g(\sigma )=\{\begin{array}{ll}i& \text{σ transistions from active to inactive at step i}\\ \infty & \text{otherwise}.\end{array}$$

Conjecture: $f$ and $g$ are well-defined. That is, a simplex only becomes active once and only becomes inactive once.

Conjecture: For any $p$-simplex $\sigma$, it follows that $g(\sigma )=i<\infty$ if and only if there is a $(p+1)$-simplex $\tau >\sigma$ such that $f(\tau )=i$. We denote this pairing by $\{\sigma <\tau \}$ and the set of such pairings we denote by $V$. Consider the Hasse diagram for $K$ (excluding the $\varnothing$). For each pairing $\{\sigma <\tau \}\in V$, flip the direction of the edge in the diagram so that $\sigma \to \tau$ (see example below). Then $V$ forms an acyclic partial matching of the modified Hasse diagram.

Figure: Modified Hasse diagram (see example given in 2026-05-26) for partial matching $V=\{\{[0,1]<[0,1,4]\},\{[1,4]<[0,1,4]\},\{[0,3]<[0,3,4]\}\}$ (shown in red) showing the lack of a cycle.

We call the unpaired simplices critical. Denote by $u_p$ the number of critical $p$-simplices. Then it follows by discrete Morse theory (Theorem 6.3) that our complex is homotopy equivalent to a CW-complex with exactly $u_p$ cells of dimension $p$, for each $p\ge 0$. As a consequence: if $V$ is a complete acyclic matching, then our complex $K$ is contractible which matches our intuition.

---

Update: While $f$ and $g$ appear to be well-defined, the pairings $V$ do not always form a partial matching. This is even visible in the above picture…

Conjecture: Assume we are working in codimension 2. Then any $p$-simplex $\sigma$ appears at in at most one pair $\{\sigma <\tau \}\in V$.

Assuming this is true, there may be a well-defined injection

$$\varphi :\{\text{paired p-simplices}\}\hookrightarrow \{\text{(p+1)-simplices}\}$$

which defines a discrete gradient $\text{Im}(\varphi )$ which represents the “flow” of simplices.

Update 2: The above conjecture is false. I found an instance where $p$-simplices appear in several pairs.

Conjecture: Denote by

• $m_i$ = number of $p$-simplices $\sigma$ with $g(\sigma )=i$.
• $n_i$ = number of $(p+1)$-simplices $\tau$ with $f(\tau )=i$. Then

$$V=\underset{i\in S}{⨆}{K}_{m_i,n_i}$$

where $S$ is the set of steps with at least one transition and $K_{\ast ,\ast }$ is the complete bipartite graph.

Update 3: While the graphs are bipartite, they are not necessarily complete. In fact, after finding the bug in my code, the first conjecture appears to be true: any $p$-simplex $\sigma$ appears in at most one pair $\{\sigma <\tau \}\in V$.

Question: In codimension 3, do any $p$-simplices appear in more than one pair?

Below is the details of $V$ for a large instance in the format [i]: {[square] < [cube]} which coincides with 7 unique $i$ values:

V = {
812: {(3,0,0) < (3,1,0)}
812: {(5,0,0) < (5,1,0)}
812: {(7,0,0) < (7,1,0)}
812: {(9,0,0) < (9,1,0)}
812: {(0,1,0) < (1,1,0)}
812: {(10,1,0) < (9,1,0)}
907: {(10,7,0) < (9,7,0)}
907: {(0,5,0) < (1,5,0)}
907: {(0,3,0) < (1,3,0)}
907: {(0,7,0) < (1,7,0)}
907: {(10,3,0) < (9,3,0)}
907: {(9,2,0) < (9,3,0)}
907: {(7,2,0) < (7,3,0)}
907: {(10,5,0) < (9,5,0)}
907: {(5,2,0) < (5,3,0)}
952: {(1,10,0) < (1,9,0)}
952: {(0,9,0) < (1,9,0)}
995: {(2,9,0) < (3,9,0)}
995: {(3,10,0) < (3,9,0)}
1057: {(5,10,0) < (5,9,0)}
1057: {(4,9,0) < (5,9,0)}
1126: {(6,9,0) < (7,9,0)}
1126: {(7,10,0) < (7,9,0)}
1181: {(10,9,0) < (9,9,0)}
1181: {(8,9,0) < (9,9,0)}
1181: {(9,10,0) < (9,9,0)}
}