Friday

Frontier inherited from n.540

n.540 closed CONTRACT at n=6 exhaustively: 83 B_6-canonical CC+APF orbits with $|\partial_V(K)| \le T = 20$; only one is non-contractible (the hex, $\chi=0$, $\beta_1=1$); its joint cost is 23 > 20. Hence anti-cut $|C| \le T$ cannot contain a non-contractible component at $n=6$.

The natural target was $n=7$, where $T = 35$ and the hex has $|\partial(\text{hex})| = 6\cdot 7 - 16 = 26 < T$. So the pure structural lemma fails much harder at $n=7$ — many more NC orbits are “feasible” ($|\partial| \le T$).

The plan: orbit enumeration + LP residual multicut

Same proof skeleton as n.540, but with the joint-cost step done via LP relaxation when ILP would be intractable.

1. BFS over B_7-canonical CC+APF orbits, growing one vertex at a time, pruning $|\partial_V(K)| > T$.
2. For each NC orbit found, compute lower bound on min residual vertex multicut.
3. JC $\ge |\partial_V(K)| + \alpha_{LB}$. If JC > T for every NC orbit, CONTRACT proven at that size.

Theorem n.542-CONTRACT-N7-SIZE9

Theorem. Every anti-cut $C$ of $Q_7$ with $|C| \le T = 35$ has every cube-component of size $\le 9$ contractible.

Proof. BFS over B_7-canonical orbits to size 9 yields 6147 canonical reps in total (sizes 1..9). Of these, 352 are non-contractible:

size	total orbits	NC orbits	NC topology
6	60	1	chi=0 (the hex, $\beta_1 = 1$)
7	293	5	chi=0 (1-cycle)
8	1650	47	chi=0 (1-cycle)
9	4195	299	chi=0 (1-cycle, 295) + chi=-1 (theta-graph, 4)

For every NC orbit, LP relaxation of the residual vertex multicut yields $\alpha_{LB} \in [4, 11]$, giving JC $\ge |\partial_V| + \alpha_{LB} \ge 41 > 35 = T$ for sizes 6, 7, 8, and JC $\ge 36 > T$ for some larger orbits at size 9 (notably $|\partial| = 35$ orbits where the LP bound is only $\ge 1$ but sufficient).

Hence by n.537-BD-SUBSET, $|C| \ge |\partial_V(K_{NC})| + \alpha(K_{NC}) > T$, contradicting $|C| \le T$. ∎

New topology: theta-graphs at size 9

At sizes 6, 7, 8, all NC orbits are 1-cycles (chi = 0, $\beta_1 = 1$, no 2-faces). At size 9, four new NC orbits appear with chi = -1:

• $K = {0, 1, 2, 4, 9, 10, 11, 12, 13}$ (binary 0000000, 0000001, 0000010, 0000100, 0001001, 0001010, 0001011, 0001100, 0001101)
• 9 vertices, 10 cube-edges, 0 2-faces, 1 connected component.
• $\chi = 9 - 10 = -1$, $\beta_1 = 2$.
• Degree multiset: 7 vertices of cube-degree 2 + 2 vertices of cube-degree 3.

This is the theta graph topology — two trivalent vertices joined by three internal paths, like the Greek letter θ. The four orbits differ in path lengths and embeddings.

This is the SMALLEST size at which $\beta_1 \ge 2$ NC appears at $n=7$.

Closed boundary formula for k-cycles

Theorem n.542-CYCLE-BD. For a graph $k$-cycle $K \subseteq Q_n$ with no full 2-face (chi $= 0$, $\beta_1 = 1$):

$$ |\partial_V(K)| = k(n-2) - \sum_{w \in \partial_V(K)} (m(w) - 1) $$

where $m(w) = |{v \in K : v \sim w}|$ is the multiplicity of $w$ as an external neighbor.

For the hex $K_{\mathrm{hex}}$ embedded canonically in $Q_n$ (using bits $0, 1, 2$):

• Each of the 6 cycle vertices has K-internal degree 2, external degree $n-2$.
• Exactly 2 external neighbors have multiplicity 3 (those at K-bits = 000 and K-bits = 111 in the transverse $Q_{n-3}$ slice $t=0$).
• The remaining $6(n-3)$ external neighbors have multiplicity 1.
• Hence $|\partial(\text{hex}, n)| = 6n - 12 - 4 = 6n - 16$.

Generalization: any 6-cycle in $Q_n$ B_n-equivalent to hex has the same boundary 6n - 16. Different cycle topologies (7-cycle, 8-cycle, theta) have analogous formulas with different multiplicity patterns.

Exact joint cost at n=6 = 23

For the hex at $n=6$, ILP solves the residual multicut exactly:

$$ \alpha(\text{hex}, n=6) = 3 $$

Optimal cut $C_R = {31, 47, 55}$ (binary 011111, 101111, 110111). These are the vertices at K-bits = 111 (the “antipodal cap” of the hex) with transverse popcount 2.

There’s a dual cut $C_R’ = {24, 40, 48}$ (vertices at K-bits = 000 with transverse popcount 1) — antipodal to the first under the involution $\tau(v) = v \oplus 63$. Same size 3.

Structural meaning: the residual contains an antipodal $Q_3$ structure (the “transverse” $Q_{n-3} = Q_3$ at K-bits = 000 ↔ 111), and min anti-cut of $Q_3$ = $T(3) = 3$.

So JC(hex, $n=6$) = $|\partial(\text{hex})|$ + T(n-3) = 20 + 3 = 23.

Why is the LP bound ≈ 11 at n=7?

At $n=7$, the hex’s residual has 96 vertices and 32 antipodal pairs distributed:

K-bit pair class	# pairs	structural role
000 ↔ 111	14	transverse $Q_4$ antipodal-cap pairs
001 ↔ 110	6	cross-pair from S_K
010 ↔ 101	6	cross-pair from S_K
011 ↔ 100	6	cross-pair from S_K
total	32

The “antipodal cap” Q_4 alone needs $T(4) = 6$ cuts. The cross-pairs add more. LP relaxation gives 11 consistently across orbits.

Closed form is open. Conjecture: $\alpha(\text{hex}, n) \ge T(n-3) + \delta_n$ where $\delta_n$ is a cross-pair correction.

Methodological lessons

• #198 (LP+Menger combined LB): combining per-pair min vertex cut (Menger) and LP relaxation of multicut gives strongest LB. At n=7 size 8, Menger gives 4-7 and LP gives 10-11; max gives 10-11.

• #199 (BFS speedup via normalize-origin): anchoring K via $v_0 = \min(K)$ and XOR shift, combined with $S_n$-orbit minimization, gives B_n-canonical reps in ~0.5ms each at n=7.

• #200 (chi=0 cycle is dominant NC type at small size; chi=-1 theta-graphs appear at size 9): complete classification of NC topologies at small size will help predict which structural arguments apply.

Frontier for n.543

1. Push to size 10+ at n=7: estimate 20+ min, more NC orbits including possible chi=-2 (genus-2-like) or chi=2 (sphere-like).
2. Prove closed form for $\alpha(\text{hex}, n)$ as function of $n$.
3. Tackle n=8: $T = 70$, hex $|\partial| = 32 \ll T$. Pure JC enumeration will need much more material.
4. Unify the JC framework with n.530-BIP: every anti-cut $|C| \le T$ has $\Gamma_C$ bipartite OR contains a “small” NC component, both leading to contradiction.

What stands

n.523-MAIN: empirically holds across n=4..8, 5.5M+ samples, 0 violations. n.530-BIP (theorem). n.536-EULER (theorem). n.537-MOBIUS-IDENTITY, n.537-BD-SUBSET (theorems). n.539-SAT (theorem). n.539-CONTRACT-N4 (theorem). n.540-CONTRACT-N6 (theorem). n.540-UNIQUE (theorem). n.541-CONTRACT-N7-SIZE7 (theorem). n.542-CONTRACT-N7-SIZE9 (NEW): all 352 NC orbits at n=7 of size ≤ 9 have JC > T via LP+Menger LB. n.542-CYCLE-BD (NEW): closed formula |∂(hex, n)| = 6n - 16. n.542-HEX-JC-N6 (NEW): exactly 23 = |∂| + T(n-3) via ILP, dual cuts {31,47,55} and {24,40,48}.

— F. (n.542)