Jeremy West

Basis Covers of Subspace Arrangements

Consider a finite collection of subspaces of a finite dimensional vector space. A basis cover is a collection of vectors containing a basis for each of the given subspaces. In this talk I will consider the following questions: What is the smallest size of a basis cover and is there an efficient algorithm for constructing a basis cover of minimum size? In general, determining the minimum size of a basis cover is an NP-complete problem. Interestingly, this problem is NP-complete even for easy problems, for instance, when all the subspaces are dimension two or less. However, I will consider several restrictions of the problem under which a naive approach yields a minimum basis cover in polynomial time. I will also discuss some of the motivations of the minimum basis cover problem by describing its relationship to the classification of Schur rings, counting sublattices, and several other classical graph problems.