All articles tagged with #combinatorics
A 55-year-old conjecture by mathematician Ronald Graham regarding the rearrangement of integers in modular arithmetic has been solved. A collaborative effort by young researchers used probabilistic methods and Fourier analysis to prove that valid orderings always exist, closing a long-standing gap in combinatorics.
Researchers completed the long-standing 'sandwich' conjecture by showing how to generate a binomial random graph and a regular graph in tandem so that each contains the other; by constructing the two graphs edge-by-edge (and then reversing the process), they derive a meta-theorem letting properties proven for the easier binomial model automatically apply to the harder regular model, streamlining many results in network theory and opening the door to more layered graph constructions.
Mathematicians explore maximizing the number of pieces from slicing an infinitely large pancake with a straight knife, reworking the classic Lazy Caterer’s puzzle in an infinite-plane setting.
DeepMind's AI system, FunSearch, has demonstrated its ability to generate new solutions to mathematical problems in the field of combinatorics, surpassing what was previously known by mathematicians and computer scientists. FunSearch utilizes large language models to create short computer programs that can generate solutions to specific mathematical problems. The system then checks the generated solutions against known ones, providing feedback to improve future iterations. The AI system was able to improve on the lower bound for a specific problem in combinatorics, showcasing the potential for human-machine collaboration in mathematics.
Mathematicians have solved a problem that has resisted progress for more than 40 years, involving so-called Ramsey numbers, which measure the size that collections of vertices and edges, called graphs, can attain before they inevitably give rise to pattern and structure. The new proof not only solves a problem that has resisted progress for more than 40 years, but also presents a novel road map for how mathematicians might tackle Ramsey problems going forward. The work heralds a shift in how mathematicians think about Ramsey problems, using pseudorandom constructions instead of randomness.