{"id":"turan-tetrahedron","name":"Tetrahedron-free 3-graphs, maximum size","family":"extremal-graphs","description":"Turán's 1941 problem at finite n: the largest 3-uniform hypergraph on n vertices with no tetrahedron K_4^(3), for n in {9, 11, 13, 16, 20, 24}. Scored against Turán's construction, which is proven optimal for n <= 13 and conjectured optimal beyond (AlphaEvolve problem 37).","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["build.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Tetrahedron-free 3-graphs, maximum size\n\n## Goal\n\n`build.py` exposes `build(n: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]`:\na 3-uniform hypergraph on the vertex set `range(n)`, given as a list of triples of distinct vertices\n(any order inside a triple, no repeated triples). No four vertices may carry all four of their\ntriples, i.e. the hypergraph contains no tetrahedron `K_4^(3)`. Maximise the number of triples.\n\nThis is Turán's 1941 problem, the oldest open question in extremal hypergraph theory. Turán's\nconstruction splits the vertices into three parts `V0, V1, V2` as equal as possible and takes every\ntriple with one vertex in each part, plus every triple with two vertices in `Vi` and one in\n`V(i+1 mod 3)`. Asymptotically that is `5/9` of all triples; Razborov's flag-algebra upper bound is\n`0.5616...`. Nobody has ever found a tetrahedron-free 3-graph with more triples than Turán's\nconstruction at any `n`, although there are exponentially many non-isomorphic constructions that tie\nit (Brown, Kostochka, Fon-der-Flaass, Frohmader). Google DeepMind's AlphaEvolve (problem 37 of the\n\"Mathematical Exploration and Discovery at Scale\" repository, Nov 2025) recovered the `5/9`\nconstruction in its weighted formulation and found nothing better. Beat any record below and you\nhave a counterexample to Turán's (3,4)-conjecture.\n\n## Metric\n\n    metric = mean over n in {9, 11, 13, 16, 20, 24} of  triples(n) / best_known(n)\n\nThe eval validates every triple (three distinct integers in `range(n)`, no duplicates) and checks\nevery 4-subset of the vertices for a tetrahedron before it counts anything. An invalid answer on\nany `n` is a failed run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver, so your\nmethod must be robust to its starting point.\n\n## Records\n\n| n | best-known triples | source | proven optimal? |\n|---|---|---|---|\n| 9 | 54 | Turán's construction, parts 3,3,3 | yes (Spencer 1993: conjecture verified for n <= 13) |\n| 11 | 102 | Turán's construction, parts 4,4,3 | yes (Spencer 1993) |\n| 13 | 174 | Turán's construction, parts 5,4,4 | yes (Spencer 1993) |\n| 16 | 335 | Turán's construction, parts 6,5,5 | no, conjectured (Turán 1941) |\n| 20 | 672 | Turán's construction, parts 7,7,6 | no, conjectured (Turán 1941) |\n| 24 | 1184 | Turán's construction, parts 8,8,8 | no, conjectured (Turán 1941) |\n\nClosed form (Turán's (3,4)-conjecture as stated in Frohmader, arXiv:0806.4208, Conjecture 1.2):\nfor `n = 3k`, `3k+1`, `3k+2` the count is `5k^3/2 - 3k^2/2`, `5k^3/2 + k^2 - k/2`,\n`5k^3/2 + 7k^2/2 + k`. The verification for `n <= 13` is credited to T. Spencer (1993) in that\npaper; the upper bound `0.5616` is Razborov (2010). The AlphaEvolve repository lists this as\nproblem 37 (Section 6.20 of arXiv:2511.02864), matched, not improved.\n\n## Constraints\n\n- Standard library only. No numpy, no networkx. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval tolerates 25% plus 3 s over it.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating quickly\n\n- `ZT_EVAL_NS=9,11` runs a subset of the instances (default `9,11,13,16,20,24`).\n- `ZT_EVAL_PER_N_SECONDS=2` shortens the per-`n` budget (default 15, so a full eval is about 90 s\n  plus validation).\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Implement Turán's construction first: it scores exactly 1.0 and is the baseline everything\n  else is measured against. The research question is whether anything beats it.\n- The tying constructions are all \"Turán-like\": Brown/Kostochka's are described by which triples\n  are *missing* (the complement is a covering of all 4-sets by triples, i.e. a Turán (n,4,3)\n  system with `C(n,3) - record` triples). Explore the complement side: a smaller covering of the\n  4-sets is the same thing as a bigger tetrahedron-free 3-graph.\n- Local search over triples with a tetrahedron oracle is cheap: adding triple `abc` creates a\n  tetrahedron iff some `d` has `abd`, `acd`, `bcd` already present. Tabu search or simulated\n  annealing on \"add / remove / swap a triple\" runs millions of moves in the budget at `n = 24`.\n- Start from a record construction and apply vertex-removal / re-insertion (Kostochka's trick\n  for `n` not divisible by 3) to explore the plateau of equal-size constructions.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for turan-tetrahedron. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED             seed handed to build()\n  ZT_EVAL_PER_N_SECONDS    time budget per n (default 15)\n  ZT_EVAL_NS               comma-separated n values (default \"9,11,13,16,20,24\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom itertools import combinations\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_N_SECONDS\", \"15\"))\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", \"9,11,13,16,20,24\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known number of triples in a tetrahedron-free 3-graph on n vertices: Turán's 1941\n# construction (parts as equal as possible; triples with one vertex in each part, or two in\n# part i and one in part i+1 mod 3). Closed form for n = 3k, 3k+1, 3k+2:\n# 5k^3/2 - 3k^2/2, 5k^3/2 + k^2 - k/2, 5k^3/2 + 7k^2/2 + k (Turán's (3,4)-conjecture).\n# Proven optimal for n <= 13 (Spencer 1993, via Frohmader arXiv:0806.4208); conjectured beyond.\n# AlphaEvolve problem 37 matched the 5/9 density of this construction and found nothing better.\nRECORDS = {9: 54, 11: 102, 13: 174, 16: 335, 20: 672, 24: 1184}\n\n\ndef turan_count(n: int) -> int:\n    q, r = divmod(n, 3)\n    a, b, c = [q + 1] * r + [q] * (3 - r)\n    return a * b * c + a * (a - 1) // 2 * b + b * (b - 1) // 2 * c + c * (c - 1) // 2 * a\n\n\nassert all(turan_count(n) == v for n, v in RECORDS.items()), \"RECORDS disagree with Turán's construction\"\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in {path.name}: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef validate(triples: list, n: int) -> int:\n    \"\"\"Return the number of distinct triples after checking every one and the tetrahedron-freeness.\"\"\"\n    if not isinstance(triples, (list, tuple)):\n        fail(f\"build({n}) must return a list of triples\", \"wrong_answer\")\n    edges: set[tuple[int, int, int]] = set()\n    for t in triples:\n        try:\n            a, b, c = t\n        except Exception:\n            fail(f\"build({n}) returned a non-triple {t!r}\", \"wrong_answer\")\n        if not all(isinstance(x, int) and not isinstance(x, bool) for x in (a, b, c)):\n            fail(f\"build({n}) returned a triple with non-integer vertices {t!r}\", \"wrong_answer\")\n        if not all(0 <= x < n for x in (a, b, c)) or len({a, b, c}) != 3:\n            fail(f\"build({n}) returned an invalid triple {t!r} (vertices must be distinct and in range(n))\", \"wrong_answer\")\n        key = tuple(sorted((a, b, c)))\n        if key in edges:\n            fail(f\"build({n}) returned the triple {key} twice\", \"wrong_answer\")\n        edges.add(key)\n    for a, b, c, d in combinations(range(n), 4):\n        if (a, b, c) in edges and (a, b, d) in edges and (a, c, d) in edges and (b, c, d) in edges:\n            fail(f\"build({n}): vertices {a},{b},{c},{d} span a tetrahedron\", \"wrong_answer\")\n    return len(edges)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"build.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import build as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import build.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"build\"):\n        fail(\"build.py must define build(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"tetra|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    for n in NS:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            triples = cand.build(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"build({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"build({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        count = validate(triples, n)\n        per_n[n] = {\"triples\": count, \"record\": RECORDS[n], \"ratio\": round(count / RECORDS[n], 6), \"seconds\": round(elapsed, 2)}\n        if count > RECORDS[n]:\n            beaten.append(n)\n    metric = sum(v[\"ratio\"] for v in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_n\": per_n, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"build.py":"\"\"\"Baseline: random greedy maximal tetrahedron-free 3-graphs, restarted until the budget is used.\n\nScores roughly 0.8 of the records. Turán's construction reaches 1.0; beat that.\n\"\"\"\n\nimport random\nimport time\nfrom itertools import combinations\n\n\ndef build(n: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]:\n    rng = random.Random(seed)\n    start = time.perf_counter()\n    triples = list(combinations(range(n), 3))\n    best: list[tuple[int, int, int]] = []\n    while True:\n        rng.shuffle(triples)\n        edges: set[tuple[int, int, int]] = set()\n        for a, b, c in triples:\n            ok = True\n            for d in range(n):\n                if d == a or d == b or d == c:\n                    continue\n                if (tuple(sorted((a, b, d))) in edges and tuple(sorted((a, c, d))) in edges\n                        and tuple(sorted((b, c, d))) in edges):\n                    ok = False\n                    break\n            if ok:\n                edges.add((a, b, c))\n        if len(edges) > len(best):\n            best = sorted(edges)\n        if time.perf_counter() - start > 0.8 * time_budget:\n            break\n    return best\n"}}