Document Type
Article
Subject Area(s)
Mathematics
Abstract
We prove an Erdos-Ko-Rado-type theorem for intersecting k-chains of subspaces of a finite vector space. This is the q-generalization of earlier results of Erdos, Seress and Szekely for intersecting k-chains of subsets of an underlying set. The proof hinges on the author's proper generalization of the shift technique from extremal set theory to finite vector spaces, which uses a linear map to defi ne the generalized shift operation. The theorem is the following.
For c = 0; 1, consider k-chains of subspaces of an n-dimensional vector space over GF(q), such that the smallest subspace in any chain has dimension at least c, and the largest subspace in any chain has dimension at most n − c. The largest number of such k-chains under the condition that any two share at least one subspace as an element of the chain, is achieved by the following constructions:
(1) x a subspace of dimension c and take all k-chains containing it,
(2) x a subspace of dimension n − c and take all k-chains containing it.
Publication Info
Combinatorics, Probability and Computing, Volume 8, Issue 6, 1999, pages 509-528.
© 1999 by Cambridge University Press