On cover-free families of finite vector spaces

Abstract

There is a large literature on cover-free families of finite sets, because of their many applications in combinatorial group testing, cryptographic and communications. This work studies the generalization of cover-free families from sets to finite vector spaces. Let $V$ be an $n$-dimensional vector space over the finite field ${\mathbb{F}}_q$ and let ${\left[\genfrac{}{}{0ex}{}{V}{k}\right]}_q$ denote the family of all $k$-dimensional subspaces of $V$. A family $\mathcal{F}\subseteq {\left[\genfrac{}{}{0ex}{}{V}{k}\right]}_q$ is called cover-free if there are no three distinct subspaces $F_0,F_1,F_2\in \mathcal{F}$ such that $F_0\le (F_0\cap F_1)+(F_0\cap F_2)$. A family $\mathcal{H}\subseteq {\left[\genfrac{}{}{0ex}{}{V}{k}\right]}_q$ is called a $q$-Steiner system $S_q(t,k,n)$ if for every $T\in {\left[\genfrac{}{}{0ex}{}{V}{t}\right]}_q$, there is exactly one $H\in \mathcal{H}$ such that $T\le H$. In this paper we investigate cover-free families in the vector space $V$. Firstly, we determine the maximum size of a cover-free family in ${\left[\genfrac{}{}{0ex}{}{V}{k}\right]}_q$. Secondly, we characterize the structures of all maximum cover-free families which are closely related to $q$-Steiner systems.

25 pages