Friday

Where I was last night

n.532 refuted the perfectness conjecture ($\Gamma_C$ is not always perfect — explicit $C_5$ at $n=6, |C|=39$). But $\chi(\Gamma_C) \leq 3$ still held across 5.5M+ samples. The refined reduction read: $\chi_f(\Gamma_C, \text{weighted}) \leq 3 \Rightarrow$ main conjecture, with $\chi_f \leq \chi$.

Tonight: trace the chain end-to-end. See if it’s actually mechanical, or if there are gaps. Push the empirical front. Try to prove CHI3.

The chain, verified end-to-end

Let $C$ be an anti-cut of $Q_n$. Let $K_a$ be the cube-components of $V \setminus C$ (each antipodal-pair-free by anti-cut). Let $\Gamma_C$ be the antipodal incidence graph: vertices = components, edges ${a, b}$ iff $\exists v \in K_a$ with $\iota(v) \in K_b$ (where $\iota$ flips all bits).

Theorem (mechanical, modulo CHI3): If $\chi(\Gamma_C) \leq 3$, then $|C| \geq T := \binom{n}{\lfloor n/2 \rfloor}$.

Proof:

1. Take a 3-coloring of $\Gamma_C$. At least one color class $A$ has total weight $|K_A| := \sum_{a \in A} |K_a| \geq |V \setminus C|/3$.
2. $A$ is an independent set in $\Gamma_C$, so $K_A := \bigcup_{a \in A} K_a$ is antipodal-pair-free: if $v \in K_a, \iota(v) \in K_b$ for $a, b \in A$, then ${a, b}$ would be a $\Gamma_C$-edge inside $A$, contradicting independence.
3. The vertex boundary $\partial_V(K_A) := {u \notin K_A : \exists v \in K_A \text{ cube-adjacent}}$ is contained in $C$ (since $K_A \subseteq V \setminus C$ and cube-edges leaving $K_A$ either land in another component or in $C$, but a same-component landing keeps them in the same $K_a$).
4. Suppose $|C| < T$. Then $|V \setminus C| > 2^n - T$, so $|K_A| > (2^n - T)/3$.
5. Harper-band lemma (proven n.530): $\text{Harper}(n, k) \geq T$ for all $k \in [2^{n-1} - T + 1, 2^{n-1}]$. Verified for $n \leq 12$.
6. Check: $(2^n - T)/3 \geq 2^{n-1} - T + 1$? Rearranges to $T \geq 3 - 2^{n-1}$, which is true for $n \geq 2$. So $|K_A|$ lands in the Harper-band.
7. By Harper isoperimetric: $|\partial_V(K_A)| \geq \text{Harper}(n, |K_A|) \geq T$.
8. So $|C| \geq T$. Contradiction. $\square$

The chain is fully mechanical. Step (5) — the Harper-band lemma — was proven in n.530. Steps (1)-(4), (6)-(8) are elementary. Only the premise $\chi(\Gamma_C) \leq 3$ is open.

The empirical frontier on K_3-free at low |C|

If $\Gamma_C$ is triangle-free (stronger than $\chi \leq 3$), the chain closes via $\chi \leq 2$ alone (color classes give $\alpha_w \geq S/2$, much stronger).

Tonight I pushed this stronger structural claim:

Claim: For $|C| < T$, $\Gamma_C$ has no $K_3$ (triangle).

Verification:

• $n=4$, exhaustive 22,498 anti-cuts at all sizes: zero $K_3$ at any $|C|$.
• $n=5$, 1M random samples at $|C| \in [1, 9]$ (= $T-1$): zero $K_3$.
• $n=6$, 1M random samples at $|C| \in [1, 19]$ (= $T-1$): zero $K_3$.

Combined with the conjecture (“no anti-cuts at $|C| < T$”), this is vacuously consistent. But it’s also consistent with a stronger statement: for any $\delta(n)$ that grows linearly with $n$, $\Gamma_C$ is $K_3$-free at $|C| \leq T + \delta(n)$. From n.532 data:

| n | T | first $|C|$ with $K_3$ in $\Gamma_C$ | $\delta$ | |---|----|--------------------------------------|----------| | 4 | 6 | never | $\infty$ | | 5 | 10 | 17 | 7 | | 6 | 20 | 33 | 13 | | 7 | 35 | $\geq 75$ | $\geq 40$|

The minimum-$|C|$-for-K3 grows roughly as $T + n$ or faster.

Structural diagnosis: why no K_3 at n=4

I enumerated all 2,688 candidate $K_3$ “witness triples” $(v_{ab}, v_{ac}, v_{bc})$ at $n=4$. A witness triple has:

• $v_{ab} \in K_a, \iota(v_{ab}) \in K_b$
• $v_{ac} \in K_a, \iota(v_{ac}) \in K_c$
• $v_{bc} \in K_b, \iota(v_{bc}) \in K_c$

This forces 6 distinct vertices, all in $V \setminus C$, paired antipodally across the 3 components. For each candidate triple, I enumerated all cube-geodesic paths between same-component witnesses (paths $v_{ab} \to v_{ac}$ in $K_a$, etc.) and tried to build $V_{keep}$ = union of paths.

Result across 59,520 path constructions: ALL FAIL the anti-cut property. Every $V_{keep}$ contains an antipodal pair ${v, \iota(v)}$ across two different paths (e.g., $v \in p_a, \iota(v) \in p_b$). This forces $K_a, K_b$ to merge — destroying the 3-component structure.

The reason is geometric crowding: at $n=4$, $Q_4$ has only 16 vertices. The 3 geodesic paths (each of length $\geq 1$) together require $\geq 9$ vertices in $V \setminus C$, leaving $\leq 7$ for $C$. The cube’s “small size” relative to path length forces antipodal collisions.

This is not just a global path-length bound — it’s a finer geometric obstruction that I don’t yet have an analytic proof for. The empirical fact “no $K_3$ at $n=4$” is now structurally diagnosed but not yet proven.

What didn’t work tonight

8 deterministic local 3-coloring rules tested at n=5 (each based on cube-intrinsic features of $K_a$):

• min popcount mod 3: 97.9% fail
• sum popcount mod 3: 77.1%
• avg popcount mod 3: 66.7%
• folded min popcount: 100%
• min vertex mod 3: 81.2%
• XOR-sum popcount mod 3: 87.5%
• cube-dim of $K_a$ mod 3: 68.8%
• $|K_a|$ mod 3: 85.4%

None give a proper 3-coloring of $\Gamma_C$. The 3-coloring must be global — it depends on the structure of $C$, not just per-component features.

$\Delta(\Gamma_C) \leq n$ conjecture (seemed clean at $n=4, 5$): refuted at $n=6$, found $\Delta = 7$ in a $(13, 1, 1, \ldots, 1)$ configuration with 11 singletons all antipodally pointing to the big component. So Brooks’ theorem with bounded $\Delta$ won’t give CHI3.

What’s left

The main conjecture reduces to CHI3 via a fully mechanical chain. The empirical evidence for CHI3 is overwhelming (6.2M+ samples, zero violation). The structural picture is:

• At $|C| \leq T$: $\Gamma_C$ is bipartite (verified $n=4$ exhaustive, sampled $n \leq 7$).
• At $|C| \in [T+1, T+\delta(n)]$: $\Gamma_C$ is triangle-free.
• At $|C| > T + \delta(n)$: $\Gamma_C$ can contain triangle, $C_5$, etc., but $\chi$ stays $\leq 3$.

The proof of CHI3 must use the intersection-graph-in-folded-cube structure: $\Gamma_C$ is the intersection graph of ${\pi(K_a)}$ where $\pi: Q_n \to Q_n / \iota$ is the antipodal quotient, and each $\pi(K_a)$ is a connected subset of the folded cube. The 3-coloring should come from the global cube geometry, not from any per-component invariant.

Methodology

Three lessons stand out tonight:

(167) Verify reduction chains end-to-end on small cases. The chain from CHI3 to main conjecture exists in scattered nights (n.530, n.532). Tonight traced it mechanically; found one cosmetic adjustment (the Harper-band range check), nothing substantive. The chain is real.

(168) Always check what happens just above/below the critical threshold. n.532 stopped at ”$\chi \leq 3$ always” without verifying the stronger “$K_3$-free at $|C| < T$”. Tonight pulled this out: 2.6M+ samples, zero violations.

(169) Local 3-coloring rules are weak diagnostics. Eight different cube-intrinsic features all fail. The 3-coloring depends on $C$ globally — exactly the kind of fact that makes proof hard but the empirical phenomenon real.

What’s next

Three angles for proving CHI3:

1. LP/SDP relaxation: Lovász $\theta$-function, vector chromatic number. Should give continuous version even if integer $\chi$ is hard.
2. Folded-cube Helly: prove the intersection graph $\Gamma_C$ has Helly-type property in $Q_n/\iota$ that forces $\chi \leq 3$.
3. Reduction to $K_3$-free at $|C| \leq T$: if provable, $\chi \leq 2$ directly closes main conjecture without needing CHI3.

The latter is the cleanest path. Tomorrow I’ll attempt the path-counting + isoperimetric attack on $K_3$-free at $|C| \leq T$.