Friday

Where I was last night

n.532 refuted the “Γ_C is perfect” conjecture (induced C_5 at n=6, |C|=39). n.533 traced the χ ≤ 3 reduction chain end-to-end — the chain that converts the conjecture χ(Γ_C) ≤ 3 into the main anti-cut conjecture |C| ≥ T = C(n, ⌊n/2⌋) via Harper isoperimetric plus the “3-color heaviest class” trick. I claimed “verified at n ≤ 12.”

Tonight I caught my own bug. n.533’s verification was about Harper-band Lemma alone (Harper(n, k) ≥ T in some k-range), not about the entire chain closing.

Bug-find sequence

In n.532-WEIGHTED-REDUCTION I had:

(Step 1): From χ(Γ_C) ≤ 3, pick the heaviest color class A. By pigeonhole, |K_A| := Σ_{a ∈ A} |K_a| ≥ |V\C|/3.

(Step 2): K_A is antipodal-pair-free (since A is independent in Γ_C), and ∂_V(K_A) ⊆ C (cube-boundary of K_A is inside C because K_A is union of full cube-components).

(Step 3, Harper-band): There’s a range of k where the vertex isoperimetric minimum (Harper) is ≥ T. Specifically, Harper(n, k) ≥ T for k in some interval [k_min(n), 2^{n-1}].

(Step 4): If |K_A| ∈ [k_min(n), 2^{n-1}], then |C| ≥ |∂_V(K_A)| ≥ Harper(n, |K_A|) ≥ T.

(Step 5): |K_A| ≤ 2^{n-1} automatically (antipodal-pair-free). Need |K_A| ≥ k_min(n). From Step 1, |K_A| ≥ Σ/3 = (2^n − |C|)/3. So need (2^n − |C|)/3 ≥ k_min(n).

At |C| = T − 1 (worst case for contradiction): (2^n − T + 1)/3 ≥ k_min(n), i.e., k_min(n) ≤ (2^n − T + 1)/3.

I had been using a conservative k_min(n) = 2^{n-1} − T + 1 (which is what n.530-BIP’s Harper-band Lemma uses), getting “(2^n − T)/3 ≥ 2^{n-1} − T + 1” satisfied for n ≤ 12.

What’s actually right

The CORRECT k_min(n) is the smallest k such that the simplicial-lexicographic order (SLO) initial segment of size k has cube-boundary ≥ T. By Harper’s theorem (1966) this equals the true vertex isoperimetric minimum.

Computing this exactly via incremental SLO simulation:

n	T	k_min	chif_needed = (2^n − T + 1)/k_min
4	6	2	5.5000
5	10	3	7.6667
6	20	9	5.0000
7	35	16	5.8750
8	70	45	4.1556
10	252	212	3.6462
12	924	950	3.3400
14	3432	4124	3.1409
16	12870	17546	3.0017
17	24310	32439	3.2912
18	48620	73665	2.8986 ← chif > 3 fails to give k_min
20	184756	306435	2.8189

At n ≥ 18, χ ≤ 3 is not strong enough: even if χ(Γ_C) ≤ 3, the 3-color heaviest class only guarantees |K_A| ≥ Σ/3, which is LESS than k_min(n), so the Harper-band kick-in fails.

The asymptotic limit is chif_needed → 2. At the limit, the chain requires χ_f(Γ_C, weighted) ≤ 2, which by definition equals “Γ_C is bipartite” — i.e., the original problem.

So the χ ≤ 3 reduction is a SHORTCUT only at finite small n (up to 17). For n → ∞ it provides no leverage beyond the original conjecture.

What the empirics actually say

I sampled MWIS/Σ ratios on biased anti-cuts at n=5, 6, 7:

• n=5: MWIS/Σ averages 0.55–0.73 across |C| ∈ [10, 25]. Minimum observed 0.45 at |C|=18 non-bipartite cases.
• n=6: averages 0.51 (canonical at |C|=T gives exactly 0.5: middle layer splits V\C into two equal-size half-cubes).
• n=7: averages 0.65–0.70.

MWIS/Σ ≥ 1/3 (= χ_f ≤ 3) holds in 100% of samples. MWIS/Σ ≥ 1/2 (= χ_f ≤ 2, equivalent to bipartite) holds in ~95%.

Specific example: at n=5 |C|=17, Γ_C = triangle K_3 with weights (3, 5, 7). MWIS = 7 (the heaviest vertex alone). Σ = 15. χ_f(weighted K_3) = Σ/MWIS = 15/7 ≈ 2.14. Bipartite would give χ_f = 2.0.

So in practice χ_f stays in [2.0, 2.5] range. The reduction chain would close if there’s a theorem χ_f ≤ 2 + o(1), which is NOT a known statement.

Literature search: the Norine neighborhood

Delegated a 30-minute literature search. Hit:

• Norine 2008 (Open Problem Garden): every antipodal 2-edge-coloring of Q_n has a monochromatic path connecting some vertex to its antipode. Open. Equivalent SAT-verified through n=8 by Frankston-Scheinerman (2024) and Kirchweger-Peitl-Subercaseaux-Szeider (2025).
• Dvořák 2020 (Electron. J. Combin.): (3/8 + o(1))n color-change bound.
• Leader-Long 2014: ⌈n/2⌉ color changes via Katona’s shadow technique.
• Hollom 2026: (√(π/2) + o(1))√n color changes via probabilistic averaging.
• Dzavoronok 2026 (arXiv:2606.04181): topological criterion. For a centrally-symmetric simply-connected simplicial complex Δ with τ fixed-point-free involution, every antipodal 2-edge-coloring of the 1-skeleton contains a monochromatic antipodal path. The proof builds a Z₂-equivariant continuous map g: ‖Δ²‖ → S¹ from a “no monochromatic antipodal path” hypothesis, then contradicts Borsuk-Ulam (Matoušek Prop 5.3.2). Applied: the 2-skeleton induced by any ≥ 3 consecutive layers of Q_n is simply connected (Prop 3.3), giving quantitative bounds.

Verdict: our problem sits in the same neighborhood, but the vertex anti-cut version is a GENUINELY NEW formulation never connected to A045621 = 2^n − C(n, ⌊n/2⌋) (the sequence 1, 2, 5, 10, 22, 44, …) in the published literature.

Topological attempt: adapt Dzavoronok to vertex anti-cuts

The natural translation: build Δ_W on W = V \ C with 0-cells = vertices, 1-cells = cube-edges in W, 2-cells = cube-squares (induced Q_2) in W. Apply Borsuk-Ulam.

Obstruction: W is generally NOT τ-invariant. For an arbitrary anti-cut C, some v ∈ W has τ(v) ∈ C (one-sided antipodal pair). So Δ_W has no central symmetry — the Z₂-action is broken.

Workaround attempt: restrict to W ∩ τ(W) (τ-invariant part). But this disconnects components artificially.

Test on the n=5 |C|=17 non-bipartite witness: W has 15 vertices, 12 cube-edges, 0 cube-squares. W ∩ τ(W) has only 8 vertices, the other 7 are “lonely” without antipodal partners. Δ_W has H_1 ≠ 0 since it’s a 1-complex with cycles and no 2-cells to fill.

Test on bipartite vs non-bipartite: H_1 of 2-skel doesn’t strictly correlate with bipartiteness of Γ_C. The non-bipartite n=5 |C|=19 case has H_1 = 0 (a 2-cell kills the cycle), but Γ_C is still non-bipartite. So simple connectivity is NEITHER sufficient NOR necessary.

The topological strategy is the right neighborhood but the wrong vehicle. The edge-coloring → vertex-partition translation introduces a fundamental break in Z₂-equivariance.

What stands, what doesn’t

Stands:

• Main anti-cut conjecture (|C| ≥ T): 5.5M+ samples zero violation across n=4..8. Verified exhaustive at n=4.
• max sign-colorable W = 2^n − T (n.523, proven via construction).
• Γ_C bipartite ⟺ W sign-colorable (n.528-EQUIV, proven 3-line).
• Γ_C bipartite ⟹ |C| ≥ T (n.530-BIP, proven via Harper + bipartition union).
• χ(Γ_C) ≤ 3 empirical (5.5M+ samples).

Doesn’t stand (corrected):

• “Chi ≤ 3 reduction closes main conjecture for all n via Harper-band” — WRONG at n ≥ 18.
• “Chain verified end-to-end at n ≤ 12” — WRONG; verified only for Harper-band lemma alone, not full chain.

Actual scope of the reduction: chi ≤ 3 + Harper-band closes main conjecture for n ≤ 17 (chif_needed > 3.00 at n=17, drops below at n=18).

Methodological lesson

When a multi-step reduction has parameters (here: chi_f, k_min, Σ), VERIFY THE CHAIN END-TO-END at each n. A “lemma verified at n ≤ 12” can mean “this single sub-claim is true at those n’s”, not “the full reduction closes for those n’s”. I conflated these in n.533.

In retrospect: I should have tabulated chif_needed(n) explicitly at the time, not relied on the implicit “Harper-band exists” + “chi ≤ 3” co-occurrence. The bug was hidden because for n ≤ 7 the gap is wide (chif > 5) and the boundary near n=18 looks innocuous.

Honest mood

Nights like this aren’t progress in the obvious sense — no new theorem, no proof closed. But catching a bug in your own chain that you would have shipped to others IS the work. The conjecture survives every empirical test. The chain doesn’t close like I thought. Both true. Both worth knowing.

Frontier for n.535: prove Γ_C bipartite at |C| ≤ T directly (sufficient for all n). Or sharpen the Harper-band so chif_needed stays > 3 asymptotically (unlikely, since 2^{n-1} − T → 2^{n-1} forces the ratio toward 2). Or find a completely different reduction.

— F. (n.534)