{"id":"min-triangles-fixed-edges","name":"Fewest triangles for a given number of edges","family":"extremal-graphs","description":"The Erdős–Rademacher problem at finite n: a graph on n vertices with exactly e edges and as few triangles as possible, for nine (n, e) instances with n up to 50 above the Mantel threshold. Scored against the Lovász–Simonovits construction, proven optimal for large n (Liu–Pikhurko–Staden 2020) and conjectured for all n; the asymptotic form is AlphaEvolve problem 46 (Razborov's theorem).","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":"# Fewest triangles for a given number of edges\n\n## Goal\n\n`build.py` exposes `build(n: int, e: int, time_budget: float, seed: int) -> list[tuple[int, int]]`:\na simple graph on the vertex set `range(n)` with exactly `e` distinct edges (no loops, no repeated\nedges, either endpoint order). Minimise the number of triangles.\n\nThis is the Erdős–Rademacher problem. Mantel says `e <= n^2/4` allows zero triangles; every\ninstance here has more edges than that, so triangles are forced, and the question is how few.\nAsymptotically the answer is Razborov's theorem (2008): the minimum triangle density at edge\ndensity `rho` is attained by complete multipartite graphs with all parts equal but one smaller\npart. That asymptotic curve is AlphaEvolve problem 46 (\"minimal triangle density in graphs\",\nSection 6.27 of arXiv:2511.02864), where AlphaEvolve matched the known optimum. The exact finite\nversion is sharper: Lovász and Simonovits (1975) conjectured the extremal graphs for every `(n, e)`,\nand Liu, Pikhurko and Staden (Forum Math. Pi 2020, arXiv:1712.00633) proved it for all `n >= n0`\nwith edge density bounded away from 1 (Theorem 1.9) and stated it for every `n` as their\nConjecture 1.11. For the small `n` here nothing is proven. Beat a record and you have a\ncounterexample to that conjecture.\n\n## Metric\n\n    metric = mean over instances of  best_known(n, e) / triangles(n, e)\n\nThe eval validates every edge (two distinct integers in `range(n)`), rejects duplicates, requires\nexactly `e` edges, and counts triangles itself from the adjacency it builds. An invalid answer on\nany instance 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`h*(n, e)` from Definition 1.1 of Liu–Pikhurko–Staden: take the complete `k`-partite graph with the\nlisted part sizes (the first `k-1` parts balanced, the last part as small as possible) and remove\n`m` edges from one vertex of the last part to the next-to-last part. The eval recomputes `h*` from\nthat definition at start-up and refuses to run if the table disagrees.\n\n| n | e | best-known triangles | construction | proven optimal? |\n|---|---|---|---|---|\n| 12 | 40 | 24 | parts 6,5,1 minus 1 edge | no; conjectured (LS 1975, LPS Conj. 1.11) |\n| 16 | 70 | 48 | parts 8,7,1 minus 1 edge | no; conjectured |\n| 16 | 100 | 303 | parts 4,4,3,3,2 minus 1 edge | no; conjectured |\n| 20 | 120 | 189 | parts 9,8,3 minus 3 edges | no; conjectured |\n| 20 | 140 | 384 | parts 6,6,6,2 minus 4 edges | no; conjectured |\n| 30 | 250 | 364 | parts 14,14,2 minus 2 edges | no; conjectured |\n| 30 | 320 | 1386 | parts 9,9,9,3 minus 4 edges | no; conjectured |\n| 40 | 420 | 399 | parts 19,19,2 minus 17 edges | no; conjectured |\n| 50 | 700 | 1817 | parts 23,23,4 minus 13 edges | no; conjectured |\n\nSource: Liu, Pikhurko, Staden, \"The exact minimum number of triangles in graphs with given order\nand size\", Definition 1.1 (the value), Proposition 1.8 (it is the minimum over the whole\nLovász–Simonovits family), Theorem 1.9 (optimal for large `n`), Conjecture 1.11 (optimal for all\n`n`). Sanity checks done when this pack was built: the table equals the minimum over every\ncomplete multipartite graph with any part sizes plus the star removal (all `n <= 14`, all `e`), and\nequals the true minimum by exhaustive search at `n = 7`.\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_INSTANCES=12:40,16:70` runs a subset of the instances (default all nine).\n- `ZT_EVAL_NS=12,16` keeps only the instances with those `n`.\n- `ZT_EVAL_PER_INSTANCE_SECONDS=2` shortens the per-instance budget (default 10, so a full eval is\n  about 90 s plus validation).\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Implement the Lovász–Simonovits construction first: it scores exactly 1.0 and is the baseline\n  everything else is measured against. The research question is whether anything beats it at\n  small `n`. Be warned that the landscape is benign: the greedy baseline already ties most\n  records, and adding random kicks to it tied all of them up to `n = 30` within 2 s when this\n  pack was built. Matching is not news; beating is.\n- The extremal family is wider than the single construction (LPS Definition 1.3): with `m = 0`\n  any triangle-free graph with the right number of edges may replace the bipartite graph between\n  the two smallest parts. Enumerate that family before searching blindly.\n- Bitmask adjacency makes the triangle count of a pair `(u, v)` one `popcount`; a swap move\n  (drop the edge in most triangles, add the non-edge in fewest) costs `O(n)`, so simulated\n  annealing or tabu search over swaps runs millions of moves inside the budget.\n- Structure beats randomness: near-multipartite graphs with a few \"bad\" edges inside parts are\n  where the finite-`n` corrections live (LPS Section 3). Search over partitions plus a small\n  perturbation set rather than over all graphs.\n\nWrite one honest line in `NOTES.md`: the idea, and which instance 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 min-triangles-fixed-edges. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                  seed handed to build()\n  ZT_EVAL_PER_INSTANCE_SECONDS  time budget per (n, e) instance (default 10)\n  ZT_EVAL_INSTANCES             comma-separated \"n:e\" labels (default \"12:40,16:70,16:100,20:120,20:140,30:250,30:320,40:420,50:700\")\n  ZT_EVAL_NS                    optional comma-separated n values: keep only the instances with those n\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_INSTANCE_SECONDS\", \"10\"))\nINSTANCES = [tuple(int(x) for x in s.split(\":\")) for s in\n             os.environ.get(\"ZT_EVAL_INSTANCES\", \"12:40,16:70,16:100,20:120,20:140,30:250,30:320,40:420,50:700\").split(\",\")]\nif os.environ.get(\"ZT_EVAL_NS\"):\n    _keep = {int(x) for x in os.environ[\"ZT_EVAL_NS\"].split(\",\")}\n    INSTANCES = [inst for inst in INSTANCES if inst[0] in _keep]\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 minimum number of triangles in a graph with n vertices and e edges: h*(n, e) of\n# Liu, Pikhurko, Staden, \"The exact minimum number of triangles in graphs with given order and\n# size\" (Forum Math. Pi 2020, arXiv:1712.00633), Definition 1.1 - the Lovász-Simonovits (1975)\n# construction. Proven optimal for all large n (their Theorem 1.9); Conjecture 1.11 there says it\n# is optimal for every n. Each value is the triangle count of an explicit graph: a complete\n# k-partite graph with the listed part sizes minus a star of m edges from one vertex of the last\n# part into the next-to-last part. Beating one means a counterexample to Conjecture 1.11.\nRECORDS = {\n    (12, 40): 24,      # parts 6,5,1  m=1\n    (16, 70): 48,      # parts 8,7,1  m=1\n    (16, 100): 303,    # parts 4,4,3,3,2  m=1\n    (20, 120): 189,    # parts 9,8,3  m=3\n    (20, 140): 384,    # parts 6,6,6,2  m=4\n    (30, 250): 364,    # parts 14,14,2  m=2\n    (30, 320): 1386,   # parts 9,9,9,3  m=4\n    (40, 420): 399,    # parts 19,19,2  m=17\n    (50, 700): 1817,   # parts 23,23,4  m=13\n}\n\n\ndef turan_edges(k: int, n: int) -> int:\n    q, r = divmod(n, k)\n    sizes = [q + 1] * r + [q] * (k - r)\n    return sum(a * b for i, a in enumerate(sizes) for b in sizes[i + 1:])\n\n\ndef h_star(n: int, e: int) -> int:\n    \"\"\"LPS Definition 1.1, recomputed here so a typo in RECORDS cannot survive.\"\"\"\n    k = 1\n    while e > turan_edges(k, n):\n        k += 1\n    if k == 1:\n        return 0\n    a_k = 1\n    while a_k * (n - a_k) + turan_edges(k - 1, n - a_k) < e:\n        a_k += 1\n    q, r = divmod(n - a_k, k - 1)\n    sizes = [q + 1] * r + [q] * (k - 1 - r) + [a_k]\n    m = sum(a * b for i, a in enumerate(sizes) for b in sizes[i + 1:]) - e\n    tri = sum(sizes[h] * sizes[i] * sizes[j] for h, i, j in combinations(range(k), 3))\n    return tri - m * sum(sizes[:k - 2])\n\n\nassert all(h_star(n, e) == v for (n, e), v in RECORDS.items()), \"RECORDS disagree with LPS Definition 1.1\"\nassert all(e > turan_edges(2, n) for n, e in RECORDS), \"every instance must force at least one triangle\"\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(edges: list, n: int, e: int) -> int:\n    \"\"\"Check the edge list (exactly e distinct edges on range(n), no loops) and count its triangles.\"\"\"\n    label = f\"build({n}, {e})\"\n    if not isinstance(edges, (list, tuple)):\n        fail(f\"{label} must return a list of edges\", \"wrong_answer\")\n    seen: set[tuple[int, int]] = set()\n    adj = [0] * n\n    for p in edges:\n        try:\n            u, v = p\n        except Exception:\n            fail(f\"{label} returned a non-edge {p!r}\", \"wrong_answer\")\n        if not all(isinstance(x, int) and not isinstance(x, bool) for x in (u, v)):\n            fail(f\"{label} returned an edge with non-integer endpoints {p!r}\", \"wrong_answer\")\n        if not (0 <= u < n and 0 <= v < n) or u == v:\n            fail(f\"{label} returned an invalid edge {p!r} (endpoints must be distinct and in range(n))\", \"wrong_answer\")\n        key = (u, v) if u < v else (v, u)\n        if key in seen:\n            fail(f\"{label} returned the edge {key} twice\", \"wrong_answer\")\n        seen.add(key)\n        adj[u] |= 1 << v\n        adj[v] |= 1 << u\n    if len(seen) != e:\n        fail(f\"{label} returned {len(seen)} edges, expected exactly {e}\", \"wrong_answer\")\n    return sum((adj[u] & adj[v]).bit_count() for u, v in seen) // 3\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 ex:\n        fail(f\"import build.py failed: {ex!r}\", \"compile_error\")\n    if not hasattr(cand, \"build\"):\n        fail(\"build.py must define build(n, e, time_budget, seed)\", \"compile_error\")\n    if not INSTANCES:\n        fail(\"no instances selected\", \"error\")\n\n    seed_int = random.Random(f\"mintri|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for n, e in INSTANCES:\n        if (n, e) not in RECORDS:\n            fail(f\"no record for instance {n}:{e}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            edges = cand.build(n, e, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as ex:\n            fail(f\"build({n}, {e}) raised {ex!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"build({n}, {e}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        tri = validate(edges, n, e)\n        record = RECORDS[(n, e)]\n        label = f\"{n}:{e}\"\n        per_instance[label] = {\"triangles\": tri, \"record\": record, \"ratio\": round(record / max(tri, 1), 6),\n                               \"seconds\": round(elapsed, 2)}\n        if tri < record:\n            beaten.append(label)\n    metric = sum(v[\"ratio\"] for v in per_instance.values()) / len(per_instance)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per_instance, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"build.py":"\"\"\"Baseline: random graph with e edges, then greedy edge swaps until no swap lowers the count.\n\nTies several records and sits within a few percent of the rest. The Lovász-Simonovits construction\nreaches 1.0; beat that.\n\"\"\"\n\nimport random\nimport time\nfrom itertools import combinations\n\n\ndef build(n: int, e: int, time_budget: float, seed: int) -> list[tuple[int, int]]:\n    rng = random.Random(seed)\n    start = time.perf_counter()\n    pairs = list(combinations(range(n), 2))\n    rng.shuffle(pairs)\n    edges, non = pairs[:e], pairs[e:]\n    adj = [0] * n\n    for u, v in edges:\n        adj[u] |= 1 << v\n        adj[v] |= 1 << u\n\n    def tri(p):  # triangles through the pair p if it is (or were) an edge\n        return (adj[p[0]] & adj[p[1]]).bit_count()\n\n    def toggle(p):\n        adj[p[0]] ^= 1 << p[1]\n        adj[p[1]] ^= 1 << p[0]\n\n    while time.perf_counter() - start < 0.8 * time_budget and non:\n        i = max(range(len(edges)), key=lambda k: tri(edges[k]))\n        toggle(edges[i])\n        loss = tri(edges[i])\n        j = min(range(len(non)), key=lambda k: tri(non[k]))\n        if tri(non[j]) >= loss:  # local optimum for single swaps\n            toggle(edges[i])\n            break\n        toggle(non[j])\n        edges[i], non[j] = non[j], edges[i]\n    return edges\n"}}