Subsets of a Finite Set that Intersect Each Other in at Most One Element

Author: Keenan, Donald Eugene

Year: 1977

Degree: Dissertation (Ph.D.)

Advisor: Ryser, Herbert J.

Committee Member: Unknown, Unknown

Option: Mathematics

DOI: 10.7907/xcak-ax60

Abstract

We study subsets of a finite set most of which intersect each other in one element. We first prove a Fisher type inequality of the form m ≤ n. We then investigate those configurations with m = n. Our main theorem is the following generalization of a result due to Ryser .

Theorem. Let S1,...,Sn be n subsets of an n-set S.

Suppose that

| Si | ≥ 3 (i = 1,...,n)

and that

| Si ꓵ Sj | ≤ 1 (i ≠ j; i,j = 1,...,n)

Suppose further that each Si has non-empty intersection with at least n - c of the other subsets. Then either

n ≤ N(c)

where N(c) depends only on c, or the incidence matrix A has constant line sums.

We then study those configurations for which A has constant line sums and each subset has non-empty intersection with exactly n - 3 of the other subsets. The rows and columns of A may be partitioned into cycles in a natural way. With this we show that A has a cyclic substructure and that the length of any row or column cycle divides the length of the longest cycle. Also, after the rows and columns have been suitably permuted we have AAT = ATA. We relate those configurations with constant cycle lengths to interdependent difference sets, and show that such configurations imply the existence of nonnegative integral matrices satisfying the matrix equation BBT = (k - λ)l + λJ.

Files