Configurations with Subset Restrictions

Abstract

An $[r,s,n,t]$-configuration is a collection $C$ of $r$-sets in $\{1,\dots ,n\}$ such that every $s$-set in $\{1,\dots ,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\le n\le 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$.