Ramsey numbers are a central topic in combinatorics. The number r(5,t) asks: how large does a graph need to be before it must contain either a clique of size 5 (five mutually connected vertices) or an independent set of size t (t vertices with no connections among them)? Finding lower bounds on r(5,t) means constructing large graphs that deliberately avoid both of these features. The challenge is that random constructions can show such graphs exist in principle, but explicit, efficiently constructible examples are much harder to find and tend to give weaker bounds.
The authors present two new explicit constructions that improve on the previous best constructive lower bound. The first takes a recent graph construction and refines it using a clever ordering of vertices, producing graphs that are provably free of 5-cliques and have small independent sets. This yields a lower bound showing r(5,t) grows at least as fast as t to the power 7/4. The second construction is more sophisticated: it uses a specific algebraic object called the Coulter-Matthews polynomial and carefully trims the resulting graph to remove unwanted structure. This gives a stronger bound, showing r(5,t) grows at least as fast as t to the power 20/11, and the construction can be carried out by a computer in polynomial time.
Both results surpass the previous best constructive bound of t to the power 5/3, which had stood for some time. The gap between constructive lower bounds and what probabilistic arguments suggest is possible remains open, but these results meaningfully narrow it. The work illustrates a broader theme in combinatorics: translating existence proofs into concrete, algorithmically efficient constructions is a deep and difficult problem, and progress often comes from combining algebraic structures with combinatorial refinements.