nach oben

Designs, Codes and Cryptography

Erschienen in:

09.09.2021

Egalitarian Steiner triple systems for data popularity

verfasst von: Charles J. Colbourn

Erschienen in: Designs, Codes and Cryptography | Ausgabe 10/2021

Einloggen, um Zugang zu erhalten

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

search-config

KI-gestützte Suche

Aus

Abstract

For an ordering of the blocks of a design, the point sum of an element is the sum of the indices of blocks containing that element. Block labelling for popularity asks for the point sums to be as equal as possible. For Steiner systems of order v and strength t in general, the average point sum is \(O(v^{2t-1})\); under various restrictions on block partitions of the Steiner system, the difference between the largest and smallest point sums is shown to be \(O(v^{(t+1)/2}\log v)\). Indeed for Steiner triple systems, direct and recursive constructions are given to establish that systems exist with all point sums equal for more than two thirds of the admissible orders.

Vorheriger Artikel Public key encryption with filtered equality test revisited

Nächster Artikel Efficient identity-based encryption with Hierarchical key-insulation from HIBE

Abel R.J.R., Lamken E.R., Wang J.: A few more Kirkman squares and doubly near resolvable BIBDs with block size 3. Discret. Math. 308(7), 1102–1123 (2008).MathSciNetMATHCrossRef

Alon N., Spencer J.H.: The Probabilistic Method. Wiley, Hoboken, NJ (2008).MATHCrossRef

Anderson I.: Some 2-rotational and cyclic designs. J. Combin. Des. 4(4), 247–254 (1996).MathSciNetMATHCrossRef

Anstice R.R.: On a problem in combinations. Camb. Dublin Math. J. 7, 279–292 (1852).

Anstice R.R.: On a problem in combinations (continued). Camb. Dublin Math. J. 8, 149–154 (1853).

Bermond J.C., Jean-Marie A., Mazauric D., Yu J.: Well-balanced designs for data placement. J. Combin. Des. 24(2), 55–76 (2016).MathSciNetMATHCrossRef

Beth T., Jungnickel D., Lenz H.: Design Theory. Vol. I, Encyclopedia of Mathematics and Its Applications, vol. 69, 2nd edn Cambridge University Press, Cambridge (1999).MATH

Bose R.C.: On the construction of balanced incomplete block designs. Ann. Eugen. 9(4), 353–399 (1939).MathSciNetCrossRef

Buratti M., Ghinelli D.: On disjoint \((3t,3,1)\) cyclic difference families. J. Stat. Plann. Inference 140(7), 1918–1922 (2010).MathSciNetMATHCrossRef

10.

Buratti M., Zuanni F.: \(G\)-invariantly resolvable Steiner \(2\)-designs which are \(1\)-rotational over \(G\). Bull. Belg. Math. Soc. Simon Stevin 5(2–3), 221–235 (1998).MathSciNetMATH

11.

Buratti M., Zuanni F.: Explicit constructions for 1-rotational Kirkman triple systems. Util. Math. 59, 27–30 (2001).MathSciNetMATH

12.

Chee Y.M., Colbourn C.J., Dau H., Gabrys R., Ling A.C.H., Lusi D., Milenkovic O.: Access balancing in storage systems by labeling partial Steiner systems. Des. Codes Cryptogr. 88, 2361–2376 (2020).MathSciNetMATHCrossRef

13.

Chernoff H.: A note on an inequality involving the normal distribution. Ann. Probab. 9(3), 533–535 (1981).MathSciNetMATHCrossRef

14.

Chung F., Lu L.: Concentration inequalities and martingale inequalities: a survey. Internet Math. 3(1), 79–127 (2006).MathSciNetMATHCrossRef

15.

Cohen M.B., Colbourn C.J.: Optimal and pessimal orderings of Steiner triple systems in disk arrays. Theor. Comput. Sci. 297(1–3), 103–117 (2003).MathSciNetMATHCrossRef

16.

Colbourn C.J.: Separations of Steiner triple systems: some questions. Bull. ICA 6, 53–56 (1992).MathSciNetMATH

17.

Colbourn C.J.: Popularity block labelling for Steiner systems. In: Seventeenth International Workshop on Algebraic and Combinatorial Coding Theory (ACCT2020), pp. 41–46 (2020)

18.

Colbourn C.J.: Egalitarian edge orderings of complete graphs. Graphs Combin. 37(4), 1405–1413 (2021).MathSciNetMATHCrossRef

19.

Colbourn C.J., Hoffman D.G., Rees R.: A new class of group divisible designs with block size three. J. Combin. Theory Ser. A 59(1), 73–89 (1992).MathSciNetMATHCrossRef

20.

Colbourn C.J., Horsley D., Wang C.: Trails of triples in partial triple systems. Des. Codes Cryptogr. 65(3), 199–212 (2012).MathSciNetMATHCrossRef

21.

Colbourn C.J., Lamken E.R., Ling A.C.H., Mills W.H.: The existence of Kirkman squares–doubly resolvable \((\nu,3,1)\)-BIBDs. Des. Codes Cryptogr. 26(1–3), 169–196 (2002).MathSciNetMATHCrossRef

22.

Colbourn C.J., Rosa A.: Triple Systems. Oxford Mathematical Monographs. Clarendon Press, Oxford (1999).

23.

Dau H., Milenkovic O.: MaxMinSum Steiner systems for access balancing in distributed storage. SIAM J. Discret. Math. 32(3), 1644–1671 (2018).MathSciNetMATHCrossRef

24.

Dewar M., Stevens B.: Ordering Block Designs: Gray Codes, Universal Cycles and Configuration Orderings CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York (2012).MATHCrossRef

25.

Dinitz J.H., Rodney P.: Disjoint difference families with block size \(3\). Util. Math. 52, 153–160 (1997).MathSciNetMATH

26.

Dinitz J.H., Shalaby N.: Block disjoint difference families for Steiner triple systems: \(v\equiv 3\,\text{ mod }\,6\). J. Stat. Plann. Inference 106(1–2), 77–86 (2002).MATHCrossRef

27.

Feng T., Horsley D., Wang X.: Novák’s conjecture on cyclic Steiner triple systems and its generalization (2020)

28.

Grannell M..J.., Griggs T..S.: Product constructions for cyclic block designs. I. Steiner quadruple systems. J. Combin. Theory Ser. A 36(1), 56–65 (1984).MathSciNetMATHCrossRef

29.

Guregová M., Rosa A.: Using the computer to investigate cyclic Steiner quadruple systems. Mat. Časopis Sloven. Akad. Vied 18, 229–239 (1968).MathSciNetMATH

30.

Hanani H.: A note on Steiner triple systems. Math. Scand. 8(1), 154–156 (1960).MathSciNetMATHCrossRef

31.

Hartman A.: The existence of resolvable Steiner quadruple systems. J. Combin. Theory Ser. A 44(2), 182–206 (1987).MathSciNetMATHCrossRef

32.

Hedayat A.S., Sloane N.J.A., Stufken J.: Orthogonal Arrays. Springer, New York (1999).MATHCrossRef

33.

Ji L., Zhu L.: Resolvable Steiner quadruple systems for the last 23 orders. SIAM J. Discrete Math. 19(2), 420–430 (2005).MathSciNetMATHCrossRef

34.

Longyear J.Q.: Nested group divisible designs and small nested designs. J. Stat. Plann. Inference 13(1), 81–87 (1986).MathSciNetMATHCrossRef

35.

Lu J.X.: Construction methods for balanced incomplete block designs and resolvable balanced incomplete block designs (in Chinese). In: L. Wu, L. Zhu, Q. Kang (eds.) Collected Works of Jiaxi Lu, pp. 1–24. Inner Mongolia People’s Press, Hunhot, Mongolia (1990). Unpublished (1965).

36.

Lu X.N., Jimbo M.: Affine-invariant strictly cyclic Steiner quadruple systems. Des. Codes Cryptogr. 83(1), 33–69 (2017).MathSciNetMATHCrossRef

37.

Mathon R.A., Phelps K.T., Rosa A.: Small Steiner triple systems and their properties. Ars Combin. 15, 3–110 (1983).MathSciNetMATH

38.

Meng Z.: Doubly resolvable Steiner quadruple systems and related designs. Des. Codes Cryptogr. 84(3), 325–343 (2017).MathSciNetMATHCrossRef

39.

Meng Z., Du B.: The last twenty orders of \((1,2)\)-resolvable Steiner quadruple systems. Discret. Math. 312(24), 3574–3584 (2012).MathSciNetMATHCrossRef

40.

Mood A.M.F., Graybill F.A., Boes D.C.: Introduction to the Theory of Statistics. McGraw-Hill, Chennai (1974).MATH

41.

Novák J.: A note on disjoint cyclic Steiner triple systems. In: Recent advances in graph theory (Proceedings Second Czechoslovak Symposium, Prague, 1974), pp. 439–440 (1975)

42.

Peltesohn R.: Eine Lösung der beiden Heffterschen Differenzenprobleme. Compos. Math. 6, 251–257 (1939).MathSciNetMATH

43.

Phelps K.T., Rosa A.: Steiner triple systems with rotational automorphisms. Discret. Math. 33(1), 57–66 (1981).MathSciNetMATHCrossRef

44.

Ray-Chaudhuri D.K., Wilson R.M.: Solution of Kirkman’s schoolgirl problem. In: Combinatorics (Proceedings of Symposium Pure Mathematics, Vol. XIX, University California, Los Angeles, CA, 1968), pp. 187–203 (1971).

45.

Siemon H.: Cyclic Steiner quadruple systems and Köhler’s orbit graphs. Des. Codes Cryptogr. 1(2), 121–132 (1991).MathSciNetMATHCrossRef

46.

Skolem T.: Some remarks on the triple systems of Steiner. Math. Scand. 6, 273–280 (1959).MathSciNetMATHCrossRef

47.

Stewart B.M.: Supermagic complete graphs. Can. J. Math. 19, 427–438 (1967).MathSciNetMATHCrossRef

48.

Stinson D.R.: Combinatorial Designs. Constructions and Analysis. Springer, New York (2004).MATH

49.

Vanstone S.A., Stinson D.R., Schellenberg P.J., Rosa A., Rees R.S., Colbourn C.J., Carter M.W., Carter J.E.: Hanani triple systems. Israel J. Math. 83(3), 305–319 (1993).MathSciNetMATHCrossRef

50.

Wei H., Ge G., Colbourn C.J.: The existence of well-balanced triple systems. J. Combin. Des. 24(2), 77–100 (2016).MathSciNetMATHCrossRef

51.

Yu W., Zhang X., Ge G.: Optimal fraction repetition codes for access-balancing in distributed storage. IEEE Trans. Inf. Theory 67(3), 1630–1640 (2021).MathSciNetMATHCrossRef

Titel: Egalitarian Steiner triple systems for data popularity
verfasst von: Charles J. Colbourn
Publikationsdatum: 09.09.2021
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 10/2021
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00925-0

Springer Professional

Egalitarian Steiner triple systems for data popularity

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 10/2021

Construction of LDPC convolutional codes via difference triangle sets

Improved indifferentiability security proof for 3-round tweakable Luby–Rackoff

Construction of binary LCD codes, ternary LCD codes and quaternary Hermitian LCD codes

Extended cyclic codes, maximal arcs and ovoids

Cyclic orbit flag codes

Twisted cubic and point-line incidence matrix in

Premium Partner