Fewest triangles for a given number of edges

# Fewest triangles for a given number of edges ## Goal `build.py` exposes `build(n: int, e: int, time_budget: float, seed: int) -> list[tuple[int, int]]`: a simple graph on the vertex set `range(n)` with exactly `e` distinct edges (no loops, no repeated edges, either endpoint order). Minimise the number of triangles. This is the Erdős–Rademacher problem. Mantel says `e <= n^2/4` allows zero triangles; every instance here has more edges than that, so triangles are forced, and the question is how few. Asymptotically the answer is Razborov's theorem (2008): the minimum triangle density at edge density `rho` is attained by complete multipartite graphs with all parts equal but one smaller part. That asymptotic curve is AlphaEvolve problem 46 ("minimal triangle density in graphs", Section 6.27 of arXiv:2511.02864), where AlphaEvolve matched the known optimum. The exact finite version is sharper: Lovász and Simonovits (1975) conjectured the extremal graphs for every `(n, e)`, and Liu, Pikhurko and Staden (Forum Math. Pi 2020, arXiv:1712.00633) proved it for all `n >= n0` with edge density bounded away from 1 (Theorem 1.9) and stated it for every `n` as their Conjecture 1.11. For the small `n` here nothing is proven. Beat a record and you have a counterexample to that conjecture. ## Metric metric = mean over instances of best_known(n, e) / triangles(n, e) The eval validates every edge (two distinct integers in `range(n)`), rejects duplicates, requires exactly `e` edges, and counts triangles itself from the adjacency it builds. An invalid answer on any instance 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 `h*(n, e)` from Definition 1.1 of Liu–Pikhurko–Staden: take the complete `k`-partite graph with the listed part sizes (the first `k-1` parts balanced, the last part as small as possible) and remove `m` edges from one vertex of the last part to the next-to-last part. The eval recomputes `h*` from that definition at start-up and refuses to run if the table disagrees. | n | e | best-known triangles | construction | proven optimal? | |---|---|---|---|---| | 12 | 40 | 24 | parts 6,5,1 minus 1 edge | no; conjectured (LS 1975, LPS Conj. 1.11) | | 16 | 70 | 48 | parts 8,7,1 minus 1 edge | no; conjectured | | 16 | 100 | 303 | parts 4,4,3,3,2 minus 1 edge | no; conjectured | | 20 | 120 | 189 | parts 9,8,3 minus 3 edges | no; conjectured | | 20 | 140 | 384 | parts 6,6,6,2 minus 4 edges | no; conjectured | | 30 | 250 | 364 | parts 14,14,2 minus 2 edges | no; conjectured | | 30 | 320 | 1386 | parts 9,9,9,3 minus 4 edges | no; conjectured | | 40 | 420 | 399 | parts 19,19,2 minus 17 edges | no; conjectured | | 50 | 700 | 1817 | parts 23,23,4 minus 13 edges | no; conjectured | Source: Liu, Pikhurko, Staden, "The exact minimum number of triangles in graphs with given order and size", Definition 1.1 (the value), Proposition 1.8 (it is the minimum over the whole Lovász–Simonovits family), Theorem 1.9 (optimal for large `n`), Conjecture 1.11 (optimal for all `n`). Sanity checks done when this pack was built: the table equals the minimum over every complete multipartite graph with any part sizes plus the star removal (all `n <= 14`, all `e`), and equals the true minimum by exhaustive search at `n = 7`. ## 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_INSTANCES=12:40,16:70` runs a subset of the instances (default all nine). - `ZT_EVAL_NS=12,16` keeps only the instances with those `n`. - `ZT_EVAL_PER_INSTANCE_SECONDS=2` shortens the per-instance budget (default 10, so a full eval is about 90 s plus validation). ## Ideas that are known to matter (check the journal before repeating one) - Implement the Lovász–Simonovits construction first: it scores exactly 1.0 and is the baseline everything else is measured against. The research question is whether anything beats it at small `n`. Be warned that the landscape is benign: the greedy baseline already ties most records, and adding random kicks to it tied all of them up to `n = 30` within 2 s when this pack was built. Matching is not news; beating is. - The extremal family is wider than the single construction (LPS Definition 1.3): with `m = 0` any triangle-free graph with the right number of edges may replace the bipartite graph between the two smallest parts. Enumerate that family before searching blindly. - Bitmask adjacency makes the triangle count of a pair `(u, v)` one `popcount`; a swap move (drop the edge in most triangles, add the non-edge in fewest) costs `O(n)`, so simulated annealing or tabu search over swaps runs millions of moves inside the budget. - Structure beats randomness: near-multipartite graphs with a few "bad" edges inside parts are where the finite-`n` corrections live (LPS Section 3). Search over partitions plus a small perturbation set rather than over all graphs. Write one honest line in `NOTES.md`: the idea, and which instance 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.