Universal cycles for minimum coverings of pairs by triples, with application to 2-radius sequences

Chee, Yeow; Ling, San; Tan, Yin; Zhang, Xiande

doi:10.1090/S0025-5718-2011-02473-7

Universal cycles for minimum coverings of pairs by triples, with application to 2-radius sequences
HTML articles powered by AMS MathViewer

by Yeow Meng Chee, San Ling, Yin Tan and Xiande Zhang;

Math. Comp. 81 (2012), 585-603

DOI: https://doi.org/10.1090/S0025-5718-2011-02473-7

Published electronically: June 21, 2011

PDF | Request permission

Abstract:

A new ordering, extending the notion of universal cycles of Chung et al. (1992), is proposed for the blocks of $k$-uniform set systems. Existence of minimum coverings of pairs by triples that possess such an ordering is established for all orders. The application to the construction of short 2-radius sequences is given, along with some new 2-radius sequences found through a computer search.

References

Alok Aggarwal and Jeffrey Scott Vitter, The input/output complexity of sorting and related problems, Comm. ACM 31 (1988), no. 9, 1116–1127. MR 1021794, DOI 10.1145/48529.48535
Brian Alspach, Katherine Heinrich, and Bojan Mohar, A note on Hamilton cycles in block-intersection graphs, Finite geometries and combinatorial designs (Lincoln, NE, 1987) Contemp. Math., vol. 111, Amer. Math. Soc., Providence, RI, 1990, pp. 1–4. MR 1079733, DOI 10.1090/conm/111/1079733
James R. Bitner, Gideon Ehrlich, and Edward M. Reingold, Efficient generation of the binary reflected Gray code and its applications, Comm. ACM 19 (1976), no. 9, 517–521. MR 424386, DOI 10.1145/360336.360343
S. R. Blackburn and J. F. Mckee, Constructing $k$-radius sequences, arXiv:1006.5812v1 (2010).
A. E. Brouwer, A. Schrijver, and H. Hanani, Group divisible designs with block-size four, Discrete Math. 20 (1977/78), no. 1, 1–10. MR 465894, DOI 10.1016/0012-365X(77)90037-1
Fan Chung, Persi Diaconis, and Ron Graham, Universal cycles for combinatorial structures, Discrete Math. 110 (1992), no. 1-3, 43–59. MR 1197444, DOI 10.1016/0012-365X(92)90699-G
Charles J. Colbourn, Dean G. Hoffman, and Rolf Rees, A new class of group divisible designs with block size three, J. Combin. Theory Ser. A 59 (1992), no. 1, 73–89. MR 1141323, DOI 10.1016/0097-3165(92)90099-G
Charles J. Colbourn and Alexander Rosa, Triple systems, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1999. MR 1843379
N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch., Proc. 49 (1946), 758–764 = Indagationes Math. 8, 461–467 (1946). MR 18142
Megan Dewar, Gray codes, Universal cycles and configuration orderings for block designs, ProQuest LLC, Ann Arbor, MI, 2007. Thesis (Ph.D.)–Carleton University (Canada). MR 2711021
Peter Eades and Brendan McKay, An algorithm for generating subsets of fixed size with a strong minimal change property, Inform. Process. Lett. 19 (1984), no. 3, 131–133. MR 782221, DOI 10.1016/0020-0190(84)90091-7
M. K. Fort Jr. and G. A. Hedlund, Minimal coverings of pairs by triples, Pacific J. Math. 8 (1958), 709–719. MR 103831
Sakti P. Ghosh, Consecutive storage of relevant records with redundancy, Comm. ACM 18 (1975), no. 8, 464–471. MR 383863, DOI 10.1145/360933.360991
J. W. Gilkerson and J. W. Jaromczyk, Restoring the order of images in a sequence of MRI slices, unpublished manuscript (2002).
J. W. Gilkerson, J. W. Jaromczyk, and Z. Lonc, On constructing sequences of radius $k$ using finite geometries, unpublished manuscript.
F. Gray, Pulse code communication, 1953 (file 1947), US Patent 2,632,058.
H.-D. O. F. Gronau, R. C. Mullin, and Ch. Pietsch, The closure of all subsets of $\{3,4,\cdots ,10\}$ which include $3$, Ars Combin. 41 (1995), 129–161. MR 1365159
Donovan R. Hare, Cycles in the block-intersection graph of pairwise balanced designs, Discrete Math. 137 (1995), no. 1-3, 211–221. MR 1312454, DOI 10.1016/0012-365X(93)E0140-Y
Peter Horák, David A. Pike, and Michael E. Raines, Hamilton cycles in block-intersection graphs of triple systems, J. Combin. Des. 7 (1999), no. 4, 243–246. MR 1691408, DOI 10.1002/(SICI)1520-6610(1999)7:4<243::AID-JCD2>3.3.CO;2-1
Peter Horák and Alexander Rosa, Decomposing Steiner triple systems into small configurations, Ars Combin. 26 (1988), 91–105. MR 982111
Glenn Hurlbert, On universal cycles for $k$-subsets of an $n$-set, SIAM J. Discrete Math. 7 (1994), no. 4, 598–604. MR 1299088, DOI 10.1137/S0895480191220861
B. Jackson, Universal cycles of $4$-subsets and $5$-subsets, unpublished manuscript.
B. W. Jackson, Universal cycles of $k$-subsets and $k$-permutations, Discrete Math. 117 (1993), no. 1-3, 141–150. MR 1226137, DOI 10.1016/0012-365X(93)90330-V
Jerzy W. Jaromczyk and Zbigniew Lonc, Sequences of radius $k$: how to fetch many huge objects into small memory for pairwise computations, Algorithms and computation, Lecture Notes in Comput. Sci., vol. 3341, Springer, Berlin, 2004, pp. 594–605. MR 2158364, DOI 10.1007/978-3-540-30551-4_{5}2
Hanfried Lenz, Some remarks on pairwise balanced designs, Mitt. Math. Sem. Giessen 165 (1984), 49–62. MR 745869
Frank Ruskey, Adjacent interchange generation of combinations, J. Algorithms 9 (1988), no. 2, 162–180. MR 936104, DOI 10.1016/0196-6774(88)90036-3
Carla Savage, A survey of combinatorial Gray codes, SIAM Rev. 39 (1997), no. 4, 605–629. MR 1491049, DOI 10.1137/S0036144595295272
Sandeep Sen, Siddhartha Chatterjee, and Neeraj Dumir, Towards a theory of cache-efficient algorithms, J. ACM 49 (2002), no. 6, 828–858. MR 2145858, DOI 10.1145/602220.602225
Charles J. Colbourn and Jeffrey H. Dinitz (eds.), Handbook of combinatorial designs, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007. MR 2246267
Richard M. Wilson, An existence theory for pairwise balanced designs. I. Composition theorems and morphisms, J. Combinatorial Theory Ser. A 13 (1972), 220–245. MR 304203, DOI 10.1016/0097-3165(72)90028-3