Classical Ramsey numbers, lower bounds by explicit graphs

# Classical Ramsey numbers: lower bounds by explicit graphs ## Goal The Ramsey number `R(k, l)` is the least `n` such that every graph on `n` vertices contains a clique of size `k` or an independent set of size `l`. A graph on `N` vertices with neither (a *`(k, l)`-graph*) proves `R(k, l) > N`. Only nine non-trivial values are known exactly (`R(3, 3..9)`, `R(4, 4) = 18`, `R(4, 5) = 25`); everything else is a pair of bounds, and every lower bound is an explicit graph, most of them found by Exoo's heuristic searches over the last four decades. `graph.py` exposes graph(k: int, l: int, time_budget: float, seed: int) -> list[tuple[int, int]] returning the edge list of a simple graph on vertices `0 .. N-1`, where `N` is one more than the largest vertex index that appears (so every vertex you want counted must touch an edge). `N` is what you are maximising. Instances are labelled `k-l`: | label | k | l | record N | known bounds on R(k, l) | |---|---|---|---|---| | `3-10` | 3 | 10 | 39 | 40 – 41 | | `3-11` | 3 | 11 | 46 | 47 – 50 | | `3-12` | 3 | 12 | 52 | 53 – 59 | | `3-13` | 3 | 13 | 60 | 61 – 68 | | `4-6` | 4 | 6 | 35 | 36 – 40 | | `4-7` | 4 | 7 | 48 | 49 – 58 | | `4-8` | 4 | 8 | 58 | 59 – 79 | | `5-5` | 5 | 5 | 42 | 43 – 46 | | `5-6` | 5 | 6 | 58 | 59 – 85 | | `6-6` | 6 | 6 | 101 | 102 – 160 | ## Metric metric = mean over instances of N(instance) / record(instance) The eval runs an exact maximum-clique search (bitset branch and bound with a greedy-colouring bound) on the graph for `K_k` and on its complement for an independent `l`-set; a hit fails the run (`wrong_answer`, naming the vertices). Loops, non-integer vertices and empty edge lists fail the run. A graph with more than `record + 5` vertices is refused rather than checked. Duplicate edges are harmless. Anything above 1.0 on an instance is a new lower bound for that `R(k, l)` and is flagged in `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed. ## Records `record` is the best-known lower bound minus one, i.e. the order of the largest published `(k, l)`-graph. Bounds and reference keys follow S. P. Radziszowski, "Small Ramsey Numbers", EJC Dynamic Survey DS1, revision 18 (April 2026), Tables Ia/Ib. None is known to be optimal, although McKay–Radziszowski (1997) give strong evidence that `R(5, 5) = 43`. Witnesses marked "verified" were downloaded and passed this pack's checker. | label | record | witness | DS1 key | verified | |---|---|---|---|---| | `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) | | `3-11` | 46 | G. Exoo, "On some small classical Ramsey numbers", EJC 20(1) (2013) P68 | Ex20 | yes (same site) | | `3-12` | 52 | M. Kolodyazhny (2015), Tyumen | Kol1 | no (graph not retrievable) | | `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 | | `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) | | `4-7` | 48 | G. Exoo, "Applying optimization algorithms to Ramsey problems" (1989) | Ex3 | yes (Exoo's site) | | `4-8` | 58 | G. Exoo, personal communication 2005–06 recorded in DS1 | Ex16 | no (not on Exoo's site) | | `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) | | `5-6` | 58 | G. Exoo, "A lower bound for R(5, 6)", manuscript (2023) | Ex25 | yes (Exoo's site) | | `6-6` | 101 | J. G. Kalbfleisch (1966): the Paley graph of order 101 | Ka2 | yes (constructed) | Upper bounds: Angeltveit 2025 (`R(3,10) ≤ 41`), Goedgebeur–Radziszowski 2013 (`R(3, k)`), Angeltveit–McKay 2019–2026 (`k ≥ 4`, including `R(5,5) ≤ 46`). ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating - `ZT_EVAL_INSTANCES=3-10,5-5` restricts the eval to a subset of labels (default: all ten). - `ZT_EVAL_PER_INSTANCE_SECONDS=3` shrinks the per-instance budget (default 9; the full eval takes about 90 s). - `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Ideas that are known to matter (check the journal before repeating one) - Circulants (the baseline): `u ~ v` iff `(u − v) mod N` is in a symmetric distance set. Harborth and Krause (2003) searched every circulant on fewer than 102 vertices, so no record here can be beaten by a plain circulant except possibly `3-13`; but circulants at `N − 1` or `N − 2` are the standard starting point, and `6-6` is the Paley graph `P(101)` itself. - Block-circulant and Cayley colourings (Exoo–Tatarevic 2015): vertices `Z_m × {0..b-1}`, edges depend on the block pair and the difference; a few hundred bits describe a 100-vertex graph. - Exoo's method: simulated annealing / tabu on the edge set with cost = number of `K_k` plus number of independent `l`-sets, counting only the subgraphs through the flipped edge (bitset intersections make that cheap), plus restarts from the best graph with one vertex deleted and a fresh one added. - Vertex extension: take a verified `(k, l)`-graph on `N` vertices (an `N − 1` circulant is easy to find) and search for the neighbourhood of a new vertex — it must be `K_{k-1}`-free and its complement must miss independent `(l−1)`-sets; this is a hitting-set problem over the maximal cliques and independent sets of the base graph, exactly the shape of the 2026 `R(3,13)` search. - Use the eval's clique routine as your inner check; on 60 vertices it runs in milliseconds, so thousands of candidates per second are realistic. 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.