2026-06-29

Below is the smallest non-TU instance to the integral OHCP I have found:

Here is the Hasse diagram for $K$:

Homology groups over $\mathbb{Z}$:

$$\begin{array}{rl}{H}_0& \cong \mathbb{Z}\\ H_1& \cong \mathbb{Z}\\ H_2& \cong 0\\ H_3& \cong 0\end{array}$$

Code output:

n_0 = 9
n_1 = 27
n_2 = 27
n_3 = 9
Dimension: 3
Euler Char: 1

c = 1*[0,1] + 1*[1,4] + 1*[4,5] + -1*[2,5] + 1*[2,3] + -1*[0,3]; lambda=0
   z*=3:  xp[2]=1 xm[13]=1 xp[23]=1 yp[0]=1 yp[2]=1 ym[4]=1 ym[5]=1 ym[10]=1 ym[13]=1 yp[14]=1
  x = 1*[3,4] + -1*[2,4] + 1*[2,3]
  y = 1*[3,4,6] + 1*[0,3,6] + -1*[1,4,6] + -1*[0,1,6] + -1*[2,4,7] + -1*[4,5,7] + 1*[2,5,7]

Every instance had $|\det B|=1$. My conjecture is that this is due to the lack of torsion in the homology groups. Note that

$$SNF({\partial }_1)=I_8,SNF({\partial }_2)=I_{18},SNF({\partial }_3)=I_8.$$

We can get an iteration with $\det B=2$ with the following input:

$$b=[0,6]+[6,7]+[7,8]-[0,8]\text{ where }\lambda =\mathrm{0.5.}$$

 54: [Feasible][P2][det(B)=2][z=4][E=[3,4,6];L=[0,3,6]] 0*[0,5] 0*[3,4,6] 0*[0,3,4] 1*[0,6] 0*[4,5,7] 0*[0,3,8] 0*[1,6,7] 0*[0,1,4] 0*[1,2,4] 1*[6,7] 0*[2,4,7] 0*[1,2] 0*[1,2,7] 0*[4,6,7] 0*[0,1] 0*[2,5,7] 0*[4,5] 0*[2,7,8] 1*[7,8] 0*[3,5,8] 0*[3,6] 0*[2,3,8] 0*[5,7,8] 0*[2,3] 1*[0,8] 0*[0,5,8] 0*[6,8]
	 x = 1*[0,6] + 1*[6,7] + 1*[7,8] + -1*[0,8]; y = 

Computing the SNF for this instance gives us

$$SNF(B)=\left[\begin{array}{cc}{I}_{26}& 0\\ 0& 2\end{array}\right].$$

The last row of left-transform matrix $U$ is

$$G=\left[\begin{array}{ccccccccccccccccccccccccccc}0& 0& 0& 0& -1& 1& 1& 1& 0& 0& 0& 1& 1& 1& 0& 0& 0& 1& 0& 0& 1& 1& 1& 0& 0& 0& 0\end{array}\right].$$

Under the congruence relation from 2026-05-14, this basis has integral $x_B=B^{-1}b$ if

$$Gb\equiv 0\mathrm{mod}2.$$

That is,

$$-b_{[0,4]}+b_{[0,3]}+b_{[1,6]}+b_{[1,4]}+b_{[1,7]}+b_{[2,7]}+b_{[2,4]}+b_{[2,5]}+b_{[2,8]}+b_{[3,8]}+b_{[3,5]}=2k$$

for some $k\in \mathbb{Z}$. None of these edges are in the input vector $b$, i.e., $Gb=0$. Adding edge $[0,4]$ to $b$, results in our basis $B$ no longer being encountered in the simplex method. Indeed, computing $B^{-1}(b+e_{[0,4]})$ shows that adding $e_{[0,4]}$ makes the basis no longer feasible. Simply adding one of these edges to our input $b$ results in $B$ no longer being feasible.

Let $\mathcal{B}$ be the list of edges in the above sum and consider the input vector

$$b^{\prime }=\sum _{i\in \mathcal{B}}{\gamma }_i{e}_i.$$

Using sympy, we get that the following system of inequalities for feasibility:

$$\begin{array}{r}-1.0{\gamma }_{13}-1.0{\gamma }_{17}-1.0{\gamma }_{22}-1.0{\gamma }_4-1.0{\gamma }_7\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}-0.5{\gamma }_{13}-0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}-0.5{\gamma }_4+0.5{\gamma }_5-0.5{\gamma }_6-0.5{\gamma }_7\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}-0.5{\gamma }_{13}-0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}-0.5{\gamma }_4+0.5{\gamma }_5-0.5{\gamma }_6-0.5{\gamma }_7\ge 0\\ 1.0{\gamma }_{13}+1.0{\gamma }_4+1.0{\gamma }_7\ge 0\\ 0.5{\gamma }_{11}+0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}+0.5{\gamma }_{20}+0.5{\gamma }_{21}+0.5{\gamma }_{22}+0.5{\gamma }_4+0.5{\gamma }_5+0.5{\gamma }_6+0.5{\gamma }_7\ge 0\\ 1.0{\gamma }_6\ge 0\\ 0.5{\gamma }_{11}+0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}+0.5{\gamma }_{20}+0.5{\gamma }_{21}+0.5{\gamma }_{22}-0.5{\gamma }_4-0.5{\gamma }_5+0.5{\gamma }_6+0.5{\gamma }_7\ge 0\\ 0.5{\gamma }_{11}+0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}+0.5{\gamma }_{20}+0.5{\gamma }_{21}+0.5{\gamma }_{22}-0.5{\gamma }_4-0.5{\gamma }_5+0.5{\gamma }_6-0.5{\gamma }_7\ge 0\\ 0.5{\gamma }_{11}+0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}+0.5{\gamma }_{20}+0.5{\gamma }_{21}+0.5{\gamma }_{22}+0.5{\gamma }_4-0.5{\gamma }_5-0.5{\gamma }_6+0.5{\gamma }_7+1.0\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}+0.5{\gamma }_{13}-0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}+0.5{\gamma }_4+0.5{\gamma }_5-0.5{\gamma }_6+0.5{\gamma }_7\ge 0\\ 0.5{\gamma }_{11}-0.5{\gamma }_{12}-0.5{\gamma }_{13}-0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}+0.5{\gamma }_4+0.5{\gamma }_5+0.5{\gamma }_6+0.5{\gamma }_7\ge 0\\ -1.0{\gamma }_{11}-1.0{\gamma }_6\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}-0.5{\gamma }_{13}-0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}-0.5{\gamma }_4+0.5{\gamma }_5-0.5{\gamma }_6-0.5{\gamma }_7\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}-0.5{\gamma }_{13}-0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}+0.5{\gamma }_4+0.5{\gamma }_5-0.5{\gamma }_6-0.5{\gamma }_7\ge 0\\ 1.0{\gamma }_{17}\ge 0\\ -1.0{\gamma }_{13}-1.0{\gamma }_4-1.0{\gamma }_7\ge 0\\ 0.5{\gamma }_{11}+0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}+0.5{\gamma }_4+0.5{\gamma }_5+0.5{\gamma }_6+0.5{\gamma }_7\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}+0.5{\gamma }_{20}+0.5{\gamma }_{21}+0.5{\gamma }_{22}+0.5{\gamma }_4-0.5{\gamma }_5-0.5{\gamma }_6+0.5{\gamma }_7+1.0\ge 0\\ 1.0{\gamma }_{22}\ge 0\\ 0.5{\gamma }_{11}+0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}+0.5{\gamma }_{20}+0.5{\gamma }_{21}+0.5{\gamma }_{22}+0.5{\gamma }_4-0.5{\gamma }_5+0.5{\gamma }_6+0.5{\gamma }_7\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}-0.5{\gamma }_{13}-0.5{\gamma }_{17}-0.5{\gamma }_{20}+0.5{\gamma }_{21}+0.5{\gamma }_{22}-0.5{\gamma }_4-0.5{\gamma }_5-0.5{\gamma }_6-0.5{\gamma }_7\ge 0\\ -1.0{\gamma }_{13}-1.0{\gamma }_{17}-1.0{\gamma }_4-1.0{\gamma }_7\ge 0\\ 0.5{\gamma }_{11}+0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}+0.5{\gamma }_{20}-0.5{\gamma }_{21}-0.5{\gamma }_{22}+0.5{\gamma }_4+0.5{\gamma }_5+0.5{\gamma }_6+0.5{\gamma }_7\ge 0\\ -0.5{\gamma }_{11}-0.5{\gamma }_{12}+0.5{\gamma }_{13}+0.5{\gamma }_{17}-0.5{\gamma }_{20}-0.5{\gamma }_{21}+0.5{\gamma }_{22}+0.5{\gamma }_4-0.5{\gamma }_5-0.5{\gamma }_6+0.5{\gamma }_7+1.0\ge 0\\ -1.0{\gamma }_{13}-1.0{\gamma }_{17}-1.0{\gamma }_{22}-1.0{\gamma }_4-1.0{\gamma }_7\ge 0\end{array}$$

which sympy was unable to reduce. Adding in the constraint

$${\gamma }_{11}+{\gamma }_{12}+{\gamma }_{13}+{\gamma }_{17}+{\gamma }_{20}+{\gamma }_{21}+{\gamma }_{22}-{\gamma }_4+{\gamma }_5+{\gamma }_6+{\gamma }_7=2k+1$$

gives us an ILP, which we can use software to determine if there is a solution! Solving this ILP using Google’s OR-Tools finds the following vector:

$$b=\left[\begin{array}{c}0\\ 1\\ 0\\ 0\\ -1\\ 1\\ 0\\ 0\\ 1\\ 1\\ 0\\ 0\\ -1\\ 1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ -1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 0\end{array}\right].$$

Testing finds this vector $b$ gives $B^{-1}b\ge 0$ and $Gb=3\not\equiv 0\mathrm{mod}2$. However, upon running the above vector through the OHCP LP, our basis $B$ is not encountered and we still get an integral solution. My guess, is that its because $b\ngeqq 0$ which my code assumes to solve, i.e., $B$ is actually not feasible. If we also require that $b\ge 0$, then there is no feasible solution to the ILP.