Search

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[V\atop k\right]_q$ denote the family of all $k$-dimensional subspaces of $V$. A family $\mathcal{F}\subseteq \left[V\atop 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}\leq (F_{0}\cap F_{1})+(F_{0}\cap F_{2})$. A family $\mathcal{H}\subseteq \left[V\atop k\right]_q$ is called a $q$-Steiner system $S_{q}(t, k, n)$ if for every $T\in \left[V\atop t\right]_q$, there is exactly one $H\in \mathcal{H}$ such that $T\leq 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[V\atop k\right]_q$. Secondly, we characterize the structures of all maximum cover-free families which are closely related to $q$-Steiner systems., Comment: 25 pages

Let $V$ be an $n$-dimensional vector space over the finite field $\mathbb{F}_{q}$, and let $\mathcal{L}(V)=\bigcup_{0\leq k\leq n}\left[V\atop k\right]$ be the set of all subspaces of $V$. A family of subspaces $\mathcal{F}\subseteq \mathcal{L}(V)$ is $s$-union if dim$(F+F')\leq s$ holds for all $F$, $F'\in\mathcal{F}$. A family $\mathcal{F}\subseteq \mathcal{L}(V)$ is an antichain if $F\nleq F'$ holds for any two distinct $F, F'\in \mathcal{F}$. The optimal $s$-union families in $\mathcal{L}(V)$ have been determined by Frankl and Tokushige in $2013$. The upper bound of cardinalities of $s$-union $(s