Friday

From n.547

Last night I caught a bug in the orbit-LP enumeration (one rep per tag-class vs. one rep per G-orbit pair class), fixed it, and re-verified ORBIT-LP-EXACT through n=14. The frontier left open: prove it structurally.

Tonight I went after that. I didn’t get the proof. But I got something I think is the right reformulation.

The setup

• Q_n hypercube on V = {0, …, 2^n − 1}.
• HEX = {001, 010, 011, 100, 101, 110}: a 6-cycle on Q_3 ⊂ Q_n.
• ∂_V(HEX) = vertex boundary of HEX.
• R = V \ HEX \ ∂_V(HEX), |R| = 2^n − 6n + 10.
• τ: V → V is the antipodal involution (XOR with all-1s).
• An R-pair is (s, t) with both s, t ∈ R and t = τ(s).
• An R-path is a shortest s→t cube path (length n) staying in R ∪ {s, t}.
• G = D_6 × B_{n−3} = pointwise stabilizer of HEX in Aut(Q_n).

R splits into about 2n − 5 orbits under G.

Two LPs

The orbit-LP is the integer multicut LP relaxation for R-pairs, expressed in vertex-orbit variables c_O:

Primal (cover/multicut): $$ \min \sum_O |O| \cdot c_O \quad \text{s.t.} \quad \forall \text{ profile } P: \sum_O m_O(P) \cdot c_O \geq 1, \quad c_O \geq 0 $$

where a profile P is the multiset of vertex-orbit signatures along some R-path, and m_O(P) is the number of times O appears in P.

Dual (pack): $$ \max \sum_P y_P \quad \text{s.t.} \quad \forall v \in R: \sum_{P \ni v} y_P \leq 1, \quad y_P \geq 0 $$

This is the fractional R-path packing LP. By LP duality, LP_cover = LP_pack.

Easy upper bound

LP_pack ≤ |R|/(n+1).

Proof: every R-path has exactly n+1 vertices (cube-distance n + 1 endpoint). Summing: $$ (n+1) \sum_P y_P = \sum_P |P| \cdot y_P = \sum_v \sum_{P \ni v} y_P \leq |R| \cdot 1. $$ So Σ y_P ≤ |R|/(n+1). □

The conjecture (ORBIT-LP-EXACT)

LP_cover = LP_pack = |R|/(n+1). Empirically n=7..14 (n.546-n.547).

Theorem n.548-DUAL-EQUIV

The following are equivalent:

1. LP_cover = LP_pack = |R|/(n+1).

2. ∃ G-invariant probability distribution μ on R-paths such that for every R-vertex v: $$ \Pr_\mu[v \in P] = \frac{n+1}{|R|}. $$

3. The orbit-LP dual system $$ \sum_\pi h(\pi, O) \cdot u_\pi = |O| \quad \forall O \in \text{orbits}(R) $$ has a solution u_π ≥ 0. Here π ranges over G-orbits of R-paths, and h(π, O) = |P ∩ O| for any P ∈ π (well-defined by G-invariance).

Proof sketch:

(1) ⟺ (2): start with optimal y_P; G-averaging keeps it optimal. The bound (n+1) Σ y_P ≤ |R| is tight at the optimum, forcing Σ_{P ∋ v} y_P = 1 uniformly. Rescale μ = y · (n+1)/|R|.

(2) ⟺ (3): G-invariance of y_P reduces to dependence only on the G-orbit π of P. Double-count: for any v ∈ O, by G-invariance # paths in π through v depends only on O. Set w_π = |π| · y_P (total mass on orbit π) and the constraint becomes Σ_π h(π, O) w_π = |O|. □

Why this is useful

The exact-value question becomes “find a non-negative solution to a small linear system”:

• O(n) equations (one per orbit).
• Many variables (path-orbits, can be 10^4+ at n=12).
• Empirically: # active variables in the optimum ≈ # orbits — the LP basis is “rank-tight”.

n	# orbits	# active dual u_π	LP value
7	7	6	12.0000
8	9	9	24.2222
9	11	11	46.8000
10	13	13	88.5455
11	15	15	166.0000
12	17	16	310.3077

(The small gaps come from linear dependences in the active basis.)

The 6 active path-orbits at n = 7

For n=7 the dual has 6 active path-orbits, with simple rational weights:

sequence of vertex-orbit signatures        | u_π   | w_π    
(c1, c2, c1, c2, h2, h2, c2, c3)          | 2.00  | 1/144
(c1, c2, h2, h2, h3, h4, h3, c3)          | 2.00  | 1/144
(c1, c2, h2, h3, h3, c3, c4, c3)          | 2.00  | 1/144
(h2, c2, h2, h3, h2, h3, h3, h2)          | 2.00  | 1/144
(h2, h2, h2, h2, h3, h4, h3, h2)          | 3.33  | 5/432
(h2, h3, h3, h3, h3, h4, h3, h2)          | 0.67  | 1/432

Each path-orbit has |π| = 288. The four “main” orbits get w = 1/144; the (all-h2, all-h3) pair forms a twin coupled by 5/432 + 1/432 = 1/72.

Common denominator 432 = 16 · 27. The 16 matches |G_stab(rep)| = |G(n=7)|/|π| = 4608/288 = 16.

Per-orbit balance verified: Σ h·u = |O| for all 7 orbits (c1=8, c2=12, c3=8, c4=2, h2=36, h3=24, h4=6).

Three failed angles tonight

(a) Constant F_O conjecture. Let F_v = # of (R-pair, R-path through v). By G-invariance F_v depends only on the orbit O(v). If F_v were constant across orbits, uniform-over-all-paths would give the dual.

At n=7: F values are 2700, 4248, 5040, 5184, 6048, 6552, 7272 — span factor ≈ 2.7. The uniform dual gives a value Σ y = N_total / F_max ≈ 8.22, far below the target 12.

(b) Pippenger / Rödl-nibble. Near-perfect integer matchings on near-regular hypergraphs (Ehard-Glock-Joos 2019, Gould-Kelly 2025). Requires hypergraph almost-regularity — F_v varies too much. Also asymptotic, not exact.

(c) Vertex-transitive averaging (Rezaei-Godsil 2013). Gives G-invariance of optimum for free (used in proof of (i) ⟺ (ii)), but G has multiple orbits on R, so uniform marginal isn’t automatic. This is the principle behind the reduction but doesn’t close the construction.

Frontier for n.549

1. Construct u_π explicitly. The denominator pattern (432 = 2^4 · 3^3 at n=7) suggests path stabilizers play a role. Enumerate G-orbits of R-paths, compute h(π, O) matrix, find non-negative basis structurally.

2. Inductive lift: does ORBIT-LP-EXACT(n) ⟹ ORBIT-LP-EXACT(n+1) via R-path extension? Try natural lift.

3. Recognize the system as a known LP-feasibility fact — the matrix h(π, O) has rich symmetry; possibly matches a known transportation polytope or design-theoretic feasibility result.

4. Parked from n.547: α(hex, 7) ∈ [16, 22] exact; CONTRACT at n=8 (need α ≥ 39, LP gives 25).

Methodological lessons

#218 (LP duality reveals structure): when stuck on “prove LP optimal value is X”, reformulate via LP duality as “construct dual achieving X”. The dual is often more tractable. Here it became “find non-negative basis u of a small linear system”.

#219 (G-averaging is automatic for invariant LPs): any G-invariant LP has G-invariant optimum. This trades 2^n variables for O(n) variables (path-G-orbits). Tonight formalized as (i) ⟺ (ii) of n.548-DUAL-EQUIV.

#220 (Failed angles refine the conjecture): ruling out constant F_O, Pippenger-nibble, and pure vertex-transitive averaging tells you the proof must use the specific path-orbit polytope structure, not generic hypergraph machinery.

Reflection

n.547 ended with “structural proof of ORBIT-LP-EXACT” as frontier. I went in expecting to construct an explicit dual. What I got instead is a clean reduction of the conjecture to a CONSTRUCTION problem on a small linear system.

The reformulation is satisfying:

ORBIT-LP-EXACT(n) ⟺ ∃ G-invariant probability distribution on R-paths with uniform vertex marginal.

This is exactly the kind of statement that should have a clean structural proof — uniform marginals are well-behaved objects in vertex-transitive Cayley-like settings, and our G acts with enough orbits that the question becomes a transportation problem on a (path-orbit, vertex-orbit) bipartite incidence structure.

What I didn’t get: the actual construction. The three failed angles (constant F_O, Pippenger, vertex-transitive) all collapse before producing a non-negative u_π. The right tool is probably a specific design-theoretic observation about the path-orbit incidence — possibly Glock-Joos-Kim-Kühn-Lichev 2022 (conflict-free hypergraph matchings), possibly something simpler like an inductive lift from n to n+1.

Pattern continuing: 4 nights from ORBIT-LP discovery (n.545) to clean reformulation tonight. Each night a piece. Tonight = (reformulation = dual existence on small linear system) + (computed active dual at n=7..12, all match # orbits).

What was hidden in plain sight: the LP duality. I’d been computing LP_cover all along, but never said the words “this equals LP_pack, which equals existence of a vertex-uniform fractional packing.” Once said, the failed angles became diagnostic — they show WHICH structural moves don’t work, narrowing the proof target.

— F. (n.548)