Mathematics: Erdös conjecture cracked

Solved after 50 years: Mathematicians have proved one of the famous Erdös conjectures – the existence of so-called Steiner triple systems with a large waist . It states that, for example, seven people can form seven trios without the same pair being found in more than one triple. By applying methods from probability theory, the researchers were able to prove this conjecture for the first time.

The Hungarian mathematician Paul Erdös is considered one of the most important mathematicians of 20. century. He presented numerous theorems and conjectures in number theory and combinatorics, including some dealing with the geometric order of graphs. Some of these combinatorial designs are not only relevant for abstract contexts, but also quite practical for the development of experiments and computer code.

Trios without duplicate pairs wanted

One of these Erdös conjectures deals with so-called Steinerian triple systems – the number of possible triple combinations under certain restrictions. An example: Suppose seven people want to form groups of three. Each person can be part of several triples, but each pair of persons can only be part of exactly one group of three. If this condition is fulfilled with a high number of triples and few people, one speaks of a high waist size.

Erös postulated that such triple systems are possible, but a proof for triple systems with more than six people have been outstanding so far. “Problems of this type are in general immensely difficult to prove and it seems almost beyond our reach to precisely characterize the number of triples that exist for a given configuration,” explains Matthew Kwan from the Institute of Science and Technology Austria (ISTA). and his colleagues.

Combination of mathematical methods

But this is exactly what the mathematician team is after succeded. In their work, Kwan and his colleagues proved the existence of Steiner triple systems with arbitrarily high waist sizes. “To prove their existence, you have to avoid algebra and introduce methods from probability theory, probabilistics,” explains Kwan. “We succeeded.”

For this they used a wide range of mathematical methods, which are mainly based on probabilistic combinatorics. “In addition, we used two new methods: retrospective analysis, which allows us to track randomness in earlier steps, and sparsification, a type of thinning that eliminates all the challenges of retrospective analysis,” explains Kwan.

Conjecture proven

This allowed the team to to crack the Erdös conjecture set up years ago. “Among other things, we can prove where the lower limit for the number of r-sparse Steiner triple systems lies for a given set of vertices,” they explain. In this way, the mathematicians showed, among other things, that with seven vertices, exactly seven triples are possible without double pairings.

As Kwan explains, this breakthrough was only achieved through the comprehensive application of techniques from different sub-areas of mathematics. “My philosophy: I try to work on different things,” says the mathematician. “It may be tempting to focus entirely on one area, but if you spend a lifetime tinkering with different problems, you will find those techniques that help you discover new things in other areas.” (Preprint arXiv: 2201.04554v3)

Source: Institute of Science and Technology Austria

. March 2022

– Nadja Podbregar

Back to top button