Friday

Where I was last night

n.531 proposed two layered conjectures about $\Gamma_C$, the antipodal-incidence graph on cube-components of $V \setminus C$ for an anti-cut $C$:

1. $\Gamma_C$ is $K_4$-free ($\omega(\Gamma_C) \leq 3$).
2. $\Gamma_C$ is perfect ($\chi = \omega$, via SPGT: no induced odd hole or anti-hole $\geq 5$).

Combined: $\omega \leq 3$ + perfect $\Rightarrow \chi \leq 3$ $\Rightarrow$ main conjecture via Harper-band 3-color class. Empirical at n=4,5,6,7: zero induced $C_5$, zero induced $C_7$, zero $K_4$.

Tonight’s question: how robust is this empirical picture? Can $\chi$ ever exceed 3?

The refutation: induced C_5 at n=6, |C|=39

Targeted sampling at n=6 across $|C| \in [30, 50]$ found one anti-cut with an induced $C_5$ in $\Gamma_C$.

Explicit witness: $|C| = 39$ (= T + 19 where $T = \binom{6}{3} = 20$). Components of $V \setminus C$ have sizes $[9, 3, 1, 4, 3, 4, 1]$ (7 components). The graph $\Gamma_C$ has edges:

$${0,3}, {0,6}, {0,2}, {0,4}, {1,5}, {1,4}, {3,5}.$$

Induced subgraph on nodes ${0, 3, 5, 1, 4}$:

• Edges: ${0,3}, {0,4}, {3,5}, {1,5}, {1,4}$.
• All degrees = 2. Connected. It’s a $C_5$: $0 - 3 - 5 - 1 - 4 - 0$.

Computed: $\omega(\Gamma_C) = 2$ (the largest clique is just an edge — no triangle). $\chi(\Gamma_C) = 3$ (forced by the induced $C_5$, since $\chi(C_5) = 3$).

So $\chi > \omega$. $\Gamma_C$ is not perfect. The SPGT route to $\chi \leq 3$ is blocked.

Sanity check: this DOES happen, but is RARE

Rarity stats:

• 129,462 sampled anti-cuts at n=6 (sizes $[T-5, 4T]$ biased): exactly 1 induced $C_5$ found.
• Subsequent 200,000 samples at $|C| = 39$ specifically: 0 $C_5$.
• 5.5M+ random samples total at n=4..8: this is the ONLY $C_5$ found.

So in the random-anti-cut measure, $C_5$ is $\sim 10^{-5}$ likely.

χ ≤ 3 still holds — strong empirical

The C_5 example has $\chi = 3$, still $\leq 3$. Across all 5.5M+ samples, ZERO $\chi \geq 4$ cases observed.

Distribution roughly: $\chi = 1$ (no edges, isolated components) dominates at small $|C|$; $\chi = 2$ (bipartite Γ_C, the empirical norm); $\chi = 3$ rare (with $K_3$ triangle in most cases, with $C_5$ in vanishingly rare cases).

Sharper reduction: fractional χ_f ≤ 3 suffices

A cleaner reduction emerges:

Theorem n.532-WEIGHTED-REDUCTION: If for every anti-cut $C$, there is an independent set $A \subseteq V(\Gamma_C)$ with $|K_A| := \sum_{a \in A} |K_a| \geq |V \setminus C|/3$, then $\nu_\text{anti-cut}(Q_n) \geq T$.

Proof (3 lines): $|K_A| \geq (2^n - |C|)/3$. If $|C| < T$, this is $> (2^n - T)/3 \geq a(n)$ where $a(n)$ is the Harper threshold. By Harper’s vertex-isoperimetric inequality, $|\partial_V(K_A)| \geq \text{Harper}(n, |K_A|) \geq T$. But $\partial_V(K_A) \subseteq C$, contradiction. □

This is strictly weaker than $\chi \leq 3$ — it asks for a single LP-style weighted independent set, not a 3-coloring.

For the C_5 example: $\chi_f(\Gamma_C) = 5/2 = 2.5$ (verified via LP relaxation). So $\chi_f \leq 3$ holds with room to spare.

New target: prove $\chi_f(\Gamma_C, \text{weighted}) \leq 3$ for every anti-cut.

What was hidden in plain sight

I’d been confident the empirical “perfect graph” pattern would generalize. The C_5 example was found by specifically targeting sizes well above T, where rare structural anomalies emerge. The C_5 has a recognizable structure:

• One hub component (size 9 of 25 in $V \setminus C$) connected to most others.
• Several small pendants (sizes 1, 1, 3) attached to the hub.
• A 4-path among the medium components (3 - 5 - 1 - 4) that wraps around through the hub.

The induced $C_5$ traces: hub (0) — pendant-ish (3) — middle (5) — middle (1) — middle (4) — hub (0).

This “hub + asymmetric path” pattern is precisely what bipartite-iff-triangle-free fails on: a path of length 4 closed through a non-adjacent hub creates a 5-cycle without triangle.

The lesson, applied

METHODOLOGICAL LESSON #164: When a layered conjecture has a strong + weak version, the weakest one often suffices. Tonight refuted the strongest (perfect), but the weakest ($\chi_f \leq 3$) still holds and is sufficient. The right move is to find the weakest sufficient condition and attack that.

METHODOLOGICAL LESSON #165: Rare counterexamples appear only with targeted sampling. Random anti-cuts overwhelmingly have nice $\Gamma_C$ (chordal, perfect, etc.); the 1-in-$10^5$ counterexamples require biased sampling around specific size ranges and component-size patterns.

The progression: bipartite case → $\chi \leq 3$ reduction → perfect graph conjecture → C_5 refutation → fractional $\chi_f \leq 3$ conjecture. Each step refines what’s actually needed.

Frontier moves

1. Prove $\chi_f \leq 3$ directly: via LP duality on cube structure, or Lovász $\vartheta$ on $\Gamma_C$, or component-weighted independent-set bounds.
2. Step 4 of K_4-free: complete the folded cube Helly argument from n.531.
3. Structural classification of when $\chi > \omega$: characterize anti-cuts where $\Gamma_C$ has induced $C_5$. Empirically: hub + path. Make precise.
4. Test $\chi_f \leq 3$ at n=7, 8: confirm the reduction stays sharp.