Maximal and minimal coverings of (k − 1)-tuples by k-tuples

J. G. Kalbfleisch and Ralph Gordon Stanton

Vol. 26 (1968), No. 1, 131–140

DOI: 10.2140/pjm.1968.26.131

Abstract

For m ≧ k, an (m,k) system is a set of k-tuples (k-subsets) of 1, 2, ⋯,m. A minimal (m,k) system is an (m,k) system with the property that every (k − 1)-tuple of the m elements appears in at least one k-tuple of the system, but no system with fewer k-tuples has this property. The numbers of k-tuples in a minimal (m,k) system will be denoted by N_k(m). A maximal (m,k) is an (m,k) system with the property that no (k − 1)-tuple appears in more than one k-tuple of the system, but no system with more k-tuples has this property. The number of k-tuples in a maximal (m,k) system is D_k(m). In this paper we shall be concerned with evaluating N_k and D_k and investigating the properties of extremal (m,k) systems for k = 2,3, and 4.

Mathematical Subject Classification

Primary: 05.04

Milestones

Received: 11 August 1967

Published: 1 July 1968