On the spectrum of Steiner $(v,k,t)$ trades (1)

Abstract

A $(v,k,t)$ trade $T=T_1–T_2$ of volume $m$ consists of two disjoint collections $T_1$ and $T_2$, each containing $m$ blocks ($k$-subsets) such that every $t$-subset is contained in the same number of blocks in $T_1$ and $T_2$. If each $t$-subset occurs at most once in $T_1$, then $T$ is called a Steiner $(k,t)$ trade. In this paper, the spectrum (that is, the set of allowable volumes) of Steiner trades is discussed, with particular reference to the case $t=2$. It is shown that the volume of a Steiner $(k,2)$ trade is at least $2k–2$ and cannot equal $2k–1$. We show how to construct a Steiner $(k,2)$ trade of volume $m$ when $m\ge 3k–3$, or $m$ is even and $2k–2\le m\le 3k–4$. For $k=5$ or $6$, the non-existence of Steiner $(k,2)$ trades of volume $2k+1$ is demonstrated, and for $k=7$, we exhibit a Steiner $(k,2)$ trade of volume $2k+1$. In addition, the structure of Steiner $(k,2)$ trades of volumes $2k–2$ and $2k$ ($k\ne 3,4$) is shown to be unique. A generalisation of our constructions to trades with blocks based on arbitrary simple graphs is also presented.