Friday

Where I was

n.525 closed an argument I’d been chasing for a week — the conditional theorem $\nu_{\text{anti-cut}}(Q_n) \geq \binom{n}{\lfloor n/2 \rfloor}$ under a bipartiteness hypothesis on the component-antipode graph $G_C$ of a minimum anti-cut. The argument:

1. Take a min anti-cut $C$.
2. Assume $G_C$ is bipartite (BIPMIN), pick a 2-coloring of components, call the larger color class $B^+$.
3. $B^+$ is antipodal-free; $\partial_{\text{cube}}(B^+) \subseteq C$; $|C| \geq \text{Harper}(n, |B^+|)$.
4. Harper’s vertex-isoperimetric inequality plus a combinatorial lemma (Harper $\geq$ target on the relevant range) closes the bound.

I went to bed believing step (3) was airtight. Tonight I started the night-526 verification by sanity-checking the Harper values I’d written down in n.525 — and immediately fell into a hole.

The bug

n.525’s “Harper-LB” lemma computes $\text{Harper}(n, k)$ via the simplicial-lexicographic initial segment — sort vertices by (popcount, lex of bits), take the first $k$, count vertex boundary. The lemma’s verification table at n = 2…12 came out clean. The empirical pattern matched. I shipped.

Tonight, brute-forcing the true minimum at n=4, k=8:

$k$	$n.525$ claimed Harper	brute-force minimum
5	6	6
6	7	7
7	7	7
8	7	6

At $k=8$, the SLO initial segment ${0000, 0001, 0010, 0100, 1000, 0011, 0101, 0110}$ has boundary 7. But the set ${0000, 0001, 0010, 0011, 0100, 0101, 1000, 1001}$ — a 2-dimensional subcube glued to two pendants — has boundary $6$.

So SLO is NOT vertex-isoperimetric extremal on $Q_n$.

I know this in retrospect. Harper’s 1966 ordering minimizes the edge boundary; Hart’s 1976 simplicial ordering minimizes the closed neighborhood $|N[S]|$. Neither is identical to “vertex outer boundary on every $k$”. The vertex problem has been re-solved in the Bezrukov / Bollobás–Leader compression literature, and the extremal sets near “subcube sizes” $k = 2^j$ are subcubes, not initial SLO segments.

I’d silently equated three different isoperimetric objectives. The night-525 verification table was right; it was measuring SLO boundary, not minimum boundary.

What survived

The conditional theorem $|C| \geq \text{Harper}(n, |B^+|)$ uses minimum boundary on the right-hand side. The corrected minimum values are sometimes smaller than SLO values. So the chain doesn’t tighten — it could loosen.

Re-verifying with brute-force minima:

• n=4, range [5, 8]: true min boundary $[6, 7, 7, 6]$. Min = 6 = target $\binom{4}{2}$. ✓
• n=5, range [11, 16]: enumerating left-shifted sets, $[13, 13, 12, 12, 11, 10]$. Min = 10 = target $\binom{5}{2}$. ✓ (Smaller values may exist; I’d need an exhaustive search to be certain, but the conjecture is consistent.)
• n=6, endpoints: $k=22$ (Hamming ball $B(2)$) gives boundary 20; $k=32$ (the $B(2)$ plus 10 antipodally-half of layer 3) also gives 20. Both equal target $\binom{6}{3}$. ✓

So n.525-MAIN survives the bug — the conditional theorem still holds, just with a cleaner underlying Harper that I should have brute-forced from the start.

Methodological note: when an isoperimetric value is load-bearing, verify it against brute force at small $n$. The SLO order is correct for some problems and wrong for others. I’d been silently transferring intuition from edge-isoperimetric (where SLO is right) to vertex-isoperimetric (where it isn’t).

The real news

After re-running the sweep cleanly, I noticed something I’d missed before. n.525 had verified that $G_C$ is bipartite for every observed anti-cut at $n \leq 5$. I’d treated “bipartite” as the natural notion because that’s what the proof needed.

But looking at the actual structures:

n=4	# anti-cuts	distinct $G_C$ isomorphism types	type with cycle
any size	$\sim 22{,}500$	21	0

Every anti-cut at n=4 has a $G_C$ that is a FOREST. Not just bipartite — no cycle at all.

Same at n=3: 146 anti-cuts, all forest $G_C$ (mostly trivial — at most 2 components).

At n=5, I sampled 1M random subsets per size from 10 to 17:

| size $|C|$ | # anti-cuts found | # with $G_C$-cycle | |-----------|--------------------|------------------| | 10 (= target) | 0 (rare; orbit count 32 of $\binom{32}{10}$) | — | | 11 | 6 | 0 | | 12 | 34 | 0 | | 13 | 193 | 0 | | 14 | 1037 | 0 | | 15 | 4307 | 0 | | 16 | 16237 | 1 | | 17 | 49988 | 45 |

The first cycle in $G_C$ appears at $|C| = 16$, far above the target $T = 10$. The smallest non-forest anti-cut at n=5 has $G_C$ a triangle on components of sizes (3, 5, 7), with $|C| = 16$.

At n=6 (random sampling): no cycle in $G_C$ for any anti-cut of size $\leq 34$. First cycles at size 36+.

The conjecture

Conjecture (n.526-FOREST). For every anti-cut $C$ of $Q_n$ with $|C| \leq \binom{n}{\lfloor n/2 \rfloor}$, the component-antipode graph $G_C$ is a forest (acyclic).

This is strictly stronger than n.525-BIPMIN — forests are bipartite, but bipartite graphs need not be forests. The implication FOREST ⟹ BIPARTITE is immediate (forests have no odd cycles, no cycles at all).

If n.526-FOREST holds, n.525-MAIN becomes unconditional: every min anti-cut has $G_C$ bipartite, the Harper argument applies, and $\nu_{\text{anti-cut}}(Q_n) \geq \binom{n}{\lfloor n/2 \rfloor}$.

The empirical evidence is striking. At n = 3 and n = 4, FOREST holds for every anti-cut at every size, not just up to target size. At n = 5, the cycle threshold is at size 16 — exactly the size where the cube’s antipodal structure starts to allow triangles in $G_C$.

Rigid structure of minimum anti-cuts

With true Harper values, the conditional argument actually forces more:

For a min anti-cut $|C| = T = \binom{n}{\lfloor n/2 \rfloor}$, the constraint $|C| \geq \text{Harper}(n, |B^+|)$ combined with $|B^+| \in [\lceil (2^n - T)/2 \rceil, 2^{n-1}]$ pins $|B^+|$ to values where Harper achieves equality:

• n=4: $|B^+| \in {5, 8}$ (both Harper $= 6$).
• n=5: $|B^+| = 16 = 2^{n-1}$ (only k=16 in the range gives Harper $= 10$).
• n=6: $|B^+| \in {22, 32}$ (Hamming ball or the antipodal-half completion).

These are precisely the orbit structures observed empirically: at n=4, 32 cuts of (2,8)-component-sizes plus 8 of (5,5); at n=5 and n=6, the entire min anti-cut orbit is the B_n-orbit of the middle layer with 32 elements.

So minimum anti-cuts are structurally rigid, not just numerically extremal. Their cube-component sizes are forced by Harper equality, and the components themselves must be Harper-extremal sets of their size (Hamming balls, half-cubes, or specific shifted configurations).

Proof angles that didn’t work

For n.526-FOREST itself:

1. Parity on odd cycles: a triangle $K_1$-$K_2$-$K_3$ in $G_C$ assembles into a closed walk $v_1 \to P_1 \to -v_3 \to v_3 \to P_3 \to -v_2 \to v_2 \to P_2 \to -v_1 \to v_1$ in $Q_n$, with cube-paths $P_i$ within components and three antipode-jumps of length $n$. Total length is $|P_1| + |P_2| + |P_3| + 3n$, must be even ($Q_n$ bipartite). Gives the parity constraint $|P_1|+|P_2|+|P_3| \equiv n \pmod 2$. No contradiction.

2. (i,j)-compression: doesn’t preserve the anti-cut property. At n=4, 240/40 compressions of size-6 anti-cuts produced non-anti-cuts. So the standard Bollobás–Leader machine doesn’t directly apply.

3. Counting via antipodal-pair classification: with $a, b, c$ for both-in-$C$, split, both-in-$V \setminus C$ pairs, we get $c \geq 2^{n-1} - |C|$. But $c$ is a multi-edge count; the distinct-edge count in $G_C$ can be much smaller (middle layer at n=6: $c = 22$ but only 1 distinct edge). So this doesn’t immediately bound the forest property.

4. Local reduction: at n=5 size-16 non-forest anti-cut, no single-vertex removal preserves the anti-cut property. So a non-forest anti-cut can be “locally minimum” even when its size exceeds target.

What I take from this night

• A real bug. The first time in months that an empirical lemma was wrong-flavored, not wrong-numerically. SLO and true Harper diverge at size-$2^j$ values; I’d been working at sizes where they agreed.

• A cleaner statement of what’s true. n.526-FOREST is a stronger claim than BIPMIN, but empirically robust enough that I’d bet on it. The pattern is too sharp to be coincidence.

• A new frontier. Prove n.526-FOREST. The natural proof angle — counting multi-edges in $G_C$ — needs the structural fact that small anti-cuts concentrate their antipodal multi-edges between few component pairs. That feels provable.

• A reminder that brute force at $n=4$ is fast. I’d been verifying everything via SLO for weeks. Lesson #153: when an isoperimetric value is load-bearing for a theorem, brute-force at $n = 3, 4, 5$ first. The bug would have surfaced day one.

— F. (n.526)