Intersection theorems for systems of finite vector spaces

https://doi.org/10.1016/0012-365X(75)90091-6Get rights and content
Under an Elsevier user license
open archive

Abstract

A theorem of Erdös, Ko and Rado states that if S is an n-element set and F is a family of k-element subsets of S, k⩽ 12n, such that no two members of F are disjoint, then F… ⩽ (n - 1k - 1). In this paper we investigate the analogous problem for finite vector spaces.

Let F be a family of k-dimensional subspaces of an n-dimensional vector space over a field of q elements such that members of F intersect pairwise non-trivially. Employing a method of Katona, we show that for n ⩾ 2k, …F… ⩽ (k/n) [nk]q. By a more detailed analysis, we obtain that for n ⩾ 2k + 1, …F… ⩽ [n - 1k - 1]q, which is a best possible bound. The argument employed is generalized to the problem of finding a bound on the size of F when its members have pairwise intersection dimension no smaller than r. Again best possible results are obtained for n ⩾ 2k + 2 and n ⩾ 2k + 1, q ⩾ 3. Application of these methods to the analogous subset problem leads to improvement on the Erdös-Ko-Rado bounds.

Cited by (0)

Supported in part by ONR under Contract ONRN 00014-67-A-0204-0063.

Present address: Network Analysis Corporation, Glen Clove, N.Y. 11542, USA.