Skip to main content
Erschienen in: Designs, Codes and Cryptography 1/2017

06.04.2016

Affine-invariant strictly cyclic Steiner quadruple systems

verfasst von: Xiao-Nan Lu, Masakazu Jimbo

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

To determine the spectrum of Steiner quadruple systems (SQS) admitting a specific automorphism group is of great interest in design theory. We consider a strictly cyclic SQS which is invariant under the affine group, called an AsSQS. For the applications of designs of experiments, group testing, filing schemes, authentication codes, and optical orthogonal codes for CDMA communication, etc., a larger automorphism group containing the cyclic group may work efficiently for the procedures of generating and searching blocks in a design with less storage and time. In this paper, constructions and a necessary condition for the existence of an AsSQS are investigated. For a prime \(p \equiv 1 \;({\hbox {mod}}\; 4)\), Direct Construction A establishes an AsSQS(2p), provided that a 1-factor of a graph exists, where the graph is defined by using a system of generators of the projective special linear group PSL(2, p). Direct Construction B gives an AsSQS(2p) which is 2-chromatic, provided that a rainbow 1-factor of a specific hypergraph exists. Accordingly, by proposing two recursive constructions of an AsSQSs\((2p^m)\) for a positive integer m, we prove that an AsSQS\((2p^m)\) exists, if the criteria developed for an AsSQS(2p) are satisfied. We verified the claim and found that an AsSQS\((2p^m)\) exists for every prime \(p \equiv 1 \;({\hbox {mod}}\; 4)\) with \(p < 10^5\) and any positive integer m.
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat Akiyama J., Kano M.: Factors and Factorizations of Graphs: Proof Techniques in Factor Theory. Lecture Notes in Mathematics, vol. 2031. Springer, Berlin (2011). Akiyama J., Kano M.: Factors and Factorizations of Graphs: Proof Techniques in Factor Theory. Lecture Notes in Mathematics, vol. 2031. Springer, Berlin (2011).
2.
Zurück zum Zitat Alspach B.: Research problems. Discret. Math. 97, 419–423 (1991). Alspach B.: Research problems. Discret. Math. 97, 419–423 (1991).
3.
Zurück zum Zitat Berman G.: The application of difference sets to the design of a balanced multiple-valued filing scheme. Inf. Control 32(2), 128–138 (1976). Berman G.: The application of difference sets to the design of a balanced multiple-valued filing scheme. Inf. Control 32(2), 128–138 (1976).
4.
Zurück zum Zitat Beth T., Jungnickel D., Lenz H.: Design Theory, vol. 1. Cambridge University Press, Cambridge (1999). Beth T., Jungnickel D., Lenz H.: Design Theory, vol. 1. Cambridge University Press, Cambridge (1999).
5.
Zurück zum Zitat Brand N.: Design invariants. Geom. Dedicata 21(2), 169–179 (1986). Brand N.: Design invariants. Geom. Dedicata 21(2), 169–179 (1986).
6.
Zurück zum Zitat Brand N., Sutinuntopas S.: One-factors and the existence of affine designs. Discret. Math. 120(1), 25–35 (1993). Brand N., Sutinuntopas S.: One-factors and the existence of affine designs. Discret. Math. 120(1), 25–35 (1993).
7.
Zurück zum Zitat Chu W., Colbourn C.J.: Optimal \((n, 4, 2)\)-OOC of small orders. Discret. Math. 279(1), 163–172 (2004). Chu W., Colbourn C.J.: Optimal \((n, 4, 2)\)-OOC of small orders. Discret. Math. 279(1), 163–172 (2004).
8.
Zurück zum Zitat Diks K., Stańczyk P.: Perfect matching for biconnected cubic graphs in \(O (n log^2 n)\) time. In: SOFSEM 2010: Theory and Practice of Computer Science, pp. 321–333. Springer, Berlin (2010). Diks K., Stańczyk P.: Perfect matching for biconnected cubic graphs in \(O (n log^2 n)\) time. In: SOFSEM 2010: Theory and Practice of Computer Science, pp. 321–333. Springer, Berlin (2010).
9.
Zurück zum Zitat Du D.Z., Hwang F.K.: Combinatorial Group Testing and Its Applications, 2nd edn. World Scientific, Singapore (1999). Du D.Z., Hwang F.K.: Combinatorial Group Testing and Its Applications, 2nd edn. World Scientific, Singapore (1999).
10.
Zurück zum Zitat Feng T., Chang Y., Ji L.: Constructions for strictly cyclic 3-designs and applications to optimal OOCs with \(\lambda = 2\). J. Comb. Theory, Ser. A 115(8), 1527–1551 (2008). Feng T., Chang Y., Ji L.: Constructions for strictly cyclic 3-designs and applications to optimal OOCs with \(\lambda = 2\). J. Comb. Theory, Ser. A 115(8), 1527–1551 (2008).
11.
Zurück zum Zitat Fuji-Hara R., Miao Y.: Optical orthogonal codes: their bounds and new optimal constructions. IEEE Trans. Inf. Theory 46(7), 2396–2406 (2000). Fuji-Hara R., Miao Y.: Optical orthogonal codes: their bounds and new optimal constructions. IEEE Trans. Inf. Theory 46(7), 2396–2406 (2000).
12.
Zurück zum Zitat Grannel M., Griggs T.: Some recent results on cyclic Steiner quadruple systems—a survey. Ann. Discret. Math. 18, 409–418 (1983). Grannel M., Griggs T.: Some recent results on cyclic Steiner quadruple systems—a survey. Ann. Discret. Math. 18, 409–418 (1983).
13.
Zurück zum Zitat Hanani H.: On quadruple systems. Can. J. Math. 12, 145–157 (1960). Hanani H.: On quadruple systems. Can. J. Math. 12, 145–157 (1960).
14.
Zurück zum Zitat Hartman A., Phelps K.T.: Steiner quadruple systems. In: Dinitz, J., Stinson, D. (eds.) Contemporary Design Theory: A Collection of Surveys, Chap. 6, pp. 205–240. Wiley, New York (1992). Hartman A., Phelps K.T.: Steiner quadruple systems. In: Dinitz, J., Stinson, D. (eds.) Contemporary Design Theory: A Collection of Surveys, Chap. 6, pp. 205–240. Wiley, New York (1992).
15.
Zurück zum Zitat Ji L.: A construction for 2-chromatic Steiner quadruple systems. Eur. J. Comb. 28(6), 1832–1838 (2007). Ji L.: A construction for 2-chromatic Steiner quadruple systems. Eur. J. Comb. 28(6), 1832–1838 (2007).
16.
Zurück zum Zitat Kasami T., Lin S., Peterson W.W.: Some results on cyclic codes which are invariant under the affine group and their applications. Inf. Control 11(5), 475–496 (1967). Kasami T., Lin S., Peterson W.W.: Some results on cyclic codes which are invariant under the affine group and their applications. Inf. Control 11(5), 475–496 (1967).
17.
Zurück zum Zitat Köhler E.: Zyklische quadrupelsysteme. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 48, pp. 1–24. Springer, Berlin (1979). Köhler E.: Zyklische quadrupelsysteme. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 48, pp. 1–24. Springer, Berlin (1979).
18.
Zurück zum Zitat Köhler E.: \(k\)-Difference cycles and the construction of cyclic \(t\)-designs. Geometries and Groups. Lecture Notes in Mathematics, vol. 893, pp. 195–203. Springer, Berlin (1981). Köhler E.: \(k\)-Difference cycles and the construction of cyclic \(t\)-designs. Geometries and Groups. Lecture Notes in Mathematics, vol. 893, pp. 195–203. Springer, Berlin (1981).
19.
Zurück zum Zitat Köhler E.: Quadruple systems over \({\mathbb{Z}} _{p}\) admitting the affine group. Combinatorial Theory. Lecture Notes in Mathematics, vol. 969, pp. 212–228. Springer, Berlin (1982). Köhler E.: Quadruple systems over \({\mathbb{Z}} _{p}\) admitting the affine group. Combinatorial Theory. Lecture Notes in Mathematics, vol. 969, pp. 212–228. Springer, Berlin (1982).
20.
Zurück zum Zitat Lenz H., Ringel G.: A brief review on Egmont Köhler’s mathematical work. Discret. Math. 97(1), 3–16 (1991). Lenz H., Ringel G.: A brief review on Egmont Köhler’s mathematical work. Discret. Math. 97(1), 3–16 (1991).
21.
Zurück zum Zitat Limaye N.B.: Cross-ratios and projectivities of a line. Math. Z. 129(1), 49–53 (1972). Limaye N.B.: Cross-ratios and projectivities of a line. Math. Z. 129(1), 49–53 (1972).
22.
Zurück zum Zitat Lindner C.C., Rosa A.: Steiner quadruple systems—a survey. Discret. Math. 22(2), 147–181 (1978). Lindner C.C., Rosa A.: Steiner quadruple systems—a survey. Discret. Math. 22(2), 147–181 (1978).
23.
Zurück zum Zitat Lu X.N.: On affine-invariant two-fold quadruple systems. Graphs Comb. 31(6), 1915–1927 (2015). Lu X.N.: On affine-invariant two-fold quadruple systems. Graphs Comb. 31(6), 1915–1927 (2015).
24.
Zurück zum Zitat Munemasa A., Sawa M.: Steiner quadruple systems with point-regular abelian automorphism groups. J. Stat. Theory Pract. 6(1), 97–128 (2012). Munemasa A., Sawa M.: Steiner quadruple systems with point-regular abelian automorphism groups. J. Stat. Theory Pract. 6(1), 97–128 (2012).
25.
Zurück zum Zitat Pei D.: Authentication Codes and Combinatorial Designs. CRC Press, Boca Raton (2006). Pei D.: Authentication Codes and Combinatorial Designs. CRC Press, Boca Raton (2006).
26.
Zurück zum Zitat Peterson P.A., Loui M.C.: The general maximum matching algorithm of Micali and Vazirani. Algorithmica 3(1–4), 511–533 (1988). Peterson P.A., Loui M.C.: The general maximum matching algorithm of Micali and Vazirani. Algorithmica 3(1–4), 511–533 (1988).
27.
Zurück zum Zitat Phelps K., Rosa A.: 2-Chromatic Steiner quadruple systems. Eur. J. Comb. 1(3), 253–258 (1980). Phelps K., Rosa A.: 2-Chromatic Steiner quadruple systems. Eur. J. Comb. 1(3), 253–258 (1980).
28.
Zurück zum Zitat Piotrowski W.: Untersuchungen über S-zyklische Quadrupelsysteme. Ph.D. thesis, Universität Hamburg (1985). Piotrowski W.: Untersuchungen über S-zyklische Quadrupelsysteme. Ph.D. thesis, Universität Hamburg (1985).
29.
Zurück zum Zitat Plesník J.: Remarks on regular factors of regular graphs. Czech. Math. J. 24(2), 292–300 (1974). Plesník J.: Remarks on regular factors of regular graphs. Czech. Math. J. 24(2), 292–300 (1974).
30.
Zurück zum Zitat Siemon H.: Some remarks on the construction of cyclic Steiner quadruple systems. Arch. Math. 49(2), 166–178 (1987). Siemon H.: Some remarks on the construction of cyclic Steiner quadruple systems. Arch. Math. 49(2), 166–178 (1987).
31.
Zurück zum Zitat Siemon H.: Infinite families of strictly cyclic Steiner quadruple systems. Discret. Math. 77(1–3), 307–316 (1989). Siemon H.: Infinite families of strictly cyclic Steiner quadruple systems. Discret. Math. 77(1–3), 307–316 (1989).
32.
Zurück zum Zitat Siemon H.: Cyclic Steiner quadruple systems and Köhler’s orbit graphs. Des. Codes Cryptogr. 1(2), 121–132 (1991). Siemon H.: Cyclic Steiner quadruple systems and Köhler’s orbit graphs. Des. Codes Cryptogr. 1(2), 121–132 (1991).
33.
Zurück zum Zitat Siemon H.: On the existence of cyclic Steiner quadruple systems SQS(\(2p\)). Discret. Math. 97(1), 377–385 (1991). Siemon H.: On the existence of cyclic Steiner quadruple systems SQS(\(2p\)). Discret. Math. 97(1), 377–385 (1991).
34.
Zurück zum Zitat Siemon H.: Piotrowski’s infinite series of Steiner quadruple systems revisited. Des. Codes Cryptogr. 8, 239–254 (1996). Siemon H.: Piotrowski’s infinite series of Steiner quadruple systems revisited. Des. Codes Cryptogr. 8, 239–254 (1996).
35.
Zurück zum Zitat Siemon H.: A number theoretic conjecture and the existence of S-cyclic Steiner quadruple systems. Des. Codes Cryptogr. 13(1), 63–94 (1998). Siemon H.: A number theoretic conjecture and the existence of S-cyclic Steiner quadruple systems. Des. Codes Cryptogr. 13(1), 63–94 (1998).
36.
Zurück zum Zitat Stinson D.R.: Some constructions and bounds for authentication codes. J. Cryptol. 1(1), 37–51 (1988). Stinson D.R.: Some constructions and bounds for authentication codes. J. Cryptol. 1(1), 37–51 (1988).
37.
Zurück zum Zitat Vazirani V.V.: A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm. Combinatorica 14(1), 71–109 (1994). Vazirani V.V.: A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm. Combinatorica 14(1), 71–109 (1994).
38.
Zurück zum Zitat Yamamoto S., Teramoto T., Futagami K.: Design of a balanced multiple-valued filing scheme of order two based on cyclically generated spread in finite projective geometry. Inf. Control 21(1), 72–91 (1972). Yamamoto S., Teramoto T., Futagami K.: Design of a balanced multiple-valued filing scheme of order two based on cyclically generated spread in finite projective geometry. Inf. Control 21(1), 72–91 (1972).
39.
Zurück zum Zitat Yoshikawa S.: Constructions of strictly cyclic Steiner quadruple systems admitting all units of \({\mathbb{Z}}_{p}\) as multipliers (in Japanese). Master’s thesis, Nagoya University (2009). Yoshikawa S.: Constructions of strictly cyclic Steiner quadruple systems admitting all units of \({\mathbb{Z}}_{p}\) as multipliers (in Japanese). Master’s thesis, Nagoya University (2009).
40.
Zurück zum Zitat Yu Q.R., Liu G.: Graph Factors and Matching Extensions. Springer, Berlin (2009). Yu Q.R., Liu G.: Graph Factors and Matching Extensions. Springer, Berlin (2009).
Metadaten
Titel
Affine-invariant strictly cyclic Steiner quadruple systems
verfasst von
Xiao-Nan Lu
Masakazu Jimbo
Publikationsdatum
06.04.2016
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 1/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0201-z

Weitere Artikel der Ausgabe 1/2017

Designs, Codes and Cryptography 1/2017 Zur Ausgabe