Tetrahedron-free 3-graphs, maximum size

# Tetrahedron-free 3-graphs, maximum size ## Goal `build.py` exposes `build(n: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]`: a 3-uniform hypergraph on the vertex set `range(n)`, given as a list of triples of distinct vertices (any order inside a triple, no repeated triples). No four vertices may carry all four of their triples, i.e. the hypergraph contains no tetrahedron `K_4^(3)`. Maximise the number of triples. This is Turán's 1941 problem, the oldest open question in extremal hypergraph theory. Turán's construction splits the vertices into three parts `V0, V1, V2` as equal as possible and takes every triple with one vertex in each part, plus every triple with two vertices in `Vi` and one in `V(i+1 mod 3)`. Asymptotically that is `5/9` of all triples; Razborov's flag-algebra upper bound is `0.5616...`. Nobody has ever found a tetrahedron-free 3-graph with more triples than Turán's construction at any `n`, although there are exponentially many non-isomorphic constructions that tie it (Brown, Kostochka, Fon-der-Flaass, Frohmader). Google DeepMind's AlphaEvolve (problem 37 of the "Mathematical Exploration and Discovery at Scale" repository, Nov 2025) recovered the `5/9` construction in its weighted formulation and found nothing better. Beat any record below and you have a counterexample to Turán's (3,4)-conjecture. ## Metric metric = mean over n in {9, 11, 13, 16, 20, 24} of triples(n) / best_known(n) The eval validates every triple (three distinct integers in `range(n)`, no duplicates) and checks every 4-subset of the vertices for a tetrahedron before it counts anything. An invalid answer on any `n` is a failed run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver, so your method must be robust to its starting point. ## Records | n | best-known triples | source | proven optimal? | |---|---|---|---| | 9 | 54 | Turán's construction, parts 3,3,3 | yes (Spencer 1993: conjecture verified for n <= 13) | | 11 | 102 | Turán's construction, parts 4,4,3 | yes (Spencer 1993) | | 13 | 174 | Turán's construction, parts 5,4,4 | yes (Spencer 1993) | | 16 | 335 | Turán's construction, parts 6,5,5 | no, conjectured (Turán 1941) | | 20 | 672 | Turán's construction, parts 7,7,6 | no, conjectured (Turán 1941) | | 24 | 1184 | Turán's construction, parts 8,8,8 | no, conjectured (Turán 1941) | Closed form (Turán's (3,4)-conjecture as stated in Frohmader, arXiv:0806.4208, Conjecture 1.2): for `n = 3k`, `3k+1`, `3k+2` the count is `5k^3/2 - 3k^2/2`, `5k^3/2 + k^2 - k/2`, `5k^3/2 + 7k^2/2 + k`. The verification for `n <= 13` is credited to T. Spencer (1993) in that paper; the upper bound `0.5616` is Razborov (2010). The AlphaEvolve repository lists this as problem 37 (Section 6.20 of arXiv:2511.02864), matched, not improved. ## Constraints - Standard library only. No numpy, no networkx. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval tolerates 25% plus 3 s over it. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_NS=9,11` runs a subset of the instances (default `9,11,13,16,20,24`). - `ZT_EVAL_PER_N_SECONDS=2` shortens the per-`n` budget (default 15, so a full eval is about 90 s plus validation). ## Ideas that are known to matter (check the journal before repeating one) - Implement Turán's construction first: it scores exactly 1.0 and is the baseline everything else is measured against. The research question is whether anything beats it. - The tying constructions are all "Turán-like": Brown/Kostochka's are described by which triples are *missing* (the complement is a covering of all 4-sets by triples, i.e. a Turán (n,4,3) system with `C(n,3) - record` triples). Explore the complement side: a smaller covering of the 4-sets is the same thing as a bigger tetrahedron-free 3-graph. - Local search over triples with a tetrahedron oracle is cheap: adding triple `abc` creates a tetrahedron iff some `d` has `abd`, `acd`, `bcd` already present. Tabu search or simulated annealing on "add / remove / swap a triple" runs millions of moves in the budget at `n = 24`. - Start from a record construction and apply vertex-removal / re-insertion (Kostochka's trick for `n` not divisible by 3) to explore the plateau of equal-size constructions. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.