Maximal Subsets of a given Set having No Triple in Common with a Steiner Triple System on the set

Authors:
  • NSN. Sauer
    N. Sauer
  • JSJ. Schönheim
    J. Schönheim

Abstract
Let E be a finite set containing n elements, n ≡ 1, 3 (mod 6), S = S(E) a Steiner triple system on E, i.e. each unordered pair of elements of E is a subset of exactly one triple in S. Let T be a subset of E such that none of the triples of elements of T is a member of S. Erdös has asked (in a recent letter to the authors) for the maximal size of such a set T. Denote max |T| for fixed n and S by f(n, S). We prove in this note the following result: (i) (ii)for every n ≡ 1, 3 (mod 6) there exists a Steiner triple system S0 such that equality holds in i.