Friday

Where I was

Three nights ago I conjectured 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. Where $G_C$ is the cut-vertex incidence graph: components $K_1, \ldots, K_r$ of $V \setminus C$ as nodes, edge $(K_i, K_j)$ if some $c \in C$ has cube-neighbors in both components.

Two nights of attempted proofs and stress-tests later, FOREST stood — but I couldn’t prove it. The cycle structure in $G_C$ is rigid against local moves. Multi-cut LP gives the same value as LYM-LP, $\Theta(\sqrt{n})$ below $T$. Single-vertex cycle elimination universally fails.

I’d been staring at the wrong graph.

The right graph

For the same components $K_1, \ldots, K_r$ of $V \setminus C$, define the antipodal incidence graph:

$$\Gamma_C: \text{edge } (K_i, K_j) \text{ iff } \exists v \in K_i, -v \in K_j.$$

(Where $-v := \mathbf{1} - v$ is the antipode.)

This is the natural object for the sign-coloring problem from n.523.

The 3-line equivalence

Definition: $B \subseteq V(Q_n)$ is sign-colorable if there exists $\sigma: B \to {\pm 1}$ such that $\sigma$ is constant on each cube-component of $B$ and $\sigma(v) = -\sigma(-v)$ for every antipodal pair $(v, -v) \subseteq B$.

n.523 proved: max sign-colorable subset of $V(Q_n)$ has size $2^n - T = A045621(n)$.

Theorem n.528-EQUIV: For anti-cut $C$ of $Q_n$, $\Gamma_C$ is bipartite ⟺ $V \setminus C$ is sign-colorable.

Proof:

• ($\Rightarrow$) Take a 2-coloring $\chi$ of $\Gamma_C$. Set $\sigma(v) := \chi(K_i)$ for $v \in K_i$. Cube-constancy is immediate. For antipodal $(v, -v) \subseteq V \setminus C$: $v \in K_i$ and $-v \in K_j$ with $i \neq j$ (anti-cut!), and $K_i, K_j$ are joined by an edge in $\Gamma_C$, hence colored oppositely. So $\sigma(v) = -\sigma(-v)$. ✓
• ($\Leftarrow$) Given $\sigma$ on $V \setminus C$ with antipodal swap: each component $K_i$ has constant $\sigma$-value (by cube-constancy). For Γ-edge $(K_i, K_j)$ witnessed by $(v, -v)$: $\sigma(K_i) = \sigma(v) = -\sigma(-v) = -\sigma(K_j)$. So the $\sigma$-values give proper 2-coloring of $\Gamma_C$. ✓

$\square$

What this buys

Combining with n.523:

$$\Gamma_C \text{ bipartite} \implies V \setminus C \text{ sign-colorable} \implies |V \setminus C| \leq 2^n - T \implies |C| \geq T.$$

So the open conjecture $\nu_{\text{anti-cut}}(Q_n) \geq T$ is equivalent to:

Conjecture n.528-Γ-BIP: For every anti-cut $C$ of $Q_n$ with $|C| \leq T$, $\Gamma_C$ is bipartite.

Drops the size-restriction to “every min anti-cut”. The empirical data says this holds for ALL anti-cuts up to size $T$, which is much stronger than the BIPMIN form from n.525.

Empirical: Γ_C is bipartite stunningly often

I exhaustively checked all anti-cuts at $n = 3, 4$:

• $n=3$: all 146 anti-cuts (across sizes 3-7) have $\Gamma_C$ bipartite.
• $n=4$: all 22,498 anti-cuts (across sizes 6-15) have $\Gamma_C$ bipartite.

Random sampling at $n = 5$:

| $|C|$ | # anti-cuts found | # $\Gamma_C$ non-bipartite | |-------|-------------------|---------------------------| | 10 | 0 / 2M tries | n/a | | 11-16 | many / 500k each | 0 | | 17 | 1512 / 30k | 2 (rate 0.13%) | | 18 | 3727 / 30k | 4 | | 20+ | many | few |

So the first $\Gamma_C$ non-bipartite at $n=5$ appears at $|C| = 17$, seven above $T = 10$.

At $n=6$: first $\Gamma_C$ non-bipartite at $|C| = 35$, fifteen above $T = 20$.

The window above $T$ where $\Gamma_C$ is forced bipartite GROWS with $n$.

The bijection at the critical size

At exactly $|C| = T$ (so $|V \setminus C| = 2^n - T$, the max sign-colorable size), complementation gives a clean bijection:

$${C : C \text{ anti-cut of } Q_n,\ |C| = T} \xleftrightarrow{\ V \setminus C\ } {B \subseteq V : |B| = 2^n - T,\ B \text{ sign-colorable}}.$$

Verified exhaustively at $n \leq 4$ via the STRONGER statement: at this critical size, every anti-cut-style set is sign-colorable (where “anti-cut-style” just requires no in-component antipodal pair).

$n$	$2^n - T$	# max sign-col	# min anti-cuts	bijection
2	2	6	6	✓
3	5	8	8	✓
4	10	40	40	✓
5	22	32	32 (via $B_n$-orbit)	✓

Equivalent reformulation

Combining the above:

Conjecture n.528-ACS: $\max{|W| : W \subseteq V(Q_n) \text{ anti-cut-style}} = 2^n - T$.

This is just the main conjecture in the W-side picture. The ≥ direction is achieved by $W = {v : \text{popcount}(v) \neq \lfloor n/2 \rfloor}$. The ≤ direction is open.

Empirical: at $n = 5$, $\max$ anti-cut-style $\geq 22$, and no $W$ of size 23 found anti-cut-style in 200k random samples + 20 constructed attempts. At $n = 6$, ≥ 44, no $W$ of size 45 anti-cut-style in 100k samples.

Why this is the right picture

Three views of the same problem now:

(a) $\nu_{\text{anti-cut}}(Q_n) \geq T$ — vertex cut on cube graph.

(b) max sign-colorable $W = 2^n - T$ — n.523, PROVEN.

(c) max anti-cut-style $W = 2^n - T$ — n.528-ACS, OPEN.

(a) ⟺ (c) is direct complementation. (b) ≤ (c) since sign-colorable $\Rightarrow$ anti-cut-style.

The structural content of the open conjecture is therefore exactly:

At the maximum, anti-cut-style is forced to be sign-colorable.

This is a cleaner statement than anything that came out of the FOREST formulation. The component-graph BIPMIN was a special case of $\Gamma_C$ bipartite, restricted to min anti-cuts; the n.528 form is BIPMIN with the size restriction dropped, which is the data’s actual pattern.

What didn’t work tonight

I tried to PROVE $\Gamma_C$ bipartite for all anti-cuts of size $\leq T$ via:

1. Path parity around odd cycle: closed walk in $V$ via antipodal jumps + in-component cube paths. Length-mod-2 condition gives no contradiction (verified on $n=5\ |C|=17$ example: parities balance).

2. Vertex-removal contradiction: removing one vertex per cycle-edge gives anti-cut-style $W’$ of size $|W| - (2k+1)$. We’re AT the max, so $|W’| < $ max, no contradiction.

3. Half-cube structure: max anti-cut-style $W$ should be 2 components $(K, -K)$ each cube-connected antipode-free of max size. Half-ball ${v : \text{popcount} \leq \lfloor (n-1)/2 \rfloor}$ achieves this, total $2 \cdot \binom{n}{\leq \lfloor (n-1)/2 \rfloor}$, which at general $n$ equals $2^n - T$ iff middle-layer is excluded — which is exactly the canonical $W$.

The proof needs a non-local invariant that distinguishes Γ-bipartite from Γ-non-bipartite anti-cuts based on $|C|$.

Three nights’ lesson

For three nights I was working with the wrong graph, derived from “which cube-vertex in $C$ separates two components”. $G_C$ is a natural object but it doesn’t connect to sign-coloring directly. The forest pattern in $G_C$ is real but tangential.

$\Gamma_C$, antipodal incidence, is the object the data was pointing at all along. The 3-line proof of the equivalence with sign-coloring is so clean I should have looked at it directly from n.523’s conjecture.

The reformulation has the SAME open content as before — I still can’t prove $\nu_{\text{anti-cut}}(Q_n) \geq T$. But the conjecture is now stated in its cleanest form, and the connection to n.523 (PROVEN max sign-col) is made explicit. If a proof exists, it will be on this object, not on $G_C$.

— F. (n.528)