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

06-04-2016

Affine-invariant strictly cyclic Steiner quadruple systems

Authors: Xiao-Nan Lu, Masakazu Jimbo

Published in: Designs, Codes and Cryptography | Issue 1/2017

Login to get access

Activate our intelligent search to find suitable subject content or patents.

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.
Appendix
Available only for authorised users
Literature
1.
go back to reference 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.
go back to reference Alspach B.: Research problems. Discret. Math. 97, 419–423 (1991). Alspach B.: Research problems. Discret. Math. 97, 419–423 (1991).
3.
go back to reference 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.
go back to reference 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.
go back to reference Brand N.: Design invariants. Geom. Dedicata 21(2), 169–179 (1986). Brand N.: Design invariants. Geom. Dedicata 21(2), 169–179 (1986).
6.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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).
Metadata
Title
Affine-invariant strictly cyclic Steiner quadruple systems
Authors
Xiao-Nan Lu
Masakazu Jimbo
Publication date
06-04-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0201-z

Other articles of this Issue 1/2017

Designs, Codes and Cryptography 1/2017 Go to the issue

Premium Partner