{"id":"ramsey-lower","name":"Classical Ramsey numbers, lower bounds by explicit graphs","family":"extremal-graphs","description":"A graph on N vertices with no K_k and no independent set of size l certifies R(k,l) > N. Ten open cases from R(3,10) to R(6,6), scored against the largest known witnesses (Exoo, Kalbfleisch, Kolodyazhny, Nagda-Raghavan-Thakurta) as tabulated in Radziszowski's survey.","metric":"record_ratio","direction":"maximize","tolerance":0.1,"eval_timeout_seconds":240,"agent_timeout_seconds":1800,"mutable":["graph.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":"# Classical Ramsey numbers: lower bounds by explicit graphs\n\n## Goal\n\nThe Ramsey number `R(k, l)` is the least `n` such that every graph on `n` vertices contains a clique\nof size `k` or an independent set of size `l`. A graph on `N` vertices with neither (a\n*`(k, l)`-graph*) proves `R(k, l) > N`. Only nine non-trivial values are known exactly\n(`R(3, 3..9)`, `R(4, 4) = 18`, `R(4, 5) = 25`); everything else is a pair of bounds, and every lower\nbound is an explicit graph, most of them found by Exoo's heuristic searches over the last four decades.\n\n`graph.py` exposes\n\n    graph(k: int, l: int, time_budget: float, seed: int) -> list[tuple[int, int]]\n\nreturning the edge list of a simple graph on vertices `0 .. N-1`, where `N` is one more than the\nlargest vertex index that appears (so every vertex you want counted must touch an edge). `N` is what\nyou are maximising. Instances are labelled `k-l`:\n\n| label | k | l | record N | known bounds on R(k, l) |\n|---|---|---|---|---|\n| `3-10` | 3 | 10 | 39  | 40 – 41   |\n| `3-11` | 3 | 11 | 46  | 47 – 50   |\n| `3-12` | 3 | 12 | 52  | 53 – 59   |\n| `3-13` | 3 | 13 | 60  | 61 – 68   |\n| `4-6`  | 4 | 6  | 35  | 36 – 40   |\n| `4-7`  | 4 | 7  | 48  | 49 – 58   |\n| `4-8`  | 4 | 8  | 58  | 59 – 79   |\n| `5-5`  | 5 | 5  | 42  | 43 – 46   |\n| `5-6`  | 5 | 6  | 58  | 59 – 85   |\n| `6-6`  | 6 | 6  | 101 | 102 – 160 |\n\n## Metric\n\n    metric = mean over instances of  N(instance) / record(instance)\n\nThe eval runs an exact maximum-clique search (bitset branch and bound with a greedy-colouring bound)\non the graph for `K_k` and on its complement for an independent `l`-set; a hit fails the run\n(`wrong_answer`, naming the vertices). Loops, non-integer vertices and empty edge lists fail the run.\nA graph with more than `record + 5` vertices is refused rather than checked. Duplicate edges are\nharmless. Anything above 1.0 on an instance is a new lower bound for that `R(k, l)` and is flagged in\n`records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is\nfixed.\n\n## Records\n\n`record` is the best-known lower bound minus one, i.e. the order of the largest published\n`(k, l)`-graph. Bounds and reference keys follow S. P. Radziszowski, \"Small Ramsey Numbers\", EJC\nDynamic Survey DS1, revision 18 (April 2026), Tables Ia/Ib. None is known to be optimal, although\nMcKay–Radziszowski (1997) give strong evidence that `R(5, 5) = 43`. Witnesses marked \"verified\" were\ndownloaded and passed this pack's checker.\n\n| label | record | witness | DS1 key | verified |\n|---|---|---|---|---|\n| `3-10` | 39  | G. Exoo, \"On two classical Ramsey numbers of the form R(3, n)\", SIAM J. Discrete Math. 2 (1989) | Ex5 | yes (cs.indstate.edu/ge/RAMSEY) |\n| `3-11` | 46  | G. Exoo, \"On some small classical Ramsey numbers\", EJC 20(1) (2013) P68 | Ex20 | yes (same site) |\n| `3-12` | 52  | M. Kolodyazhny (2015), Tyumen | Kol1 | no (graph not retrievable) |\n| `3-13` | 60  | A. Nagda, P. Raghavan, A. Thakurta, \"Reinforced generation of combinatorial structures: Ramsey numbers\", arXiv:2603.09172 (2026), AlphaEvolve; matrix on GitHub | NaRT | yes |\n| `4-6`  | 35  | G. Exoo, \"On the Ramsey number R(4, 6)\", EJC 19(1) (2012) P66; 37 graphs at McKay's site | Ex19 | yes (r46_35some.g6) |\n| `4-7`  | 48  | G. Exoo, \"Applying optimization algorithms to Ramsey problems\" (1989) | Ex3 | yes (Exoo's site) |\n| `4-8`  | 58  | G. Exoo, personal communication 2005–06 recorded in DS1 | Ex16 | no (not on Exoo's site) |\n| `5-5`  | 42  | G. Exoo, \"A lower bound for R(5, 5)\", J. Graph Theory 13 (1989); 328 graphs at McKay's site | Ex4 | yes (r55_42some.g6) |\n| `5-6`  | 58  | G. Exoo, \"A lower bound for R(5, 6)\", manuscript (2023) | Ex25 | yes (Exoo's site) |\n| `6-6`  | 101 | J. G. Kalbfleisch (1966): the Paley graph of order 101 | Ka2 | yes (constructed) |\n\nUpper bounds: Angeltveit 2025 (`R(3,10) ≤ 41`), Goedgebeur–Radziszowski 2013 (`R(3, k)`),\nAngeltveit–McKay 2019–2026 (`k ≥ 4`, including `R(5,5) ≤ 46`).\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=3-10,5-5` restricts the eval to a subset of labels (default: all ten).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=3` shrinks the per-instance budget (default 9; the full eval takes\n  about 90 s).\n- `ZT_EVAL_SEED` only changes the `seed` handed to your solver.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Circulants (the baseline): `u ~ v` iff `(u − v) mod N` is in a symmetric distance set. Harborth and\n  Krause (2003) searched every circulant on fewer than 102 vertices, so no record here can be\n  beaten by a plain circulant except possibly `3-13`; but circulants at `N − 1` or `N − 2` are the\n  standard starting point, and `6-6` is the Paley graph `P(101)` itself.\n- Block-circulant and Cayley colourings (Exoo–Tatarevic 2015): vertices `Z_m × {0..b-1}`, edges\n  depend on the block pair and the difference; a few hundred bits describe a 100-vertex graph.\n- Exoo's method: simulated annealing / tabu on the edge set with cost = number of `K_k` plus number\n  of independent `l`-sets, counting only the subgraphs through the flipped edge (bitset\n  intersections make that cheap), plus restarts from the best graph with one vertex deleted and a\n  fresh one added.\n- Vertex extension: take a verified `(k, l)`-graph on `N` vertices (an `N − 1` circulant is easy to\n  find) and search for the neighbourhood of a new vertex — it must be `K_{k-1}`-free and its\n  complement must miss independent `(l−1)`-sets; this is a hitting-set problem over the maximal\n  cliques and independent sets of the base graph, exactly the shape of the 2026 `R(3,13)` search.\n- Use the eval's clique routine as your inner check; on 60 vertices it runs in milliseconds, so\n  thousands of candidates per second are realistic.\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 ramsey-lower. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to graph()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per instance (default 9)\n  ZT_EVAL_INSTANCES              comma-separated \"k-l\" labels (default: all ten)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"9\"))\nINSTANCES = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"3-10,3-11,3-12,3-13,4-6,4-7,4-8,5-5,5-6,6-6\").split(\",\") if s.strip()]\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# \"k-l\" -> N, the largest known graph with no K_k and no independent set of size l (so R(k, l) > N);\n# that is, the best-known lower bound on R(k, l) minus one. Sources in program.md (Radziszowski's\n# dynamic survey DS1.18, April 2026); none of these is proven optimal.\nRECORDS = {\n    \"3-10\": 39, \"3-11\": 46, \"3-12\": 52, \"3-13\": 60,\n    \"4-6\": 35, \"4-7\": 48, \"4-8\": 58,\n    \"5-5\": 42, \"5-6\": 58,\n    \"6-6\": 101,\n}\nSLACK = 5  # vertices allowed beyond the record; larger graphs are refused rather than checked\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 pack.py: {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(label: str, out, cap: int) -> tuple[int, list[int]]:\n    \"\"\"Returns (n, adjacency bitmasks). n = 1 + largest vertex index used.\"\"\"\n    if not isinstance(out, (list, tuple)):\n        fail(f\"graph({label}) must return a list of edges (a, b), got {type(out).__name__}\", \"wrong_answer\")\n    if len(out) == 0:\n        fail(f\"graph({label}) returned no edges; the order of the graph is read off the largest vertex index\", \"wrong_answer\")\n    adj = [0] * cap\n    n = 0\n    for e in out:\n        try:\n            a, b = e\n        except Exception:\n            fail(f\"graph({label}) returned a non-edge {e!r}\", \"wrong_answer\")\n        if type(a) is not int or type(b) is not int or a < 0 or b < 0:\n            fail(f\"graph({label}) returned a non-edge {e!r} (need pairs of non-negative ints)\", \"wrong_answer\")\n        if a == b:\n            fail(f\"graph({label}) returned a loop ({a}, {b})\", \"wrong_answer\")\n        if a >= cap or b >= cap:\n            fail(f\"graph({label}) uses vertex {max(a, b)}; refused, more than record + {SLACK} vertices\", \"wrong_answer\")\n        adj[a] |= 1 << b\n        adj[b] |= 1 << a\n        n = max(n, a + 1, b + 1)\n    return n, adj[:n]\n\n\ndef find_clique(adj: list[int], n: int, size: int):\n    \"\"\"Exact search for a clique of `size` vertices (bitset branch and bound with a greedy colouring bound).\n    Returns the clique as a list of vertices, or None.\"\"\"\n    if size <= 1:\n        return [0] if size == 1 and n else []\n\n    def bound(cand: int, need: int) -> bool:\n        colours = 0\n        while cand and colours < need:\n            colours += 1\n            q = cand\n            while q:\n                v = (q & -q).bit_length() - 1\n                cand &= ~(1 << v)\n                q &= ~adj[v] & ~(1 << v)\n        return colours >= need\n\n    def rec(cand: int, need: int, chosen: list[int]):\n        if need == 0:\n            return chosen\n        if cand.bit_count() < need or not bound(cand, need):\n            return None\n        while cand:\n            v = cand.bit_length() - 1\n            cand &= ~(1 << v)\n            if cand.bit_count() + 1 < need:\n                return None\n            got = rec(cand & adj[v], need - 1, chosen + [v])\n            if got is not None:\n                return got\n        return None\n\n    return rec((1 << n) - 1, size, [])\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"graph.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import graph as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import graph.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"graph\"):\n        fail(\"graph.py must define graph(k, l, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"ramsey|{SEED}\").getrandbits(32)\n    per, beaten = {}, []\n    for label in INSTANCES:\n        if label not in RECORDS:\n            fail(f\"no record for instance {label!r} (known: {sorted(RECORDS)})\", \"error\")\n        k, l = (int(x) for x in label.split(\"-\"))\n        record = RECORDS[label]\n        t0 = time.perf_counter()\n        try:\n            out = cand.graph(k, l, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"graph({label}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"graph({label}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        n, adj = validate(label, out, record + SLACK)\n        clique = find_clique(adj, n, k)\n        if clique is not None:\n            fail(f\"graph({label}): vertices {sorted(clique)} form a K_{k}\", \"wrong_answer\")\n        full = (1 << n) - 1\n        co = [(full & ~adj[v]) & ~(1 << v) for v in range(n)]\n        indep = find_clique(co, n, l)\n        if indep is not None:\n            fail(f\"graph({label}): vertices {sorted(indep)} are an independent set of size {l}\", \"wrong_answer\")\n        edges = sum(a.bit_count() for a in adj) // 2\n        per[label] = {\"k\": k, \"l\": l, \"N\": n, \"edges\": edges, \"record\": record, \"ratio\": round(n / record, 6),\n                      \"seconds\": round(elapsed, 2)}\n        if n > record:\n            beaten.append(label)\n    metric = sum(v[\"ratio\"] for v in per.values()) / len(per)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"graph.py":"\"\"\"Baseline: Paley graphs and random maximal K_k-free circulants, order raised while the budget lasts. Beat it.\n\nA circulant on Z_n with distance set D (d in D iff n-d in D) joins u, v iff (u - v) mod n is in D. Adding\ndistances never removes a clique, so distances are added in random order while the graph stays K_k-free;\nthe maximal graph that results is kept if its independence number is below l. Orders are tried upward\nfrom k + l - 1 and the largest valid graph found is returned; K_{k-1} is the fallback.\n\"\"\"\n\nimport random\nimport time\n\n\ndef _find_clique(adj, n, size):\n    if size <= 1:\n        return size == 1 and n > 0\n\n    def bound(cand, need):\n        colours = 0\n        while cand and colours < need:\n            colours += 1\n            q = cand\n            while q:\n                v = (q & -q).bit_length() - 1\n                cand &= ~(1 << v)\n                q &= ~adj[v] & ~(1 << v)\n        return colours >= need\n\n    def rec(cand, need):\n        if need == 0:\n            return True\n        if cand.bit_count() < need or not bound(cand, need):\n            return False\n        while cand:\n            v = cand.bit_length() - 1\n            cand &= ~(1 << v)\n            if cand.bit_count() + 1 < need:\n                return False\n            if rec(cand & adj[v], need - 1):\n                return True\n        return False\n\n    return rec((1 << n) - 1, size)\n\n\ndef _circulant(n, dist):\n    adj = [0] * n\n    for v in range(n):\n        for d in dist:\n            adj[v] |= 1 << ((v + d) % n)\n    return adj\n\n\ndef _valid(adj, n, k, l):\n    if _find_clique(adj, n, k):\n        return False\n    full = (1 << n) - 1\n    co = [(full & ~adj[v]) & ~(1 << v) for v in range(n)]\n    return not _find_clique(co, n, l)\n\n\ndef _edges(adj, n):\n    return [(u, v) for u in range(n) for v in range(u + 1, n) if adj[u] >> v & 1]\n\n\ndef graph(k: int, l: int, time_budget: float, seed: int) -> list[tuple[int, int]]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + 0.85 * time_budget\n    best_n, best = k - 1, [(u, v) for u in range(k - 1) for v in range(u + 1, k - 1)]\n\n    # Paley graphs: p = 1 mod 4 prime, u ~ v iff u - v is a non-zero square. Self-complementary, so they\n    # only matter for k = l, but they are cheap to test.\n    for p in (5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101):\n        if p <= best_n or time.perf_counter() > deadline:\n            continue\n        sq = {x * x % p for x in range(1, p)}\n        adj = _circulant(p, sorted(sq))\n        if _valid(adj, p, k, l):\n            best_n, best = p, _edges(adj, p)\n\n    # orders climb from the best so far; after six orders without a hit, start again just above the best\n    n = max(best_n + 1, k + l - 1)\n    misses = 0\n    while time.perf_counter() < deadline:\n        found = False\n        for _ in range(20):\n            if time.perf_counter() > deadline:\n                break\n            adj = [0] * n\n            order = list(range(1, n // 2 + 1))\n            rng.shuffle(order)\n            for d in order:\n                trial = list(adj)\n                for v in range(n):\n                    trial[v] |= (1 << ((v + d) % n)) | (1 << ((v - d) % n))\n                if not _find_clique(trial, n, k):\n                    adj = trial\n            if _valid(adj, n, k, l):\n                found = True\n                if n > best_n:\n                    best_n, best = n, _edges(adj, n)\n                break\n        misses = 0 if found else misses + 1\n        n += 1\n        if misses >= 6:\n            n, misses = best_n + 1, 0\n    return best\n"}}