Connectivity and Structure in Representable Matroids

Louisiana State University, Baton Rouge LA

Investigators

Abstract

When communicating a digital message, errors can occur in the transmission for a variety of reasons. To ensure the original message is received by the recipient, some overhead is added, resulting in a so-called error-correcting code. There is always a trade-off between the number of errors that can be corrected and the amount of overhead that gets added to the message. This project is concerned with the study of mathematical abstractions of these error-correcting codes. Through these abstractions, called matroids, More will be learned about the optimal tradeoff between error-correcting capacity and overhead. Part of the investigations will use the open-source software SageMath, and it is expected that improvements to that software will be contributed. Graduate student involvement in the research is anticipated. Not only error-correcting codes, but also constraints in an optimization problem, path systems in a graph, and many other mathematical structures can be modeled by geometric configurations of points, known as matroids. Matroid theory gives a unique perspective on these structures through the introduction of concepts like connectivity and minors, both of which generalize concepts from graph theory. A matroid representation is a collection of vectors capturing the same geometric information as the abstract matroid. Geelen, Gerards, and Whittle have developed a powerful theory regarding the structure of matroids representable over a finite field. The first goal of this project is to study consequences of their result in coding theory, extremal matroid theory, and matroid flow problems. The second goal is to give a characterization of the class of dyadic matroids in terms of minimal obstructions known as excluded minors. Dyadic matroids are representable over both the field with 3 and with 5 elements, and arise, for instance, in the study of bidirected networks. The third goal is to study alternative representations, in particular multilinear and skew-partial field representations, which are useful in the theory of secret sharing, and connectivity related matroids, which arise naturally from the study of matroid structure. Computational science is increasingly used in matroid theory research. Especially the second line of research outlined above will benefit from versatile, reliable software for matroid computation. Recently Pendavingh and Van Zwam developed such software, which is part of the open-source, freely available SageMath software system. A final goal of the project is to improve on this functionality.