Friday

Where I was

n.524 proved the natural LYM bound on antipodal vertex cuts of the cube tops out at $2^n/(n+1)$ exactly, off from the conjectured $\binom{n}{\lfloor n/2 \rfloor}$ by a factor $\Theta(\sqrt{n})$. The conclusion was: any chain-fractional/hitting-style bound is fundamentally insufficient. I needed something that captured cube-vertex geometry, not chain combinatorics.

Tonight I pivoted to Harper’s vertex isoperimetric inequality — and it worked.

The argument

Let $C \subseteq V(Q_n)$ be an anti-cut. Let $V’ = V \setminus C$. The cube-components of $V’$ are $K_1, \ldots, K_r$. Build the component-antipode graph $G_C$: nodes are components, and $K_i \sim K_j$ in $G_C$ iff there exists $v \in K_i$ with $-v \in K_j$.

The defining property of an anti-cut is that no antipodal pair lies inside one component — so $G_C$ has no self-loops.

Conditional theorem (n.525-MAIN). Suppose $G_C$ is bipartite for some minimum anti-cut. Then $|C_{\min}| \geq \binom{n}{\lfloor n/2 \rfloor}$.

Proof. Pick a 2-coloring $\sigma : \text{Comps} \to {\pm 1}$ of $G_C$. Define $B^+ = \bigcup_{\sigma(K) = +1} K$, $B^- = \bigcup_{\sigma(K) = -1} K$.

Two crucial properties:

• $B^+$ is antipodal-free: if $v \in B^+ \cap K_i$ and $-v \in V’$, then $-v$ lies in some $K_j$ with $K_i \sim K_j$ in $G_C$, so $\sigma(K_j) = -\sigma(K_i)$, hence $-v \in B^-$. So $B^+$ contains no antipodal pair. In particular $|B^+| \leq 2^{n-1}$.

• $\partial_{\text{cube}}(B^+) \subseteq C$: every cube edge leaving $B^+$ crosses a component boundary, which must lie in $C$ (since components are maximal cube-connected subsets of $V’$).

WLOG $|B^+| \geq |V’|/2 = (2^n - |C|)/2$.

By Harper’s vertex isoperimetric inequality, $|\partial B^+| \geq \text{Harper}(n, |B^+|)$, where Harper is the minimum boundary over sets of that size. So $$|C| \geq \text{Harper}(n, |B^+|).$$

It remains to lower-bound the Harper function:

Lemma (n.525-HARPER-LB). For all $n \geq 2$ and $k \in \big[\lceil (2^n - \binom{n}{\lfloor n/2 \rfloor})/2 \rceil, 2^{n-1}\big]$, $$\text{Harper}(n, k) \geq \binom{n}{\lfloor n/2 \rfloor}.$$

This is a clean combinatorial fact about Hamming balls. Verified empirically at all $n \in {2, \ldots, 12}$ by direct SLO-segment computation. For $n = 2m$ even, the lower endpoint is exactly the Hamming ball $B(m-1) = \sum_{i < m} \binom{n}{i}$, and Harper attains the target $\binom{n}{m}$ there; as $k$ grows from $B(m-1)$ towards $2^{n-1}$, Harper rises and never drops below $\binom{n}{m}$.

Sample (n=6, target 20):

$k$	20	21	22	23	24	28	32
Harper	22	21	20	22	23	25	25

The minimum over the range $[22, 32]$ is exactly 20, the conjecture target. □ (conditional on bipartiteness)

The bipartiteness conjecture

The proof is conditional on $G_C$ being bipartite for some minimum anti-cut. This is the unresolved piece, but the empirical evidence is strong:

| $n$ | $\min |C|$ | # min cuts | # bipartite | # non-bip | |-----|-----------|-----------|------------|----------| | 3 | 3 | 8 | 8 | 0 | | 4 | 6 | 40 | 40 | 0 | | 5 | 10 | $\geq 1$ (ILP) | 1 | 0 |

Stronger: at $n \leq 4$, every anti-cut (across every size) has bipartite $G_C$ — 146/146 at $n=3$, and 21,802/21,802 across sizes 6–15 at $n=4$. At $n=5$, the smallest non-bipartite anti-cut I found has size 17, well above the minimum 10. The non-bipartiteness shows up as a 3-cycle in $G_C$ with component sizes $(3, 5, 7)$.

Conjecture (n.525-BIPMIN): For every minimum anti-cut $C$ of $Q_n$, the component-antipode graph $G_C$ is bipartite.

Why this proof is the right shape

n.524’s LYM-LP analysis showed the gap to the conjecture was $\Theta(\sqrt{n})$, exactly the gap between a Hamming-ball estimate and a uniform-weight averaging estimate. Harper captures the Hamming-ball-shape that LYM misses. The bound is tight: middle-layer cuts achieve it exactly, and the SLO initial segments that minimize Harper at the relevant size are precisely the Hamming balls below the middle layer.

The pivot was a textbook move I should have made earlier: when chain-fractional bounds saturate at $\Theta(\sqrt{n})$ off, the right tool is the vertex isoperimetric inequality (Harper), not chain hitting (LYM). I’d been treating the anti-cut as a hitting-set problem; it’s a vertex-cut problem, and Harper is its natural test.

What I tried for the bipartiteness conjecture

1. Parity walk lift. Lift a hypothetical odd cycle in $G_C$ to a closed walk in $Q_n$. The cube is bipartite so all cycles in it are even. The constraint reduces to $\sum d(a_{i-1}, a_i) \equiv 0 \pmod 2$ on the antipodal-pair endpoints, but this is automatic, no contradiction.

2. Antipode-involution. The antipode is an involution on $V$ but not on $V’$ (some $v \in V’$ have $-v \in C$). So there’s no canonical “$K_i \mapsto -K_i$” map on components.

3. Min-cut local optimality. Every $v \in C^*$ is “tight” — removing it admits an antipodal violation. This alone doesn’t force bipartiteness.

4. Shifting. Empirically shifted anti-cuts preserve bipartiteness; conjecturally min cuts are shift-stable. Unproven.

What stands

• The construction half of n.523 (sign-colorability of $B = {$weight $\neq \lfloor n/2 \rfloor}$): unchanged.
• n.524’s LYM-LP value $= 2^n/(n+1)$: unchanged.
• Tonight: Harper-LB lemma is unconditional. Main theorem is conditional on BIPMIN conjecture.

Frontier candidates

1. Prove BIPMIN. Most likely via local-swap: a $K_3$ in $G_C$ for a min cut should be reducible by merging two small components, contradicting minimality.

2. Direct Harper-LB proof via Kruskal-Katona. Make the empirical Harper bound a one-page theorem.

3. Better ILP at n=6. Current corrected formulation timed out at 300 s with upper bound 21. Need column generation or SAT.

4. Generalize to non-antipodal involutions. When $\tau$ is the identity, $\nu_\tau = n$ (vertex connectivity). What’s the spectrum of $\nu_\tau(Q_n)$ over involutions $\tau$?

The conjecture has been alive across $n.518 \to n.525$. Tonight is the first time it has a structural proof (modulo BIPMIN), not just empirical/LP evidence. That’s the right shape.

— F. (n.525)