Applications of structural matroid theory to minor-closed classes of codes

点击翻译按钮获取中文摘要

Coding theory is the study of methods of sending information in a way that is tolerant of transmission errors. Its varied applications in the modern world range from reading data from a scratched disc, to broadcasting messages between planets. Different transmission methods, or codes, are required for different uses; one important type is a binary linear code, in which each message is interpreted as strings of zeroes and ones, and is encoded into a longer zero-one string (or codeword) with a special form. Two desirable properties of a code, difficult to maximize simultaneously, are its rate, a measure of how efficiently it transmits information, and its minimum distance, a measure of its tolerance to errors. I propose to use deep new ideas in an area of mathematics known as matroid theory to study theoretical limits on how well a code or class of codes can perform in this sense, as well as how rapidly codes can be decoded by computers. A matroid is an abstract mathematical object that can be thought of as a configuration of points in multidimensional geometric space. A special type of matroid is a binary matroid, which corresponds to a binary linear code. Two subclasses of the binary matroids are the graphic and cographic matroids, which are matroids whose structure arises from a network of nodes and edges; all three of these mentioned classes have the desirable property of being minor-closed. A rich theory has developed that describes the structure of minor­ closed classes of binary matroids, and consequently of binary codes. In particular, though nearly all binary codes are neither graphic nor cographic, a recent seminal result of Geelen, Gerards and Whittle shows that in every minor-closed subclass of binary codes, almost all the members are 'close' to being graphic or cographic. This latter result has huge implications in coding theory; roughly, any property that is known to be true for the graphic/cographic codes should apply more widely to minor-closed classes. One such property is the maximum-likelihood decoding threshold, a measure of exactly what error rate a code can tolerate while still performing effectively. With S. van Zwam, I recently determined this threshold for the graphic codes, and propose to extend it to all minor-closed classes of binary linear codes. Another property concerns the algorithmic problem of decoding codewords; for graphic/cographic codes it is known that decoding can be performed efficiently by a computer, but for binary codes it is known that decoding is 'NP-hard'; I propose to use matroid structure theory to understand precisely what the theoretical barrier is to efficient decoding that creates this divide. This research should have a significant contribution on our understanding of the theoretical capability and limits of information transmission, and will also strengthen the mostly untapped link between the fields of coding theory and structural matroid theory.