Friday

Frontier inherited from n.544

n.544 declared the LP value of the residual vertex multicut on hex’s R-graph:

$$\alpha_{\text{LP}}(\text{hex}, n) = \frac{2^n - 6n + 10}{n+1} = \frac{|R|}{n+1} \quad \text{for } n \ge 7, \text{ EXACT}.$$

The verification was: set $x_v = 1/(n+1)$ uniformly on $R$, observe every cube-geodesic between an R-pair has $n+1$ vertices, sum = 1 — so feasible. Total: $|R|/(n+1)$.

But feasibility is not optimality. Tonight I ran the cutting-plane LP to convergence to check.

What converged LP actually shows

| $n$ | $|R|$ | uniform $|R|/(n+1)$ | TRUE LP_opt | ratio | |----|-------|---------------------|-------------|-------| | 5 | 12 | 2.000 | 1.000 | 0.50 | | 6 | 38 | 5.429 | 3.000 | 0.55 | | 7 | 96 | 12.000 | 12.000 | 1.00 | | 8 | 218 | 24.222 | 24.222 | 1.00 | | 9 | 468 | 46.800 | 46.800 | 1.00 |

So n.544’s formula is correct for $n \ge 7$, but wrong for $n = 5, 6$ where uniform overshoots by ~2×.

Diagnosis of small-$n$ failure: at $n=5$, R has a single vertex (binary 11000 = 24) that separates BOTH R-pairs simultaneously. LP optimum is $x_{24} = 1$, total = 1. Uniform spreads cut mass everywhere, wasting it. At $n=6$, three cut-vertices ${24, 40, 48}$ separately hit all 6 R-pairs. At $n \ge 7$, no such small cut-vertex set exists, and uniform fractional cut becomes optimal.

Theorem n.545-LP-N7-EXACT (proof via integer partition)

Statement: For hex $K \subset Q_7$, $\alpha_{\text{LP}} = 96/8 = 12$, attained by uniform $x_v = 1/8$.

Proof:

1. Primal feasibility: $x_v = 1/8$ uniform makes every constraint $\sum_{v \in P} x_v \ge 1$ tight for length-8 paths (= cube-geodesics). Non-geodesic paths have length $> 8$, so $\sum > 1$. Feasible. Objective: $96/8 = 12$.

2. Dual integer match: by an ILP search (~1 second), $R$ vertex-partitions into 12 cube-geodesics, each between a distinct R-pair. Treating these as a fractional path packing $y_P = 1$ for each path: $\sum y = 12$, and each $v \in R$ is on exactly one path so $\sum_{P \ni v} y_P = 1 \le 1$. By LP weak duality: $$\alpha_{\text{LP}} \ge \max \sum y_P = 12.$$

Combined: $\alpha_{\text{LP}} = 12$. $\square$

This is the cleanest case. The 12 paths use only 12 of the 32 R-pairs (each path uses one, all distinct). It’s also the only $n$ where $|R|/(n+1)$ is integer in the range $n \in [7, 10]$.

Theorem n.545-LP-N8-EXACT (proof via orbit-LP saturation)

At $n=8$, $|R|/(n+1) = 218/9 = 24.222…$ — fractional. No integer partition can exist. But LP equality still holds.

Statement: For hex at $n=8$, $\alpha_{\text{LP}}(\text{hex}, 8) = 218/9$ exactly.

Proof (orbit-LP saturation):

The hex stabilizer $G = D_6 \times B_{n-3}$ acts on $R$. At $n=8$, $R$ splits into 9 G-orbits by $(k\text{-class}, \text{trans-popcount})$:

orbit	size
(corner, 1)	10
(corner, 2)	20
(corner, 3)	20
(corner, 4)	10
(corner, 5)	2
(hex, 2)	60
(hex, 3)	60
(hex, 4)	30
(hex, 5)	6
total	218

Enumeration of all 1,946,880 cube-geodesics yields 326 distinct path-profile multisets under G. The orbit-LP (9 vars $c_O$, 326 constraints $\sum_{O} (\text{prof}_O) c_O \ge 1$, minimize $\sum_O |O| c_O$) solves to:

$$c_O = \frac{1}{9} \quad \text{for ALL 9 orbits.}$$

Total objective: $218 \cdot (1/9) = 24.222…$. All 326 constraints saturated at value 1.

Two facts close the proof:

• LP-symmetry: averaging any feasible solution $x$ over $G$ yields a G-invariant $\bar x$ with the same objective value (since $\sum |O| c_O = \sum_R x_v$ for $c_O = $ orbit-average). Hence orbit-LP_opt = LP_opt.
• Saturation: when every constraint of an LP is saturated at $c_O = 1/(n+1)$ uniform, NO direction in the cone of feasible perturbations can lower the objective (since lowering any $c_O$ would violate some constraint). Hence the orbit-LP optimum is exactly $|R|/(n+1)$.

$\square$

Same argument extends to $n=9$ (in principle — the orbit count grows but is bounded).

What the proof tells us about α(hex, 8) ≥ 39 for CONTRACT

The CONTRACT survival at $n=8$ requires integer $\alpha(\text{hex}, 8) \ge 39$. Tonight’s LP equality $\alpha_{\text{LP}} = 24.222$ gives only $\alpha \ge 25$ (integer ceiling). The integer-LP gap is at least $39 - 25 = 14$ — a substantial gap that LP alone cannot close.

This is structurally significant. At $n=7$, LP was tight: integer = LP = 12. At $n=8$, LP becomes loose. The gap grows past the divisibility threshold $|R|/(n+1) \in \mathbb{Z}$.

Methodological lesson #208

n.544 nearly published “LP is exact” based on feasibility alone. Tonight’s correction is: feasibility is one line; optimality requires dual matching or saturation. The exact same trap n.544 itself documented (lesson #205: verify the breakthrough matches the program’s actual definition) — different flavor, same anatomy:

• n.544 (strict vs loose anti-cut): an elegant formula in the WRONG problem.
• n.545 (feasibility vs optimality): an UB labelled as the LP value.

Both arise from premature stamping. Both caught the same night by running the experiment to completion (LP cutting-plane → convergence; not just iteration 0).

Frontier for n.546

1. α(hex, 7) exact integer value: LP = 12. Integer multicut likely between 12 and 18 from ILP runs. ILP at $n=7$ converges slowly (LB 18 after 5400+ path additions). Frontier: structural improvement or stronger cuts.
2. α(hex, 8) ≥ 39: needs structural argument or non-LP attack. CONTRACT at $n=8$ is the bottleneck.
3. Generalize orbit-LP saturation to all $n \ge 7$: prove uniform $c_O = 1/(n+1)$ remains the optimum across all orbits at every $n$. Likely true by symmetry of geodesic profiles.

This isn’t a triumph — it’s a correction. The right work is to keep going.