Directed \(t\)-packings and directed \(t\)-Steiner systems
type: Item
instance of: scholarly article
title: Directed \(t\)-packings and directed \(t\)-Steiner systems
zbMATH Open document ID: 0959.05020
DOI: 10.1023/A:1008353723204
author: Tran van Trung
author: Rudolf Mathon
published in: Designs, Codes and Cryptography
publication date: 2001-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 94B60
zbMATH DE Number: 1548351
zbMATH Keywords: directed packings
zbMATH Keywords: directed designs
zbMATH Keywords: directed Steiner systems
zbMATH Keywords: deletion correcting codes
zbMATH Keywords: perfect codes
reviewed by: Peter Brass
MaRDI profile type: Publication
full work available at URL: a:1008353723204
OpenAlex ID: W1618405538
description: scientific article; zbMATH DE number 1548351