An analogue of the Erdös-Ko-Rado theorem for the distance-regular graphs of bilinear forms

✍ Scribed by Tayuan Huang

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 425 KB
• Volume: 64
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90188-9

✦ Synopsis

An analogue of the Erd6s-Ko-Rado theorem is proved for the distance-regular graphs Hq(k, n) with k x n matrices over GF(q) as vertex set and two matrices A and B adjacent if the rank of A -B is 1, where n >~ k + 1 and (n, q) ~ (k + 1, 2). As an easy corollary, we prove that Hq(k, n) has no perfect e-codes, e ~> 1.

][. llltroduction Erd6s, Ko and Ratio [7] proved the following theorem for subsets of a finite set:

Let 3~ be a collection of k-subsets of an n-set X where n I> n0(r, k) and 0 ~< r ~< k. If [An BI I> r for all A, B e ~, then I,~1 ~< (5 --~). Equality occurs if and only if ~: consists of all k-subsets which contain a fixed r-subset of X (i.e., n ~ = f'~A consists of r elements). The original proof in [7] established that n0(r, k)~< r + (k-r)(k) 3. In 1976, Frankl [8] improved that no(r, k) = (r + 1)(k -r + 1) for r ~ 15. Recently, Wilson [14] showed that no(r, k)=(r+l)(k-r+l) in the remaining cases, i.e., r=2,3,..., 14, and characterized the extremal configurations when n> (r + 1)(k -r + 1).

In the language of graphs, the Erd6s-Ko-Rado theorem gives the upper bound on the sizes of subsets of vertices with maximum distance k-r in the Johnson graph J(n, k) and characterizes the extremal cases, where J(n, k) is the graph with the set of all k-subsets of an n-set as vertex set and two vertices adjacent if their intersection consists of k -1 points. We note that J(n, k) is a distance-regular graph and the distance between any two vertices A and B is k -r if and only if ]A A B[ = r. Analogous results are known for some other distance-regular graphs, e.g. [10] for Hamming graphs, [9] for q-analog Johnson graphs, and [13] for dual polar spaces. The reader is referred to [1,3] for the definition and fundamental properties of distance-regular graphs. In this paper, by modifying the technique used by Hsieh [9], we prove an analogous theorem for the distance-regular graph Hq(k, n) defined on Mgx.(q), the set of all k x n matrices over GF(q), with two vertices A, B adjacent if the rank of A -B is 1. It