Configurations with Subset Restrictions

Abstract

An \( [r, s, n, t] \)-configuration is a collection \(C\) of \(r\)-sets in \( \{1, \ldots, n\} \) such that every \( s \)-set in \( \{1, \ldots, n\} \) contains at most \( t \) of the \( r \)-sets in \( C \). Studying this generalization of the Steiner system was suggested by a theorem of Poonen on union-closed families of sets. In this paper, we consider only \( [3, 4, n, 2] \)-configurations, and refer to them as \(n\)-configurations; by an \( (n, k) \)-configuration we mean an \(n\)-configuration containing exactly \(k\) \(3\)-sets. An \((n,k)\)-configuration is maximal if it is not contained in any \( (n, k + 1) \)-configuration; finally, \( L(n) \) is the largest integer \(k\) for which an \((n, k)\)-configuration exists. In this paper, we determine \(L(n)\) for \( 4 \leq n \leq 9 \), and characterize all the maximal \( n \)-configurations for \(n = 4, 5,\) and \(6\), as well as the \((n, L(n))\)-configurations for \( n = 7, 8, \) and \( 9 \).