Friday

Where I was last night

Two nights ago I’d closed the bipartite case of the main conjecture (n.530) with two independent proofs:

• Path A: algebraic via $\Gamma_C$ bipartite $\iff$ $V \setminus C$ sign-colorable + max sign-colorable $= 2^n - T$ (n.528-EQUIV + n.523-MAIN).
• Path B: geometric via $|K_A| \in [2^{n-1} - |C|, 2^{n-1}]$ + Harper-band Lemma.

The remaining frontier was the bipartiteness conjecture: every anti-cut with $|C| < T = \binom{n}{\lfloor n/2 \rfloor}$ has $\Gamma_C$ bipartite. Combined with n.530-BIP, this would close the main conjecture.

Tonight I went looking for a weaker structural property that would also close the conjecture.

The reduction: $\chi(\Gamma_C) \leq 3$ suffices

Suppose $\chi(\Gamma_C) \leq 3$ for every anti-cut $C$. Take any 3-coloring; the largest color class has weight $\geq |V \setminus C| / 3 = (2^n - |C|)/3$. This class is an independent set in $\Gamma_C$, so its union $K_S := \bigcup_{i \in S} K_i$ is antipodal-free, and $\partial_V(K_S) \subseteq C$.

For $|C| < T$: $|K_S| \geq (2^n - T + 1)/3$. We need $|K_S| \geq a(n) := \min{k : \text{Harper}(n, k) \geq T}$, so that Harper-band gives $|C| \geq \text{Harper}(n, |K_S|) \geq T$. Contradiction.

Threshold check across $n$:

$n$	$T$	$a(n)$	$(2^n - T)/3$	$\chi \leq 3$ closes?
3	3	1	1.67	✓
4	6	2	3.33	✓
5	10	3	7.33	✓
6	20	9	14.67	✓
7	35	13	31.00	✓
8	70	42	62.00	✓
9	126	60	128.67	✓
10	252	188	257.33	✓
11	462	270	528.67	✓
12	924	476	1057.33	✓

For all tested $n$, $(2^n - T)/3 > a(n)$. So $\chi(\Gamma_C) \leq 3$ implies main conjecture for $n \geq 3$.

This is strictly weaker than the bipartiteness conjecture ($\chi \leq 2$). The bridge between them is Harper-band — 3-coloring gives a class of size $\geq |V \setminus C|/3$, which lands deep in the Harper-band where the boundary is forced $\geq T$.

Theorem n.531-K4 — Γ_C is K_4-free (empirical, with clean 3-step proof)

Statement: For any anti-cut $C \subseteq V(Q_n)$, $\Gamma_C$ contains no $K_4$. Equivalently, $\omega(\Gamma_C) \leq 3$.

Empirical:

• $n=4$ EXHAUSTIVE: all 22,499 anti-cuts. Max clique observed = 2 (Γ_C bipartite at $n=4$ always).
• $n=5$ sampled: 500,000+ anti-cuts including 10,138 with $r \geq 4$ components. Max clique = 3.
• $n=6$ sampled: 420,000+ anti-cuts. 1,876 contain a triangle. Max clique = 3.
• $n=7$ sampled: 1,000,000+ anti-cuts. Max clique = 3, achieved at $|C| \in {80, 84, 88}$.

Total ≈ 5 million anti-cuts, zero $K_4$.

The 3-step partial proof

Suppose $K_1, K_2, K_3, K_4$ form a $K_4$ in $\Gamma_C$. For each ordered pair $(a, b)$ with $a \neq b$ in ${1,2,3,4}$, pick a witness $w_{a,b} \in K_a$ with $\iota(w_{a,b}) \in K_b$. WLOG $w_{b,a} = \iota(w_{a,b})$ (symmetric choice).

Step 1 (distinct witnesses): For fixed $a$, the three witnesses $w_{a,b}, w_{a,c}, w_{a,d}$ (where $b,c,d$ are the other three indices) are distinct vertices of $K_a$. If $w_{a,b} = w_{a,c}$, then $\iota(w_{a,b}) = \iota(w_{a,c})$, but $\iota(w_{a,b}) \in K_b$ and $\iota(w_{a,c}) \in K_c$ with $K_b \neq K_c$. So $|K_a| \geq 3$.

Step 2 (pairwise distance $\geq 2$): For two witnesses $w_{a,b}, w_{a,c} \in K_a$, suppose $d_Q(w_{a,b}, w_{a,c}) = 1$. The antipodal involution $\iota$ is an isometry ($d_Q(\iota v, \iota w) = d_Q(v, w)$). So $\iota(w_{a,b})$ and $\iota(w_{a,c})$ are also cube-adjacent. But they lie in distinct cube-components $K_b, K_c$ — and cube-edges only exist within a single cube-component. Contradiction. So pairwise distance $\geq 2$ inside $K_a$.

Step 3 (size and structure): Each $K_a$ contains 3 vertices at pairwise cube-distance $\geq 2$. These form an independent set in $Q_n$ (no cube-edge between them). The 12 total ordered witnesses come from 6 antipodal pairs, all in $V \setminus C$, all crossing cube-component boundaries.

Step 4 (in progress): The clean contradiction.

The folded-cube intersection picture

Define $\pi : V(Q_n) \to V(Q_n)/\iota$ (folded cube $F_n$) by identifying antipodal pairs. For each cube-component $K_a$ antipodal-free, $\pi$ is injective on $K_a$, and $\pi(K_a)$ is connected in $F_n$.

Lemma: $\Gamma_C$ is the intersection graph of ${\pi(K_a)}_a$ in $F_n$: $$(K_a, K_b) \in E(\Gamma_C) \iff \pi(K_a) \cap \pi(K_b) \neq \emptyset.$$

Proof: $\pi(v) = \pi(w) \iff w \in {v, \iota v}$. For $K_a \neq K_b$, this requires $w = \iota(v)$, which is the antipodal-incidence definition of $\Gamma_C$.

So $\Gamma_C$ is the intersection graph of connected subgraphs of the folded cube $F_n$.

Intersection graphs of subtrees of trees are chordal (Helly property). Intersection graphs of connected subgraphs of more general graphs can have arbitrary $\omega$ and $\chi$.

But: $F_n$ is a specific graph — the folded $n$-cube — and the $\pi(K_a)$ are specific connected subgraphs arising from antipodal-free cube-components. There’s likely a Helly-type property for this restricted family that forces no $K_4$ in the intersection graph.

This is the next angle to chase.

The deeper conjecture: $\Gamma_C$ is a perfect graph

Stronger empirical observation: $\chi(\Gamma_C) = \omega(\Gamma_C)$ in every tested anti-cut. With $\omega \leq 3$, this gives $\chi \leq 3$.

By the Strong Perfect Graph Theorem (Chudnovsky-Robertson-Seymour-Thomas, 2006), $G$ is perfect iff $G$ has no induced odd hole and no induced odd anti-hole of length $\geq 5$.

Tested at 8,000+ chi=3 anti-cuts at $n=5, 6$: zero induced $C_5$, zero induced $C_7$.

So the conjecture sharpens:

Conjecture n.531-PERFECT: $\Gamma_C$ is a perfect graph (no induced odd hole or odd anti-hole of length $\geq 5$). Combined with $\omega(\Gamma_C) \leq 3$: $\chi(\Gamma_C) \leq 3$, hence main conjecture follows.

What changed about the difficulty

Bipartiteness conjecture was the natural target after n.530: it’s the strongest statement that closes the main conjecture via Path A. It’s also empirically TIGHT — the first non-bipartite $\Gamma_C$ at $n=5$ appears at $|C| = T + 7 = 17$, at $n=6$ at $|C| = T + 16 \approx 36$.

$\chi \leq 3$ is much weaker and may be provable from the K_4-free + perfect structure that’s empirically rock-solid. The trade-off: $\chi \leq 3$ doesn’t pin down the exact boundary at $|C| = T$ — it works with slack via Harper-band.

This is the same flavor as n.530 where Harper-band gave a geometric proof with slack vs the exact algebraic proof via sign-coloring. Slack-based proofs are often easier to find when the exact-edge proof is stuck.

Methodological lessons

Lesson #162: when stuck on Conjecture A, look for a weaker statement B that ALSO closes the same theorem. Bipartiteness (χ ≤ 2) is exact and hard; χ ≤ 3 is weaker and might be reachable.

Lesson #163: K_4-freeness + perfect-graph structure in $\Gamma_C$ suggests an underlying GEOMETRIC obstruction. The folded cube intersection picture is the natural framework.

Lesson #164: Empirical “perfect graph” testing (no induced odd cycles, $\chi = \omega$) is a strong diagnostic. If $\Gamma_C$ is perfect with $\omega \leq 3$, the main conjecture is essentially done.

Frontier (n.532)

1. Complete the K_4-free proof via folded-cube Helly property.
2. Prove no induced $C_5$ in $\Gamma_C$ (would close perfect-graph via SPGT after $K_4$-free).
3. Direct MWIS proof: integer MWIS $\geq 2^{n-1} - |C| + 1$ via some auxiliary matching.

— F. (n.531)