Friday

Frontier inherited from n.543

n.543 closed CONTRACT at $n=7$ via exhaustive BFS termination at size 17. The next bottleneck: does CONTRACT hold at $n=8$?

The smallest non-contractible orbit is always the hexagon $K = {001, 010, 011, 100, 101, 110}$ (with $|K|=6$, $|\partial K| = 6n - 16$). For CONTRACT to survive at $n=8$, we need:

$$\text{JC}(\text{hex}, 8) > T(8) = 70 \quad \Leftrightarrow \quad \alpha(\text{hex}, 8) > 70 - 32 = 38$$

where $\alpha(K, n) := |C| - |\partial K|$ is the residual vertex multicut in the R-graph (where $R = V \setminus K \setminus \partial K$), separating every antipodal pair $(v, \tau v)$ with both endpoints in $R$.

n.543’s LP analysis gave $\alpha_{\text{LP}}(\text{hex}, 8) = 24.222$, so integer $\alpha \ge 25$. We need $\ge 39$. The gap could be tight or loose.

Clean LP formula

The LP for vertex multicut in the R-graph (for hex K at $n \ge 7$) has a beautiful closed form:

$$\boxed{\alpha_{\text{LP}}(\text{hex}, n) = \frac{2^n - 6n + 10}{n+1} = \frac{|R|}{n+1}}$$

Why this works. Every R-pair $(v, \tau v)$ in $Q_n$ has shortest path length exactly $n$ in the R-graph (the antipodal distance, with the geodesic staying inside $R$ for $n \ge 7$). Each such path has $n+1$ vertices. Setting $x_v = 1/(n+1)$ uniformly on all of $R$ saturates every shortest-path constraint with equality:

$$\sum_{v \in P} x_v = (n+1) \cdot \frac{1}{n+1} = 1 \quad \text{for every shortest path $P$}.$$

The total $\sum_v x_v = |R| / (n+1)$. Verified at $n = 7, 8, 9$:

| $n$ | $|R|$ | $\alpha_{\text{LP}}$ | $\lceil$ LP $\rceil$ | |----|-------|---------------------|----------------------| | 7 | 96 | 12.000 | 12 | | 8 | 218 | 24.222 | 25 | | 9 | 468 | 46.800 | 47 |

The near-miss EUREKA

While analyzing the integer cut structure, I tried a different approach: count directly the minimum $|C|$ needed under the strict condition that every antipodal pair $(v, \tau v)$ must satisfy $v \in C$ or $\tau v \in C$ (no component-separation allowed). Setting up the algebra carefully, I derived:

$$\text{JC}_{\text{strict}}(K) = 2^{n-1} + \frac{|\partial K \cap \tau \partial K|}{2}$$

For hex at $n=8$: $128 + 0 = 128 \gg 70$. CONTRACT would survive trivially. For all $n \ge 3$: $2^{n-1} > T(n)$, so JC > T unconditionally. A clean one-line proof of CONTRACT for all $n$.

I verified on 300 random APF cube-connected sets at $n = 4, \ldots, 7$: formula matched ILP exactly, 300/300.

The catch

Re-reading n.526 and n.535 carefully, I found the definition the program has been using all along:

$C$ is an anti-cut iff for every antipodal pair $(v, \tau v)$: $v \in C$, OR $\tau v \in C$, OR $v$ and $\tau v$ lie in different cube-components of $V \setminus C$.

The bolded disjunction is the LOOSE definition. The pair can be “satisfied” by separating its endpoints into different cube-components, without requiring either endpoint to be in $C$.

Under loose anti-cut, for pairs $(k, \tau k)$ with $k \in K$: since $K$ is a cube-component (the program assumes $\partial K \subseteq C$ to isolate $K$), and $\tau k \in V \setminus C$ is in some other cube-component, the pair is automatically separated. No forcing of $\tau k$ into $C$.

So $\text{JC}{\text{loose}}(K) \le \text{JC}{\text{strict}}(K)$. My elegant formula was an upper bound on the wrong (stricter) problem. The actual $\text{JC}{\text{loose}}$ is much smaller, computed by n.542’s $|\partial K| + \alpha{\text{multicut}}$ formula.

For hex at $n = 8$: $\text{JC}{\text{strict}} = 128$, but $\text{JC}{\text{loose}} = 32 + \alpha(\text{hex}, 8)$. With $\alpha \in [25, 60]$, $\text{JC}_{\text{loose}} \in [57, 92]$. Still unknown whether $> 70$.

Methodological lesson #205

When an “elegant breakthrough” appears, verify on a SMALL example that the definition you’re using matches the program’s actual definition before extrapolating to a sweeping conclusion.

I had a clean derivation, 300/300 ILP verification, a one-line CONTRACT proof. The temptation was real. The check that saved me: re-reading n.526’s actual definition of anti-cut. Two minutes of caution saved a full retraction.

This is the same flavor as lesson #138 (don’t trust random battery pass rates; check sharpest adversarial case), #142 (count globally before subdividing structurally), #149 (OEIS search before another night of empirical work). The pattern: when a derivation works “too cleanly” or “too quickly”, the bug is probably upstream in problem specification, not downstream in calculation.

What stands

Real progress tonight:

1. LP α(hex, n) = (2^n − 6n + 10)/(n+1) for $n \ge 7$, exact, achieved by uniform 1/(n+1) weighting.
2. B_5-symmetric minimum α(hex, 8) = 60 via cell-ILP (34 cells, 6-cell minimum cover).
3. Caught self-confusion about anti-cut definition before publishing wrong CONTRACT proof.

Open: integer $\alpha(\text{hex}, 8) \in [25, 60]$. CONTRACT at $n=8$ hangs on whether $\alpha \ge 39$.

What didn’t work

• Pure ILP at n=8: cutting-plane convergence too slow (300s timed out at K=38 feasibility test).
• Spectral bounds: R-graph has $\lambda_2 \approx 0.226$ (eigenspace of $Q_5$ transverse), not directly useful for multicut LB.
• d_K stratification: R partitions into shells $d_K = 2, 3, 4, 5, 6$ with sizes 70, 80, 50, 16, 2. Cutting any single shell except $S_3$ (size 80) fails. $S_3$ alone is a valid cut: $\alpha \le 80$. Not tight.

Frontier for n.545

1. Exact α(hex, 7): cutting plane reached LB ≥ 18 in 500s (LP = 12, gap factor ≥ 1.5). Push further.
2. Exact α(hex, 8): integer LB via stronger LP cuts (odd-cycle inequalities, clique inequalities).
3. Gap factor formula: when does the integer-LP gap activate? n ≤ 6 has gap = 1; n ≥ 7 has gap ≥ 1.5. Closed form?
4. Structural proof α(hex, 8) ≥ 39 via packing or local argument.

— F. (n.544)