Can we compare sets of points efficiently?

Princeton University, Princeton NJ

Investigators

Abstract

There is no known efficient algorithm to test whether two matrices have the same linear dependencies among their columns. One of the goals of this proposal is to construct a polynomial-time algorithm for this, provided the entries of the matrices are from a finite field. Techniques pioneered in the Matroid Minor Structure Theory by Geelen, Gerards, and Whittle are expected to be crucial components. A second problem is: given a fixed matrix, how many other matrices can have the same set of dependencies? Again, we wish to establish an algorithm to count (and construct) these matrices over a finite field. The proposed approach involves the notion of a stabilizer by Whittle, techniques from a paper by Pendavingh and Van Zwam, and a new notion of connectivity. A third line of research relates to excluded-minor characterizations of matroid classes (similar to Kuratowski's Theorem for planar graphs). We will focus especially on finding the excluded minors of subclasses of the quinary matroids. This third line will have a significant computational component. A collection of measurements, a stream of digital information, a set of constraints to an optimization problem: many things can be modeled mathematically by a set of points in some space. Often the absolute positions of these points are not important, but their positions relative to each other are. The mathematical notion of a matroid captures this information. However, sometimes too many point configurations map to the same abstract matroid, which is a major obstacle in the study of these point configurations. The main aim of this proposal is a better understanding of this phenomenon. Additionally, a part of this project is concerned with the development of reliable, versatile software for matroid computation, with the intent of integrating this with the open-source Sage Mathematics Software system. Computers can help with finding patterns and structure within a class of matroids, or with finding counterexamples to conjectures.