Gasarch, Glenn and Kruskal also tried several other strategies. One promising idea leaned on randomness. A simple way to come up with a progression-free set is to put 1 in your set, then always add the next number that doesn’t create an arithmetic progression. Follow this procedure until you hit the number 10, and you’ll get the set {1, 2, 4, 5, 10}. But it turns out this isn’t the best strategy in general. “What if we don’t start at 1?” Gasarch said. “If you start at a random place, you actually do better.” Researchers have no idea why randomness is so useful, he added.
Calculating the finite versions of the two other new Ramsey theory results is even more vexing than determining the size of progression-free sets. Those results concern mathematical networks (called graphs) made up of nodes connected by lines called edges. The Ramsey number r(s, t) is the smallest number of nodes a graph must have before it becomes impossible to avoid including either a group of s connected nodes or t disconnected ones. The Ramsey number is such a headache to compute that even r(5, 5) is unknown — it’s somewhere between 43 and 48.
In 1981, Brendan McKay, now a computer scientist at Australian National University, wrote a software program called nauty, which was intended to make calculating Ramsey numbers simpler. Nauty ensures that researchers don’t waste time checking two graphs that are just flipped or rotated versions of one another. “If somebody’s in the area and is not using nauty, the game is over. You must use it,” said Stanisław Radziszowski, a mathematician at the Rochester Institute of Technology. Still, the amount of computation involved is almost incomprehensible. In 2013, Radziszowski and Jan Goedgebeur proved that r(3, 10) is at most 42. “It took, I think, almost 50 CPU years,” said Goedgebeur, a computer scientist at KU Leuven University in Belgium.
If you can’t compute an exact Ramsey number, you can try narrowing down its value with examples. If you found a 45-node graph without five nodes that were all connected and without five nodes that were all disconnected, that would prove that r(5, 5) is bigger than 45. Mathematicians studying Ramsey numbers used to think that finding those examples, called Ramsey graphs, would be simple, Radziszowski said. But it wasn’t so. “There was this expectation that nice, cool mathematical constructions will give the best possible constructions, and we just need more people to work on it,” he said. “My feeling is more and more that it’s chaotic.”
Randomness is both an obstacle to understanding and a useful tool. Geoffrey Exoo, a computer scientist at Indiana State University, has spent years refining random methods to generate Ramsey graphs. In a 2015 paper announcing dozens of new, record-beating Ramsey graphs, Exoo and Milos Tatarevic generated random graphs and then gradually tweaked them by deleting or adding edges that reduced the number of unwanted clusters until they found a Ramsey graph. Exoo’s techniques are as much an art as anything, though, Radziszowski said. They sometimes require him to combine multiple methods, or to use judgment about what kind of graphs to start with. “Many, many people try it, and they cannot do it,” Radziszowski said.
The techniques developed to generate Ramsey graphs could be more broadly useful someday, said Goedgebeur, who has worked on producing other kinds of graphs, such as graphs that represent chemical compounds. “It is not unlikely that these techniques can also be transferred and adjusted to help generate other classes of graphs more efficiently (and vice versa),” he wrote in an email.
To Radziszowski, however, the reason for studying the small Ramsey numbers is much simpler. “Because it’s open, because nobody knows what the answer is,” he said. “The trivial cases we do by hand; a little larger, you need a computer, and a little larger, even the computer is not good enough. And so the challenge emerges.”
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/mathematical-tricks-for-taming-the-middle-distance-20230707/
