LLM-generated search heuristics run through the CPro1 protocol with the reasoning model o3-mini-high produced verified constructions resolving open instances in 7 Handbook design families and newer problems.
On the clique covering numbers of Johnson graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We initiate a study of the vertex clique covering numbers of Johnson graphs $J(N, k)$, the smallest numbers of cliques necessary to cover the vertices of those graphs. We prove identities for the values of these numbers when $k \leq 3$, and $k \geq N - 3$, and using computational methods, we provide explicit values for a range of small graphs. By drawing on connections to coding theory and combinatorial design theory, we prove various bounds on the clique covering numbers for general Johnson graphs, and we show how constant-weight lexicodes can be utilized to create optimal covers of $J(2k, k)$ when $k$ is a small power of two.
citation-role summary
background 1
citation-polarity summary
fields
cs.AI 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems
LLM-generated search heuristics run through the CPro1 protocol with the reasoning model o3-mini-high produced verified constructions resolving open instances in 7 Handbook design families and newer problems.