Math Problem Cracked After 90 Years

Mathematicians solved a 'Ramsey' graph problem that's baffled many for decades
 By Gina Carey,  Newser Staff Posted Nov 4, 2023 7:45 AM CDT

Unless you dabble in advanced math, r(4,t) probably doesn't mean much to you. But to the delight of mathematicians across the globe, researchers cracked this "Ramsey problem," which has baffled great minds for decades. Phys.org reports that the findings of University of California San Diego researchers Jacques Verstraete and Sam Mattheus are being reviewed by Annals of Mathematics (though a preprint is available). "It really did take us years to solve," Verstraete said. "And there were many times where we were stuck and wondered if we'd be able to solve it at all. But one should never give up, no matter how long it takes." So what's been discovered after more than 90 years of head-scratching? Hold on to your abacus—we're about to talk math.

Ramsey theory (named after British mathematician Frank Ramsey, per New Atlas) has to do with graphs—which, as we learned in grade school, organize and visualize data. Generally speaking, the theory says that "in any large enough structure, there exists a relative large uniform substructure"—so if a graph is sizable, according to Ramsey theory, order can be found in that data. Ramsey problems—set up as r(s,t)—look at the sets of points on the graph that have lines between them connected (s), or have no lines connecting them (t). A well-known Ramsey problem that's been solved is r(3,3)=6, also known as "the theorem on friends and strangers." It posits that "amongst any six people, there will be at least three people who all know each other, or at least three people who all do not know each other."

"It's a fact of nature, an absolute truth," Verstraete said. "It doesn't matter what the situation is or which six people you pick—you will find three people who all know each other or three people who all don't know each other. You may be able to find more, but you are guaranteed that there will be at least three in one clique or the other." After this discovery, the gauntlet was thrown to solve r(4,4), r(5,5), and r(4,t)—where "t," representing the numbers of unconnected points, is variable. The answer to r(4,4) was discovered in the 1930s (it's 18), and r(5,5) still hasn't been solved. But this new research has rung the bell on the elusive r(4,t) problem.

story continues below

Verstraete had previously solved r(3,t) along with another collaborator in 2019 using a pseudorandom graph. He pushed forward this time by incorporating finite geometry, algebra, and probability, eventually finding that r(4,t) is close to a cubic function of "t." "If you find that the problem is hard and you're stuck, that means it's a good problem," Verstraete said. "[Mathematician] Fan Chung said a good problem fights back. You can't expect it just to reveal itself." Live Science notes that this March, researchers made a big breakthrough in determining what the upper bounds of a Ramsey problem can be—narrowing down the possibilities greatly. (Meanwhile, both math and reading scores are down in US schools).

Get the news faster.
Tap to install our app.
X
Install the Newser News app
in two easy steps: