Quadratically Dense Matroids

Auburn University, Auburn AL

Investigators

Abstract

Matroids are objects that axiomatize the notions of independence and dependence. Because of their generality, matroids have found applications in a wide variety of areas including optimization, network theory, and cryptography. This project seeks to prove new upper bounds on how many elements a given matroid can have as a function of its rank, and show that in many important special cases the upper bounds are attained by matroids that arise from networks with labeled edges. Graduate students will be trained and mentored as part of this project. More specifically, this project will focus on minor-closed classes of matroids for which the densest matroids have a quadratic number of elements as a function of rank, such as the class of binary matroids without a fixed projective geometry minor and the class of real-representable matroids without a fixed rank-2 uniform minor. The first part of this project seeks to refine the celebrated matroid Growth Rate Theorem by showing that the maximum density of a matroid in a class of this type is always determined by a finite group associated with the class. This will require new constructions for matroids from graphs with edges labeled by a finite group, and the second part of this project will explore applications of these new constructions in optimization, structural rigidity theory, and network flow theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.