From Cell-Specific Heuristics to Transferable Structural Search for Ramsey Graph Construction

One of the most stubborn questions in mathematics asks how large a party must be before you can guarantee that either r people all know one another or s people are all mutual strangers. That threshold is the Ramsey number R(r, s), and even R(5,5) remains unknown today (the best bounds place it somewhere between 43 and 46, with the upper bound due to Angeltveit and McKay in 2024; for a comprehensive and regularly maintained reference, see the Radziszowski dynamic survey, most recently updated in January 2026).

My new research paper, „From Cell-Specific Heuristics to Transferable Structural Search for Ramsey Graph Construction„, published today in the Mathematics journal as a Feature Paper in section E: Applied Mathematics, special issue „Advances in Graph Labelings and Ramsey Theory in Discrete Structures„, asks a different question: not what Ramsey numbers are, but how we search for them. The supplementary experiments document can be found here.

To prove a lower bound on a Ramsey number, you need to construct a witness graph, one that avoids both a large clique and a large independent set. Modern automated search methods can do this impressively well, but they are usually tuned to one Ramsey cell at a time. Each new cell effectively starts from scratch, with little reuse of the structural insight embedded in previous witnesses. That seems like a waste. Strong Ramsey witnesses are rarely random; they often display cyclic symmetry, repeated local motifs, and modular organization. It is implausible that this organization disappears when we move from R(4, 13) to R(4, 14); the more natural hypothesis is that some of it persists and can be extracted, compressed, and transferred to new cells.

Before I explain how the framework works, let me tell you the most surprising result, because it shapes everything else. As a diagnostic tool, I included a baseline I call the structure oracle, a method that explicitly favors candidate graphs that most closely resemble known witnesses, prioritizing motif overlap and cyclic-shift agreement above all else. I expected it to perform well. Instead, it performs substantially worse where it matters most: validity. Although it achieves high structural similarity, its exact forbidden-clique burden is more than twice that of the balanced portfolio method. This exposes a genuine structure–validity frontier. The set of graphs that look like known witnesses is not the same as the set of graphs that satisfy the Ramsey constraints. Structural resemblance alone is therefore a misleading evaluation target, and finding the balance between the two is a real, non-trivial challenge.

The framework is inspired by a recent result in scientific machine learning called Ψ-NN, which showed that a high-capacity neural network trained on physics problems could be distilled into a smaller student model that reveals the underlying equations governing the system, not as a black box, but as explicit, interpretable structure. The key methodological lesson is that problem-solving and structure discovery can be decoupled: let a powerful teacher solve the task first, then extract the reusable organization from what it learned.

Concretely, the framework starts from known strong Ramsey witnesses and describes each one structurally. Consider a witness for R(4, 13): it places edges at particular cyclic distances, say shifts 3, 7, and 12 are heavily used while others are nearly absent. That fingerprint (which shifts are active, how dense the graph is, which pairs of motifs tend to coexist) is the structural signature of that witness. Now do the same for witnesses from neighboring cells. Some motifs recur; others are cell-specific noise. The framework compresses these descriptions into a shared structural summary that captures what persists across a neighborhood of related cells, then uses that summary to guide the construction of candidate graphs for a new, unseen target cell. Those candidates are subsequently refined by local search and selected through a portfolio mechanism.

The portfolio mechanism turned out not to be a tuning detail but a substantive part of the method. Different target cells respond to different forms of transferred structure (edge-shift statistics, motif frequencies, density profiles, compatibility patterns) and no single distilled representation is consistently best across all cells. Keeping several structural hypotheses alive and competing, then selecting under a balanced objective that penalizes both forbidden cliques and structural deviation, is what gives the approach its robustness. I tested the framework across five target cells: R(3, 13), R(3, 18), R(4, 13), R(4, 14), and R(4, 15). The portfolio transfer method came out as the strongest balanced approach across the board, not through a single favorable case but consistently. Crucially, matched-compute experiments (where every method receives the same search budget) confirmed that the advantage is not an artifact of spending more iterations. The portfolio method still wins under equal compute, which is the cleanest evidence that the structural transfer is doing real work rather than simply buying extra search time. I should note that the search-side results are more nuanced: the portfolio-guided search is competitive and stable, but simpler baselines like structured-seed local search can match it under some conditions. The transfer conclusion is the robust one; the search conclusion is promising but more sensitive to initialization. One result I didn’t expect: under a minimal configuration where only a single teacher witness is available, the portfolio method achieved its strongest validity result across all experiments, with a mean exact clique count of just 95. One witness from one neighboring cell, no cell-specific tuning, and the portfolio mechanism still amplifies that sparse signal into near-valid candidates.

One additional component proved especially useful for the smaller cells. In the R(3,s) regime, exact triangle counts are still computationally feasible, so the framework can incorporate direct supervision, refining candidates by literally driving the triangle count to zero. This materially improves performance on those cells and suggests that transferable structural priors and exact local supervision are not competing paradigms but natural complements. Extensive robustness experiments (spanning eight random seeds, multiple compute budgets, varied teacher pools, and different structural resolutions) largely reinforce these findings. The structure–validity frontier, in particular, is highly stable: no matter how I perturbed the experimental settings, the oracle that best matches witness shape continued to underperform the balanced method on actual Ramsey validity.

The broader significance, I believe, goes beyond Ramsey theory. Extremal combinatorics is full of problems where human experts develop deep structural intuitions that get rediscovered, cell by cell, problem by problem, at great cost. If automated search could extract that knowledge, compress it, and transfer it, the whole enterprise changes character: search stops being pure optimization and starts being structure discovery.

This is very much a proof of concept, and there is a lot of room to grow. I am particularly excited about richer representations that capture automorphism groups and orbit structure more directly, and about the possibility of a portfolio mechanism that learns when each type of structural prior is likely to be useful: a kind of meta-transfer. Of course, the deepest question is what happens when you move to genuinely unknown cells, where no reference witness exists to compare against. I didn’t attempt that here because doing so would mean claiming new Ramsey lower bounds, which requires independent verification and is a fundamentally different standard of evidence than the proof-of-concept comparisons in this paper. But the framework was designed with that direction in mind, and getting there is what I most want to work on next.

The full code and experiments are available on my GitHub repository. Mathematics has always learned from itself, through human mathematicians carrying intuitions from one problem to the next. This paper is a small step toward letting automated search do the same.