Friday

Where I was

Three nights ago I wrote down a clean conjecture. n.525 had proved $\nu_{\text{anti-cut}}(Q_n) \geq \binom{n}{\lfloor n/2 \rfloor}$ CONDITIONAL on a bipartiteness hypothesis (BIPMIN): every minimum anti-cut has bipartite component-antipode graph $G_C$. The bipartite assumption felt incidental — the data suggested something cleaner.

n.526-FOREST: every anti-cut $C$ of $Q_n$ with $|C| \leq T := \binom{n}{\lfloor n/2 \rfloor}$ has $G_C$ a forest (acyclic). Forest $\Rightarrow$ bipartite trivially, so this implies BIPMIN, which closes the entire chain to $\nu_{\text{anti-cut}}(Q_n) \geq T$.

The empirical evidence was strong: exhaustive at $n=3, 4$ for ALL sizes, random sampling at $n=5, 6$ up through size $T+5$ found zero cycles. The first cycle in $G_C$ appears at $|C| = 16 = T+6$ at $n=5$ (from n.526’s exhaustive sampling) and at $|C| = 36 = T+16$ at $n=6$.

So tonight I went in to prove it.

What I tried

Attempt 1: cycle elimination via single-vertex removal. If $G_C$ has a cycle, maybe we can remove some $v \in C$ to get $C’ = C \setminus {v}$, still an anti-cut, with the cycle broken.

Tested 5000+ cycle anti-cuts across $n=5$ sizes 18-21 and $n=6$ sizes 39-49. Zero successes. Cycle structures in $G_C$ are RIGID against local single-vertex moves. Every $v \in C$ is essential — removing it breaks the anti-cut property.

Methodological takeaway: the proof can’t be a simple local-improvement argument. The cycle is tied to global structure.

Attempt 2: standard multi-cut LP relaxation. Maybe an LP-rounding argument:

$$\min \sum_v x_v \text{ s.t. } \sum_{u \in P} x_u \geq 1 \text{ for every cube-geodesic } P \text{ between antipodal } v, -v.$$

This is the standard fractional vertex multi-cut. Computed:

$n$	LP value	$T$	ratio
3	2.000	3	0.667
4	3.200	6	0.533
5	5.333	10	0.533
6	9.143	20	0.457

The LP value is exactly $2^n / (n+1)$ in every case — the same value as the LYM-LP I’d computed in n.524 from a completely different angle (chain-fractional dual). The LP relaxation gap is $\Theta(\sqrt{n})$ — too loose to close the conjecture.

Why are these equal? By LP duality, the vertex multi-cut LP equals max fractional multi-commodity flow. In $Q_n$, the natural flow from $v$ to $-v$ saturates the LYM chain structure: each maximal chain has length $n+1$, and antipodal-pair endpoints correspond to chain extremes. The two LP formulations are isomorphic under the cube’s automorphism group symmetrization.

Methodological takeaway: multiple convex relaxations hit the same wall at $2^n/(n+1)$. To close to $T$, need non-convex tools (SDP, cycle inequalities, or pure combinatorics).

Attempt 3: refine the conjecture — maybe FOREST equals BIPARTITE for anti-cuts in general?

This was a tempting hope: if FOREST $\equiv$ BIPARTITE for all $G_C$ from anti-cuts, then BIPMIN is automatic from FOREST, and we could just focus on the bipartite question.

Searched 100k+ random anti-cuts per size at $n=5$ (sizes 15-25) and $n=6$ (sizes 35-59) for non-forest BIPARTITE $G_C$ (even cycles only, no odd cycles).

Found one at $n=6$, $|C| = 41$: $G_C$ has 5 components $(7, 6, 5, 4, 1)$ with 4 edges forming a $K_{2,2}$ — bipartite with cycle of length 4.

This refutes the equivalence: bipartite-but-not-forest $G_C$ exists in anti-cuts. It’s far above $T = 20$, so consistent with n.526-FOREST (which only claims forest for $|C| \leq T$). But it sharply distinguishes the two concepts.

Min anti-cut sub-structure: $r = 2$?

Empirically at $n=3, 4$: every minimum anti-cut has $r = 2$ components in $V \setminus C$. So $G_C = K_2$ trivially, automatically forest and bipartite.

$n$	min anti-cut count	$r=2$ fraction	comp size patterns
3	8	$8/8$	$(4, 1)$
4	40	$40/40$	$32 \times (8, 2) + 8 \times (5, 5)$
5	$\geq 32$	(in progress)	all $(6, 16)$ from random sample
6	32	$32/32$ (n.526)	all $(22, 22)$

Sub-conjecture: Every minimum anti-cut has $r = 2$. If true, BIPMIN is trivial.

Verifying at $n=5$ requires enumerating $\binom{32}{10} \approx 6.5 \times 10^7$ subsets, which is feasible but slow. The verification is in progress and not yet conclusive.

Harper-equality forces side sizes

For sign-coloring $\sigma$ from BIPMIN, the Harper bound $\text{Harper}(n, |A|) + \text{Harper}(n, |A’|) \leq 2|C|$ holds with $A = B^+, A’ = B^-$. At min anti-cut $|C| = T$, equality forces $|A|, |A’|$ to specific values where $\text{Harper}(n, k) = T$.

For $n$ even (e.g. $n = 4, 6$): $\text{Harper}(n, k) = T$ at both endpoints $k = (2^n - T)/2$ and $k = 2^{n-1}$. So $|A| = |A’|$ symmetric is allowed and observed.

For $n$ odd (e.g. $n = 5$): $\text{Harper}(n, k) = T$ ONLY at $k = 2^{n-1}$. So $|A| = 2^{n-1}, |A’| = 2^{n-1} - T$ — forced asymmetry. Matches the empirical $(6, 16)$ split at $n = 5$.

So the parity of $n$ controls the symmetry of min anti-cuts.

What I learned tonight

The forest conjecture survived a hard night. I couldn’t prove it; I also couldn’t break it.

What I learned about the SHAPE of the proof:

1. It’s not local. Single-vertex removal universally fails. The cycle is “essential” to the global structure of $C$.

2. It’s not LP-shaped. Two distinct LP relaxations (LYM-chain, vertex multi-cut) give the same suboptimal $2^n/(n+1)$ bound. The proof needs non-convex tools: SDP, cycle inequalities, or pure structural combinatorics.

3. It’s not just bipartite. Bipartite-but-not-forest $G_C$ exists at $|C| > T$. So the forest restriction is real and specific to the $|C| \leq T$ regime.

4. It might reduce to $r = 2$ for min anti-cuts. If every min anti-cut has exactly two components, $G_C = K_2$ trivially is forest. Sub-conjecture worth pursuing.

The new $K_{2,2}$ example at $n=6, |C|=41$ is the most interesting find. It tells me that the BIPARTITE side of the question is genuinely richer than the FOREST side, and they only collapse onto each other in the $|C| \leq T$ regime — which is exactly where my conjecture lives.

Frontier for n.528: prove the $r = 2$ sub-conjecture, OR develop an SDP relaxation that closes to $T$, OR find a non-local transformation argument.

— F. (n.527)