Directed \(t\)-packings and directed \(t\)-Steiner systems
A directed \(t\)-\((v,k,\lambda)\)-design is a collection of ordered \(k\)-tuples chosen from a \(v\)-element ground set such that each ordered \(t\)-tuple from that ground set occurs in exactly \(\lambda\) of those \(k\)-tuples in that order. For \(\lambda=1\) they are called directed Steiner systems. So a directed design is a variant of a block design, in which the elements of each block are also ordered. They were introduced by \textit{V. I.~Levenshtein} [Diskretn. Mat. 3, No. 1, 3--20 (1991; Zbl 0732.94015 and Zbl 0787.94023)] in connection with a coding problem, since they can be considered as perfect \(k-t\)-deletion correcting codes. In this paper the authors are especially interested in \((t,k,k)\)-Steiner systems, systems of permutations of a \(k\)-element set such that each permutation of a \(t\)-element subset occurs in that order in exactly one permutation of the system. They give a counterexample to a conjecture of Levenshtein by showing that a \((4,6,6)\)-directed Steiner system exists, they completely classify all such systems, show a connection to a property of the symmetric group \(S_6\), and obtain a number of further results on existence and nonexistence of small such directed Steiner systems.
scientific article; zbMATH DE number 1548351