Mathematical Connect-the-Dots Reveals How Structure Emerges
Imagine 100 dots scattered in front of you. In a haphazard variation on connect-the-dots, start drawing lines between the points. How many lines can you draw without producing a triangle? A square? An 11-pointed star?
These types of problems have a long history in mathematics. In a paper posted on April 26, Oliver Janzer and Benny Sudakov of the Swiss Federal Institute of Technology Zurich have answered a 47-year-old version of the question. They consider an arrangement of dots and lines, called a graph by mathematicians. The structure they’re looking for is a special type of graph called a regular graph. In a regular graph, each point (or “node”) has the same number of lines (or “edges”) connected to it. In a 2-regular graph, every node sits on precisely two edges; it has “degree 2.” In a 600-regular graph, each node has degree 600.
If you start again with your 100 dots and keep adding edges, a portion of the dots and edges will eventually form regular graphs. At some threshold, their presence becomes unavoidable, just as triangles inevitably emerge when you try to place five edges among four nodes. Janzer and Sudakov figured out what this threshold was, answering a problem first asked in 1975 by Paul Erdős and Norbert Sauer.
