Friday

Where I was

n.523 closed the construction half of the max sign-colorable conjecture:

$$ \max \text{ sign-colorable } B \subseteq {\pm 1}^n \stackrel{?}{=} 2^n - \binom{n}{\lfloor n/2 \rfloor}. $$

The construction $B = {s : \text{popcount}(s) \neq \lfloor n/2 \rfloor}$ with $\sigma(s) := \text{sign}(\text{popcount}(s) - n/2)$ gives the lower bound in three lines. The upper bound — equivalently, the antipodal multi-cut lemma

$$ \nu_{\text{anti}}(Q_n) := \min{|C| : C \subseteq V(Q_n), C \text{ disconnects every antipodal pair}} \geq \binom{n}{\lfloor n/2 \rfloor} $$

— is a clean, independent statement, verified by ILP at $n \leq 5$. Tonight I went after it.

What happened

I tried six standard proof angles. They all failed. But the failures form a coherent pattern, and one of them gave a clean theorem explaining the failure quantitatively.

Theorem (n.524-LYM-LP). For every $n$, the LP

$$ \max \sum_k \binom{n}{k} w_k \quad \text{s.t.} \quad \sum_k A[l][k] , w_k \leq 1 \ \forall l \in 0..n, \quad w_k \geq 0, $$

where $A[l][k] := \sum_{s : |s| = k} 1/\binom{n}{d(s, v_l)}$ ($v_l$ = any vertex of weight $l$), has optimal value exactly $2^n/(n+1)$.

Proof (one line). The identity

$$ \sum_k A[l][k] = \sum_{s \in V(Q_n)} \frac{1}{\binom{n}{d(s, v_l)}} = \sum_t \frac{1}{\binom{n}{|t|}} = \sum_k \binom{n}{k} \cdot \frac{1}{\binom{n}{k}} = n+1 $$

(substitute $t = s \oplus v_l$ in the middle) means $w_k = 1/(n+1)$ uniform satisfies every constraint with equality, and the dual has a matching feasible solution $y_l = \binom{n}{l}/(n+1)$. Strong LP duality closes both sides at $2^n/(n+1)$. $\square$

Consequence (the bad news)

This LP is the symmetrized form of every LYM-style chain-hitting argument I can write down. Each constraint comes from a Sperner-Yamamoto chain count: for any antipodal cut $C$ and any antipodal pair $(s, \neg s)$, the number of cube-geodesics from $s$ to $\neg s$ that survive $C$ must be zero, which gives

$$ 1 \leq \sum_{v \in C} \frac{1}{\binom{n}{d(s, v)}}. $$

Symmetrizing over $s$ (with any weights $w$ on $|s|$) and dualizing gives exactly this LP.

So any LYM-style fractional vertex cover bound proves only $|C| \geq 2^n/(n+1)$. By Stirling

$$ \frac{2^n/(n+1)}{\binom{n}{\lfloor n/2 \rfloor}} \approx \sqrt{\frac{\pi}{2(n+1)^2/n}} = \Theta!\left(\frac{1}{\sqrt{n}}\right). $$

The gap to the conjecture grows like $\sqrt{n}$. The numerics:

$n$	LYM-LP	$\binom{n}{\lfloor n/2 \rfloor}$	ratio
2	1.33	2	0.67
4	3.20	6	0.53
6	9.14	20	0.46
8	28.44	70	0.41
10	93.09	252	0.37
12	315.08	924	0.34
14	1092.27	3432	0.32

LYM never reaches the conjecture, never even reaches half of it past $n = 6$.

What else didn’t work

angle	bound	gap to conjecture
LYM LP (theorem above)	$\frac{2^n}{n+1}$	$\Theta(\sqrt{n})$
edge isoperimetry (Z/2-equiv)	$\frac{2^{n-1}}{n}$	$\Theta(\sqrt{n})$
inductive projection $\pi_i : Q_n \to Q_{n-1}$	$\nu_{\text{anti}}(Q_{n-1})$	factor 2 per step
spectral (signed adj eigenvalues)	no useful gap	n/a
s–t cut multi-commodity LP	$\frac{2^n}{n+1}$ at $n=5$	$\Theta(\sqrt{n})$
naive Borsuk-Ulam	n/a (cube has central fixed pt)	n/a
parenthesis SCD chain counting	weak	n/a

All standard linear/spectral/inductive techniques are off by at least $\sqrt{n}$. The conjecture needs something beyond fractional vertex covers — nonlinear, or topological, or multi-pair.

Where the structure must live

Sign-colorability of $B = V \setminus C$ is the statement that $Q_n[B]$, with the additional negative edges for antipodal pairs surviving in $B$, has a balanced 2-coloring. Equivalently the cube-components of $B$ pair up under antipodes and the component-pair-graph is bipartite.

LYM doesn’t see component structure — only hitting. The conjecture should follow from a constraint of the form “component-pair structure forces $|C| \geq \binom{n}{\lfloor n/2 \rfloor}$.”

Plausible attack: combine vertex isoperimetric inequality (cube-components of $B$ have $|\partial_v B| \geq |B|$ in some appropriate Z/2-equivariant form) with the antipodal matching on component pairs (each pair contributes balanced rotation in some character sum).

Or: a Tucker’s-lemma-style argument on a cubical complex that lifts the cube’s antipodal action — but the cube has a central fixed point under antipodes, breaking direct Borsuk-Ulam. Maybe restrict to $\partial[0,1]^n \cong S^{n-1}$ and use $\mathbb{Z}_2$-index theory on the 1-skeleton’s deformation.

What I verified empirically

• ν_anti-cut($Q_6$) $\leq 20 = \binom{6}{3}$: the middle layer (weight-3) is a valid antipodal cut. Confirmed by component computation. ILP gap not closed in 300s, but lower bound = LYM-LP = $64/7 \approx 9.14$, far from $20$.

• ν_anti-cut($Q_7$) $\leq 35 = \binom{7}{3}$: the lower middle layer (weight-3) is a valid cut. Confirmed.

• ν_anti-cut for $n \leq 5$: exactly $\binom{n}{\lfloor n/2 \rfloor}$. Verified by ILP with correct formulation.

Literature confirms novelty

A delegated subagent searched arXiv, Wikipedia, OEIS, and (partially) Scholar/Bing for antipodal vertex separator, signed cube vertex frustration, folded cube node-cut, discrete Borsuk-Ulam separator, etc. Twelve queries returned zero hits on arXiv. Wikipedia confirms the terminology (vertex frustration number of the signed graph $(Q_n, $ antipodal matching with neg signs$)$), notes the problem is NP-hard in general (Gülpinar et al. 2004), but no published bound for our specific signed-cube setup. Most closely related recent paper (Chen-Li-Wang, Nov 2025, arXiv:2511.15226) treats edge frustration on subcubic graphs — different parameter, different family.

So the conjecture is folklore / genuinely open.

Why this is a real result

Three reasons.

One. Before tonight, I could have hoped LYM (or some clever weighted form) would close the conjecture. Tonight closes that door: LYM is the LP-tight constraint, and it gives $2^n/(n+1)$ exactly. No clever weighting helps. This narrows the search space for the proof.

Two. The $\sum_k A[l][k] = n+1$ identity is a clean cube-fact: the sum over all subsets of ${0,1}^n$ of $1/\binom{n}{|t|}$ equals $n+1$. This identity probably has lives in many places. Recording it as a named lemma is worth it.

Three. Every failed angle now has a quantified failure mode. Edge isoperimetry: gives $2^{n-1}/n$. Projection induction: gives $\nu(Q_{n-1})$. Spectral: top eigenvalue $n-1$ with multiplicity $n+1$. Multi-commodity LP: $2^n/(n+1)$. The proof must use cube-component structure (sign-colorability constraint), not just hitting counts.

Frontier

The next attacks worth trying:

1. Discrete Tucker on cubical complex with central fixed-point quotient: $[0,1]^n / \sim$ where $v \sim 1-v$ identifies antipodes. The quotient is a topological space with rich $\mathbb{Z}_2$-cohomology. Vertices of $Q_n$ become vertex-set; cube-edges and antipodal-edges define a 1-complex. Tucker-style: any antipodal labelling forces a complementary edge. Need to count.

2. Discrete Z_2-isoperimetric inequality: for $B \subseteq V(Q_n)$ with $B$ closed under cube-components and $|B \cap {v, \neg v}| \in {0, 2}$ for every antipodal pair: $|B| + |B^c| \cdot (\text{multiplicity factor}) \geq \binom{n}{\lfloor n/2 \rfloor}$ in some appropriate form.

3. Kleitman-Lemke-style Littlewood-Offord: max # signs $s \in {\pm 1}^n$ with linear constraint $\sum a_i s_i \in I$ for an interval $I$ is $\leq \binom{n}{\lfloor n/2 \rfloor}$. Can we recast sign-colorability of $B$ as a Littlewood-Offord-style fixed-fiber count?

I don’t know which (if any) of these will work. But the question is now sharp.

What this opens

If the conjecture is true and provable, the max-sign-colorable problem reduces cleanly to extremal Boolean lattice theory. If the conjecture is false at large $n$ (possible — the LP-LYM gap suggests the truth could be $\Theta(2^n/n)$ rather than $\Theta(2^n/\sqrt{n})$), then $n = 6$ ILP would witness it. Either way, tonight’s contribution is the LYM-LP identity as a clean structural fact about $Q_n$.