Matroids

From Mathsreach

Jump to: navigation, search


Matroids are unusual because there are 40 different ways to define these abstract objects, and no one definition is preferred. Some mathematicians think of them as graphs (networks of nodes joined by lines), others as matrices.

Mayhew is one of only 50 or so pure mathematicians worldwide studying this topic, an
d he prefers to think of matroids geometrically. “For me, a matroid is like a configuration of points sitting in space. It’s projective geometry - if you project it onto a screen you get the same geometry, regardless of the angle of the screen. For example, points always sit on a common line or in the same plane. However, geometry is not always helpful; I can’t visualise 10 points sitting in five-dimensional space.”

Matroids were first explored in the 1930s, and underlie many different mathematical objects. A catalogue is useful for helping to find whether all matroids with property X also have property Y, or to find matroids with particular properties.

In 1969, with the help of an early computer, mathematicians catalogued the few thousand matroids with up to eight elements. Those researchers thought it “unlikely” that the complete set of matroids with nine elements would ever be compiled. However, it took only another 35 years before Mayhew and his Australian collaborator Gordon Royle created an online database of all 383,172. They, too, were pessimistic about a catalogue of those with up to ten elements, saying that about 200 years of computing time would be needed to find the estimated two and a half trillion matroids. “I assumed it would be impossible for years, but another mathematician with clever optimisations has made good progress on the 10-element matroids, using a network of 30 or 40 computers for weeks on end,” says Mayhew. However, he thinks “getting past 10 will be impossible for a long time”.

Each number system has a different family of matroids, and obstacles mean that certain matroids will never arise in a particular number system. With five collaborators, Mayhew is also trying to work out how many obstacles exist in the five number system of matroids. This, too, has been a slow process. In 1958, researchers proved that there is one obstacle in the two number system. It took 21 more years to prove the four obstacles in the three number system, and another 21 to prove the seven obstacles in the four number system. More elements means that the number of obstacles grows explosively: “We know that there are at least 564 obstacles, but we have no idea of the upper bound – it could be billions.”

Matroids have applications in computer science, says Mayhew. “Binary matroids are points in space identified by strings of zeros and ones, so by studying binary matroids you understand space as a computer sees it. Understanding that space is really important for making error-correcting technology for CDs and satellites. Your satellite sends a string of ones and zeroes but interference swaps those digits; on the receiving end you need to work out where those errors occurred and correct them. The algorithms for doing that, and for correcting CD scratches, depend on understanding binary space.”

Matroids are also useful for assessing the rigidity of joint and bar networks. “To decide if your joints are rigid or not, you have to look at a related matroid, and I think that’s delightful. But the applications aren’t the reason I study them – I think they’re beautiful and fun.”