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

编码理论是研究以一种容忍传输错误的方式发送信息的方法。它在现代世界中的各种应用范围从从刻录的光盘上读取数据，到在行星之间广播信息。不同的用途需要不同的传输方法或代码；一种重要的类型是二进制线性码，其中每个消息被解释为0和1的字符串，并被编码为具有特殊形式的更长的0-1字符串(或码字)。码的两个理想属性很难同时最大化，这两个属性是码率和最小距离，前者是衡量其传输信息的效率，后者是衡量其对错误的容忍度。我建议使用一个被称为拟阵理论的数学领域的深刻新想法来研究一种代码或一类代码在这一意义上可以执行得多好的理论限制，以及计算机解码代码的速度。 拟阵是一种抽象的数学对象，可以被认为是多维几何空间中的点的配置。一种特殊类型的拟阵是二进制拟阵，它对应于二进制线性码。二元拟阵的两个子类是图形拟阵和余图拟阵，它们是由结点和边的网络构成的拟阵；所有这三个类都具有次闭的理想性质。一个丰富的理论已经发展起来，它描述了二元拟阵的次闭类的结构，从而描述了二进制码的结构。具体地说，尽管几乎所有的二进制代码既不是图形也不是图形，但Geelen，Gerards和Whitter最近的一项开创性结果表明，在二进制代码的每个次要封闭的子类中，几乎所有的成员都接近图形或图形。 后一个结果在编码理论中有巨大的影响；粗略地说，任何已知对图形/密码码成立的性质都应该更广泛地应用于次要闭合类。其中一个这样的属性是最大似然译码阈值，这是一种衡量代码在仍然有效执行的情况下可以容忍的误码率的确切指标。最近，我和S.van Zwam一起为图形码确定了这个阈值，并建议将其扩展到所有次闭类的二元线性码。另一个性质涉及解码码字的算法问题；对于图形/码形码，已知解码可由计算机有效地执行，但对于二进制码，已知解码是‘NP-难的’；我建议使用拟阵结构理论来准确地理解造成这种分割的有效解码的理论障碍是什么。 这项研究将对我们理解信息传输的理论能力和限度做出重大贡献，也将加强编码理论和结构拟阵理论之间最未开发的联系。

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.