Independent Sets in Steiner Triple Systems

Abstract

A set of points in a Steiner triple system (STS($v$)) is said to be independent if no three of these points occur in the same block. In this paper, we derive for each $k\le 8$ a closed formula for the number of independent sets of cardinality $k$ in an STS($v$). We use the formula to prove that every STS(21) has an independent set of cardinality eight and is, as a consequence, $4$-colourable.