![]() ![]() How do we find not the exact answer, but the best estimates for what these Ramsey numbers might be?" "This is what Sam and I have achieved in our recent work. "Because these numbers are so notoriously difficult to find, mathematicians look for estimations," Verstraete explained. If you started with 45 points, there would be more than 10 234 graphs to consider. Let's say you knew the solution to r(5,5) was somewhere between 40–50. ![]() Why is something so simple to state so hard to solve? It turns out to be more complicated than it appears. The solution to r(4,4) is 18 and is proved using a theorem created by Paul Erdös and George Szekeres in the 1930s. What happened after mathematicians found that r(3,3) = 6? Naturally, they wanted to know r(4,4), r(5,5), and r(4,t) where the number of points that are not connected is variable. You may be able to find more, but you are guaranteed that there will be at least three in one clique or the other." "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. "It's a fact of nature, an absolute truth," Verstraete states. To those of us who don't deal in graph theory, the most well-known Ramsey problem, r(3,3), is sometimes called "the theorem on friends and strangers" and is explained by way of a party: in a group of six people, you will find at least three people who all know each other or three people who all don't know each other. This is written as r(s,t) where s are the points with lines and t are the points without lines. Ramsey theory suggests that if the graph is large enough, you're guaranteed to find some kind of order within it-either a set of points with no lines between them or a set of points with all possible lines between them (these sets are called "cliques"). In mathematical parlance, a graph is a series of points and the lines in between those points. Now, University of California San Diego researchers Jacques Verstraete and Sam Mattheus have found the answer to r(4,t), a longstanding Ramsey problem that has perplexed the math world for decades. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |