×

On directed designs with block size five. (English) Zbl 0959.05015

A \(t\)-\((v,k,\lambda)\) directed design is a pair \(({\mathcal P},{\mathcal B})\) where \({\mathcal P}\) is a set of \(v\) elements, or points, and \({\mathcal B}\) is a collection of ordered \(k\)-tuples of distinct elements of \({\mathcal P}\), called blocks, with the property that every ordered \(t\)-tuple of distinct elements of \({\mathcal P}\) occurs in exactly \(\lambda\) blocks (as a subsequence). In this paper the authors restrict their attention to directed designs with \(\lambda = 1\), \(k = 5\) and \(t=3,\) 4. For \(t=3\) no designs were previously known. A. Mahmoodi [Combinatorial and algorithmic aspects of directed designs, PhD thesis, University of Toronto (1995)] showed by computer search that there is no such design for \(v=5, 6\) or \(7\). The authors give an analytical proof of this result. They also construct the first known \(3\)-\((v,5,1)\) directed designs, namely for \(v=26\), 37. In particular, they have determined, by computer search, that there are precisely two non-isomorphic \(3\)-\((26,5,1)\) directed designs that are invariant under the group of mappings \(\{z \mapsto az+b\mid a,b \in Z_{26}\) and \((a,26)=1\}\). One of these can be used to show that there exists a \(3\)-\((25^n+1,5,1)\) directed design for any \(n \geq 1\). For the case \(t=4\), the authors construct \(4\)-\((v,5,1)\) directed designs for the new values \(v=7,8,13,18\) and \(48\). For \(v=8\), 18 and 48 the designs were constructed by hand or by computers assuming the action of a group of the form \(\text{PGL}_2(p^\alpha)\). For \(v=7\) the cyclic group \(\{z \mapsto z+b\mid b \in Z_7\}\) was used, and for \(v=13\) the Frobenius group \(\{z \mapsto az+b\mid a,b \in Z_{13}\) and \(a \neq 0\}\) was used. The existence of a \(4\)-\((7,5,1)\) directed design is of particular importance as it permits the construction of the first infinite class of \(4\)-\((v,5,1)\) directed designs, namely the set of \(4\)-\((2^n-1,5,1)\) directed designs for all \(n \geq 3\).

MSC:

05B05 Combinatorial aspects of block designs

Keywords:

directed design
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] F.E. Bennett, R. Wei, J. Yin andA. Mahmoodi, Existence of DBIBDs with block size 6,Utilitas Math. 43 (1993), 205-217. · Zbl 0792.05015
[2] F.E. Bennett andA. Mahmoodi, Directed designs, inThe CRC Handbook of Combinatorial Designs (ed. C.J. Colbourn and J.H. Dinitz), pages 317-321, CRC Press, Boca Raton, 1996. · Zbl 0848.05016
[3] A.Betten, R.Laue and A.Wassermann, A Steiner 5-design on 36 points,Des. Codes Cryptogr. 17, 181-186. · Zbl 0934.05015
[4] C.J.Colbourn and R.A.Mathon, Steiner systems, inThe CRC Handbook of Combinatorial Designs (ed. C.J. Colbourn and J.H. Dinitz), CRC Press, 1996, 66-75. · Zbl 0851.05020
[5] C.J. Colbourn andA. Rosa, Directed and Mendelsohn triple systems, inContemporary Design Theory: A Collection of Surveys (ed. J.H. Dinitz and D.R. Stinson). pages 97-136, John Wiley and Sons, New York, 1992. · Zbl 0767.05026
[6] J.E. Dawson, J. Seberry andD.B. Skillicorn, The directed packing numbers DD(t, v, v)t?4,Combinatorica 4 (2-3) (1984), 121-130. · Zbl 0554.05018 · doi:10.1007/BF02579211
[7] M.J. Grannell, T.S. Griggs andR.A. Mathon, Some Steiner 5-designs with 108 and 132 points,J. Combin. Des. 1 (1993), 213-238. · Zbl 0820.05009 · doi:10.1002/jcd.3180010304
[8] M.J.Grannell, T.S.Griggs and K.A.S.Quinn, All admissible 3-(v, 4, ?) directed designs exist,J. Combin. Math. Combin. Comput., to appear. · Zbl 0972.05009
[9] S.H.Y. Hung andN.S. Mendelsohn, Directed triple systems,J. Combin. Theory Ser. A 14 (1973), 310-318. · Zbl 0263.05020 · doi:10.1016/0097-3165(73)90007-1
[10] E.S. Kramer, Some results on t-wise balanced designs,Ars Combin. 15 (1983), 179-192. · Zbl 0516.05009
[11] V. Levenshtein, On perfect codes in deletion and insertion metric,Discrete Math. Appl. 2 (1992), 241-258. · doi:10.1515/dma.1992.2.3.241
[12] A.Mahmoodi,Combinatorial and algorithmic aspects of directed designs, PhD thesis, University of Toronto, 1995.
[13] J. Seberry andD.B. Skillicorn, All directed DBIBDs withk=3 exist,J. Combin. Theory Ser. A 29 (1980), 244-248. · Zbl 0439.05011 · doi:10.1016/0097-3165(80)90014-X
[14] N.Soltankhah, Directed quadruple designs, inCombinatorics Advances (ed. C.J. Colbourn and E.S. Mahmoodian), pages 277-291, Kluwer Academic Publishers, 1995. · Zbl 0837.05018
[15] D.J. Street andJ. Seberry, All DBIBDs with block size four exist,Utilitas Math. 18 (1980), 27-34. · Zbl 0455.05015
[16] D.J. Street andW.H. Wilson, On directed balanced incomplete block designs with block size five,Utilitas Math. 18 (1980), 161-174. · Zbl 0454.05012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.