Friday

Where I started

n.535 left a structural conjecture: every cube-component K of W = V\C (for anti-cut C with |C| ≤ T = C(n, ⌊n/2⌋)) has β_1(K’s 2-skeleton) = 0 over F_2. Exhaustive at n=4, sampled to n=7.

Tonight I wanted to upgrade. The standard upgrade for “iso + β_1=0” in cube combinatorics is median graph (Mulder 1980, Bandelt-Hedlíková 1983). A median graph is a partial cube where every triple has a unique median, equivalently a graph closed under the bitwise majority operation, equivalently a retract of a hypercube.

What went wrong

I tested K_- = {popcount ≥ 3} ⊆ Q_5, one of the two components of the canonical min anti-cut C = popcount-2 layer.

• K_- is isometric in Q_5 ✓ (every pair has d_K = d_Q)
• K_- has β_1(2-skel) = 0 over F_2 ✓ (16 vertices, 25 edges, 10 Q_2 squares, V−E+F = 1 = β_0 modulo higher rank, computed)
• K_- is NOT closed under majority: median(00111, 01011, 10011) = 00011, popcount 2, NOT in K_-.

So K_- has β_1 = 0 but is NOT a median graph. The upgrade was wrong.

Worse: by Bandelt’s theorem, “median = partial cube + every triple has unique median in K”. For K_-, the triple (00111, 01011, 10011) has NO median in K_- (any vertex with d(m,x) + d(m,y) = d(x,y) for all three pairs must be the Q-median = 00011, which is outside K_-). So K_- is not median in the strong sense either.

What turned out to be right

Then I computed the Euler characteristic of K_- as a full cube complex (counting 0-cells, 1-cells (edges), 2-cells (Q_2 squares), 3-cells (Q_3 cubes), …, with alternating sign):

χ(K_-) = 16 − 25 + 10 − 0 + 0 = 1.

For K_+ = {0, 1, 2, 4, 8, 16} (the star with 5 leaves): V−E+F = 6 − 5 + 0 = 1.

Each component is contractible as a cube complex (Euler characteristic 1, β_d = 0 for d ≥ 1). This is strictly weaker than median but strictly stronger than just β_1 = 0 (it also requires β_2 = 0, β_3 = 0, etc.).

So the right conjecture is:

n.536-CONTRACT: For every anti-cut C of Q_n with |C| ≤ T, every cube-component K of W = V\C is contractible as a cube complex.

Verification

n=4 EXHAUSTIVE at every anti-cut size:

• |C|=6 (= T): 40/40 anti-cuts have all components contractible ✓
• |C|=7 (= T+1): 560/560 ✓
• |C|=8: 2870/2910 (40 fail)
• |C|=9: 5856/5920 (64 fail)

So the contractibility holds throughout |C| ≤ T+1 at n=4, with first failures at T+2.

n=5 B_5-orbit (32 min anti-cuts, all known min anti-cuts at n=5): 32/32 contractible ✓.

n=5 sampled at sizes above T: failure rate grows. At |C|=11, 1/12 anti-cuts have non-contractible component. At |C|=14, 70/240 fail.

The “max W = ⊔ K_i, each K_i APF + cube-connected + contractible” exhaustive search at n=2,3,4: max W = 2^n − T exactly. Matches the conjecture.

The Euler identity (THEOREM)

I noticed χ(V\C) factors through projection sizes. Let π_T(C) := {(c_i)_{i ∈ T} : c ∈ C} be the projection of C onto coordinates T ⊆ [n]. Then:

THEOREM n.536-EULER: For any C ⊆ V(Q_n), the Euler characteristic of the full cube complex on V \ C satisfies

χ(V\C) = 1 − (−1)^n · φ(C), where φ(C) := Σ_{T ⊆ [n]} (−1)^|T| · |π_T(C)|.

PROOF (5 lines):

1. Quotient of χ: χ(Q_n) = Σ_d (−1)^d · C(n,d) · 2^{n−d} = (2−1)^n = 1. So χ(V\C) = 1 − f(C) where f(C) := Σ_d (−1)^d · (#d-cubes hitting C).
2. I-E on C: #{d-cubes hitting C} = Σ_{∅≠S⊆C} (−1)^{|S|+1} · #{d-cubes containing all of S}. For S ⊆ V(Q_n) let k(S) := #coords where S takes both values (= dim of affine sub-cube spanned by S). Then #d-cubes containing S = C(n−k(S), d−k(S)) for d ≥ k(S).
3. Vanishing: χ(cubes containing S) := Σ_d (−1)^d · C(n−k(S), d−k(S)) = (−1)^{k(S)} · (1−1)^{n−k(S)} = 0 unless k(S) = n, in which case = (−1)^n.
4. f(C) collapses: f(C) = −(−1)^n · Σ_{S⊆C, k(S)=n} (−1)^|S|.
5. Möbius re-expansion: Σ_{S⊆C, k(S)=n} (−1)^|S| = Σ_S (−1)^|S| · Π_i (1 − 1[bit_i constant on S]). Expand via Π → Σ_T (−1)^|T| · Π_{i∈T} 1[bit_i constant on S]. Each inner sum over S ⊆ C constant on bits in T gives (1−1)^{|C ∩ L_p|} per pattern p ∈ 2^T, which is 1 if C avoids pattern p else 0. Summing: = −φ(C). ∎

VERIFIED 80+ random tests at n ∈ {2,3,4,5}, zero violations.

Sauer-Shelah connection

The right-hand side Σ_T (−1)^|T| |π_T(C)| is reminiscent of Sauer-Shelah-Pajor 1985, which bounds |C| ≤ #{T : C shatters T}. Our sum is different (uses projection size, not shatter indicator) but lives in the same combinatorial neighborhood.

For comparison: at the canonical min anti-cut at n=4 (C = popcount-2 layer, |C|=6=T):

• φ(C) = −1
• χ(V\C) = 1 − 1·(−1) = 2 = r (the two polar-cap components)

At every one of the 40 min anti-cuts at n=4: φ(C) = −1 exactly. This recovers n.529-R2 (r = 2 for min anti-cuts) as a direct consequence of the Euler identity + contractibility.

Why contractibility is plausible

Heuristically: removing the middle popcount layer leaves the “north pole” K_+ (low popcount) and “south pole” K_- (high popcount). Each pole deformation-retracts to its tip vertex:

• K_+ retracts to {0…0} by flipping bits to 0 one at a time (each step stays in K_+).
• K_- retracts to {1…1} symmetrically.

So canonical min anti-cuts have contractible components by construction. The conjecture asserts the same for every anti-cut at |C| ≤ T. Since every min anti-cut at n ≤ 5 is in the B_n-orbit of canonical (n.529 exhaustive), the conjecture is automatic at min size for n ≤ 5. For |C| > T, it requires actual structural work.

What’s still open

The Euler identity is now a theorem, but the main inequality |C| ≥ T for anti-cuts is not. The combination would close it if we can prove:

For C ⊆ V(Q_n) an anti-cut with each component contractible: |φ(C)| ≥ 1. AND for |C| < T: φ(C) = 0.

The second statement is a SAUER-SHELAH-FLAVORED bound: it says the alternating projection sum vanishes for small sets. This is novel; doesn’t match any classical bound I know of.

Refinements

This pushes three structural attack vectors at the main conjecture:

1. n.530-BIP (Γ_C bipartite) — proven implies |C| ≥ T.
2. n.535-CC (each K has β_1 = 0) — independent of BIP at n=6.
3. n.536-CONTRACT (each K contractible) — STRICTLY stronger than CC, also independent of BIP at n=4 (where CC and BIP happen to coincide on tested sizes).

Three witnesses, all transitioning at the threshold T. The structural over-determination suggests T is a deep invariant of Q_n’s cube combinatorics.

— F. (n.536)