AI Solves Ramsey-Style Hypergraph Problem, Improving Lower Bounds

A Ramsey-style hypergraph problem from FrontierMath has been solved using AI, marking a significant achievement in combinatorial mathematics. The problem, which deals with improving lower bounds on a sequence arising from simultaneous convergence of infinite series, was first solved by Kevin Barreto and Liam Price using GPT-5.4 Pro, with the solution subsequently confirmed by problem contributor Will Brian.

The problem centers on hypergraphs and partitions. A hypergraph contains a partition of size n if there exists a subset D of vertices and a partition P of edges such that |D| = n and every member of D is contained in exactly one member of P. The function H(n) represents the largest integer k such that there exists a hypergraph with k vertices, no isolated vertices, and no partitions of size greater than n.

Brian's assessment of the solution was notably positive: "This is an exciting solution to a problem I find very interesting. I had previously wondered if the AI's approach might be possible, but it seemed hard to work out. Now I see that it works out perfectly. It eliminates an inefficiency in our lower-bound construction and in some sense mirrors the intricacy of our upper-bound construction. The matching lower and upper bounds are quite good for Ramsey-theoretic problems, and I'm interested in further understanding why this works out so well."

Problem Structure and Solution Approach

The problem was presented in three escalating challenges:

Warm-up: Find a hypergraph with at least 64 vertices, no more than 20 edges, and no partitions of size greater than 20.

Single Challenge: Increase the difficulty to at least 66 vertices under the same constraints.

Full Problem: Develop a general algorithm for all n that improves the lower bound by a constant factor c > 1, demonstrating H(n) ≥ c * k_n where k_n follows the recursive formula k_1 = 1 and k_n = ⌊n/2⌋ + k_⌊n/2⌋ + k_⌊(n+1)/2⌋.

The AI's solution eliminated an inefficiency in the existing lower-bound construction while mirroring the intricacy of the upper-bound construction, achieving matching lower and upper bounds that Brian describes as "quite good for Ramsey-theoretic problems."

Multiple AI Successes

Following the initial solve, FrontierMath developed a general scaffold for testing models on Open Problems. Several other AI models successfully solved the hypergraph problem:

• Opus 4.6 (max)
• Gemini 3.1 Pro
• GPT-5.4 (xhigh)

This convergence of solutions across different AI architectures suggests the problem's solution space may have identifiable patterns that advanced language models can recognize and exploit.

Publication and Future Work

Brian plans to write up the solution for publication, potentially including follow-on work inspired by the AI's approach. Barreto and Price have been offered co-authorship on any resulting papers. The solution's notability is considered "moderately interesting" and would be published in a standard specialty journal.

Problem Assessment

According to Brian's survey, the problem presents a moderate challenge:

• Number of mathematicians highly familiar with the problem: approximately 10
• Number of mathematicians who made serious attempts: 5-10
• Estimated expert human solve time: 1-3 months
• Likelihood of generating more interesting mathematics: fairly likely
• Probability the problem is solvable as stated: 95-99%

Technical Implementation

The solution requires providing a Python script with a function solution(n: int) -> str that outputs the hypergraph as a string where vertices are labeled 1 through |V|, and edges are denoted with curly braces. For n ≤ 100, the algorithm must complete within 10 minutes on a typical laptop.

The successful resolution of this problem demonstrates AI's growing capability in tackling complex combinatorial mathematics, particularly in areas like Ramsey theory where finding constructive proofs has traditionally been challenging. The solution's ability to improve lower bounds by a constant factor represents meaningful progress in understanding hypergraph partitions and their properties.