The following code implements an exhaustive search using backtracking to compute the maximum size of a 3-uniform set system on [n] with VC-dimension at most 2.<\/p>\n\n\n\n
In practice, this program only works for small values of n. For our purpose, we only need the result for n=6 and n=7. For example, on a typical personal computer, when n = 7, this C program takes only about 1 minute to verify that the size of the largest 3-uniform set system on [7] with the given VC-dimension is at most 16.<\/p>\n\n\n\n
The detailed algorithm is provided in the Appendix.<\/p>\n\n\n\n
The following code was written by Prof. Jian Wang (wangjian01@tyut.edu.cn).<\/p>\n\n\n\n
\/*A search using back-tracking*\/\n#include <iostream>\n#include<fstream>\n#include <algorithm>\n#include<ctime>\n#include <string>\n#include <bitset>\n#include <math.h>\nusing namespace std;\n#define N 50\n#define M 10000\n#define L 7\n#define K 3\n\n\nint n, k, tmp,sum=1,pos;\n\nint setNum[M]; \/\/the set of all 0-1 sequences with k 1's\nint traceList[M][N]; \/\/traceList[i][j], j=1,2,...,2^k, list all possible traces of sequences setNum[i]\nint traceList2[N][M][N]; \/\/traceList2[q][i][j] gives whether the trace traceList[i][j] is shattered in run q of the backtracking\nint current[M]; \/\/the list in backtracking\nint max = 1;\nfstream file;\n\nint number_of_1(int m) \/\/ return the number of 1's in binary m\n{\n int count = 0;\n for (int i = 0; i < n; i++) {\n if (((m >> i) & 1) == 1) {\n count++;\n }\n }\n return count;\n}\nstring index_of_1(int m) \/\/return the index of 1 in binary m\n{\n string set = \"\";\n for (int i = 0; i < n; i++) {\n if (((m >> i) & 1) == 1) {\n set = set + to_string(i + 1);\n }\n }\n if (set == \"\") set = \"empty\";\n return set;\n}\n\nint generateSets()\/\/ generate all 0-1 sequences with k 1's as an integer\n{\n sum = 1;\n for (int i = 0; i < pow(2, n); i++)\n {\n tmp = number_of_1(i);\n if (tmp == k)\n {\n setNum[sum] = i;\n \/\/ bitset<7> bit(i);\n \/\/ cout << bit << endl;\n sum++;\n }\n }\n sum--;\n return 0;\n}\n\nint generateTracelist()\/\/ generate all possible traces of sequences setNum[i]\n{\n for (int i = 1; i <= sum; i++)\n {\n bitset<L> bit1(setNum[i]);\n tmp = setNum[i]; \n for (int j = 0; j < pow(2, k); j++)\n {\n bitset<K> bit2(j);\n int count = 0;\n for (int p = 0; p < n; p++) {\n if (((tmp >> p) & 1) == 1) {\n\n bit1[p] = bit2[count];\n count++;\n }\n }\n traceList[i][j+1] = bit1.to_ullong();\n }\n }\n return 1;\n}\n\nint showList()\n{\n file.open(\"full.txt\", ios::out);\n if (!file) {\n cerr << \"Unable to open file!\" << endl;\n return 1; \/\/ fail\n }\n for (int i = 1; i <=sum; i++)\n {\n file <<i<<\"->\" << index_of_1(setNum[i]) << \":\";\n for (int j = 1; j <=pow(2, k); j++)\n {\n file << index_of_1(traceList[i][j]) << \"|\";\n }\n file << endl;\n }\n file.close();\n return 0;\n}\n\nint checkList()\n{\n file.open(\"checkList.txt\", ios::out);\n if (!file) {\n cerr << \"Unable to open file!\" << endl;\n return 1; \/\/ fail\n }\n pos = 13;\n current[1] = 4; current[2] = 6; current[3] = 8; current[4] = 9;\n current[5] = 10; current[6] = 11; current[7] = 14; current[8] = 15;\n current[9] = 16; current[10] = 17; current[11] = 18; current[12] = 19;\n current[13] = 20;\n int temlist[N];\n \n for (int i = 1; i <= pos; i++)\n {\n for (int j = 1; j <= pow(2, k); j++)\n {\n temlist[j] = 0;\n }\n int x = current[i];\/\/check the trace of x\n for (int j = 1; j <= pos; j++)\n {\n int y = current[j];\n int trace = setNum[x] & setNum[y];\n for (int p = 1; p <= pow(2, k); p++)\n {\n if (temlist[p] == 0 && trace == traceList[x][p])\n {\n temlist[p] = 1;\n }\n }\n }\n file << index_of_1(setNum[x]) << \":missing->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (temlist[j] == 0)\n {\n file << index_of_1(traceList[x][j]) << \"|\";\n }\n }\n file << \"********trace->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (temlist[j] == 1)\n {\n file << index_of_1(traceList[x][j]) << \"|\";\n }\n }\n \n file << \"*********************************************************************\" << endl;\n }\n file.close();\n return 0;\n}\n\nint maxSetVcdim2() \/\/the back-tracking\n{\n file.open(\"example.txt\", ios::out);\n if (!file) {\n cerr << \"Unable to open file!\" << endl;\n return 1; \/\/ fail\n }\n for (int i = 1; i <= sum; i++)\n {\n for (int j = 0; j <= pow(2, k); j++)\n {\n for (int p = 0; p <= pow(2, k); p++)\n {\n traceList2[p][i][j] = 0;\n }\n }\n }\n\n current[1] = 1;\n traceList2[1][1][0] = 1;\n traceList2[1][1][(int)pow(2, k)] = 1;\n pos=2;\n int max = 1;\n current[pos] = current[pos - 1];\n while (pos>1)\n {\n \/*checking output data*\/ \n \/* for (int i = 1; i < pos; i++)\n {\n int y = current[i]; \n cout << index_of_1(setNum[y]) << \":missing->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (traceList2[pos - 1][y][j] == 0)\n {\n cout<< index_of_1(traceList[y][j]) << \"|\";\n }\n }\n cout << index_of_1(setNum[y]) << \"********trace->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (traceList2[pos - 1][y][j] == 1)\n {\n cout << index_of_1(traceList[y][j]) << \"|\";\n }\n }\n cout << endl;\n }\n \/\/ getchar();\n \/*checking output data*\/\n current[pos]++;\n if (current[pos] > sum)\n {\n pos--;\n if (pos >=max) \/\/If a larger family is found then output it.\n {\n max = pos;\n file << max << \"->\";\n for (int i = 1; i <=pos; i++)\n {\n file << index_of_1(setNum[current[i]]) << \" \";\n }\n file << endl;\n file << \"*********************************************************************\" << endl;\n for (int i = 1; i <=pos; i++)\n {\n int y = current[i];\n file << index_of_1(setNum[y]) << \":missing->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (traceList2[pos][y][j] == 0)\n {\n file << index_of_1(traceList[y][j]) << \"|\";\n }\n }\n file <<\"********trace->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (traceList2[pos][y][j] == 1)\n {\n file << index_of_1(traceList[y][j]) << \"|\";\n }\n }\n file << endl;\n }\n file << \"*********************************************************************\" << endl;\n\n }\n continue;\n }\n int increaseVCdim = 0; \n \/\/if we add setNum[z] to the family, the variable used to check whether the Vc dimension is increased.\n int z = current[pos];\/\/index of the new set\n for (int j = 1; j <= pow(2, k); j++)\n {\n traceList2[pos][z][j] = 0;\n }\n traceList2[pos][z][(int)pow(2, k)] = 1;\n for (int i = 1; i <pos; i++)\n {\n int y = current[i];\n int numx = setNum[y]&setNum[z];\/\/the intersection of setNum[y] and setNum[z]\n for (int j = 1; j <= pow(2, k) - 1; j++)\n {\n if (numx == traceList[z][j])\/\/record the traces of z with sets already in the family\n {\n traceList2[pos][z][j] =1;\n }\n }\n \/\/ cout << index_of_1(numx) << \"------\" << index_of_1(setNum[z]) << \"cap\" << index_of_1(setNum[y]) << traceList2[pos][z][4] << endl;\n if (traceList2[pos-1][y][0] !=(int) pow(2, k) - 1) continue; \/\/clearly y is not shattered in this case\n \n for (int j = 1; j <= pow(2, k)-1; j++) \/\/if traces of setNum[y] is 2^k-1 before adding z, consider the new trace created by setNum[y]&setNum[z]\n {\n if (numx == traceList[y][j]&& traceList2[pos-1][y][j] == 0)\n {\n increaseVCdim = 1;\n break;\n }\n }\n if (increaseVCdim == 1) break;\n }\n traceList2[pos][z][0] = 0; \/\/update the trace of setNum[z]\n for (int j = 1; j <= pow(2, k); j++)\n {\n traceList2[pos][z][0] += traceList2[pos][z][j];\n }\n if (traceList2[pos][z][0] == (int)pow(2, k)) increaseVCdim = 1;\/\/ if z is shattered\n\n if (increaseVCdim == 0) \/\/one can add z into the current family\n {\n for (int i = 1; i < pos; i++)\n {\n int y = current[i]; \/\/copy the previous trace \n for (int j = 0; j <= pow(2, k); j++)\n {\n traceList2[pos][y][j] = traceList2[pos-1][y][j];\n }\n }\n\n for (int i = 1; i < pos; i++)\/\/update the traces \n {\n int y = current[i];\n int numx = setNum[y] & setNum[z];\n for (int j = 1; j <= pow(2, k) - 1; j++)\n {\n if (numx == traceList[y][j]&& traceList2[pos][y][j]==0)\n {\n traceList2[pos][y][j] = 1;\n traceList2[pos][y][0]++;\n }\n }\n }\n if (false&&pos == 3) {\n for (int i = 1; i <= pos; i++)\n {\n int y = current[i];\n cout << index_of_1(setNum[y]) << \":missing->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (traceList2[pos][y][j] == 0)\n {\n cout << index_of_1(traceList[y][j]) << \"|\";\n }\n }\n cout << \"********trace->\";\n for (int j = 1; j <= pow(2, k); j++)\n {\n if (traceList2[pos][y][j] == 1)\n {\n cout << index_of_1(traceList[y][j]) << \"|\";\n }\n }\n cout << endl;\n }\n \/\/ getchar();\n }\n \n pos++;\n current[pos] = current[pos - 1];\n }\n }\n file.close();\n return 1;\n}\n\nint main()\n{\n n = L;\n k = K;\n generateSets();\n generateTracelist();\n showList();\n \/\/checkList();\n \/\/ getchar();\n maxSetVcdim2();\n return 0; \n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"The following code implements an exhaustive search using backtracking to compute the maximum size of a 3-uniform set system on [n] with VC-dimension at most 2. In practice, this program only works for small values of n. For our purpose, we only need the result for n=6 and n=7. For example, on a typical personal […]<\/p>\n","protected":false},"author":12,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-510","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/posts\/510","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/comments?post=510"}],"version-history":[{"count":4,"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/posts\/510\/revisions"}],"predecessor-version":[{"id":514,"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/posts\/510\/revisions\/514"}],"wp:attachment":[{"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/media?parent=510"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/categories?post=510"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ibs.re.kr\/ecopro\/zixiangxu\/wp-json\/wp\/v2\/tags?post=510"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}