## 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 PDF
- Math. Comp.
**81**(2012), 585-603 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**0424386**, 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**0383863**, 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

## Additional Information

**Yeow Meng Chee**- Affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
- Email: ymchee@ntu.edu.sg
**San Ling**- Affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
- Email: lingsan@ntu.edu.sg
**Yin Tan**- Affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
- Email: tanyin@ntu.edu.sg
**Xiande Zhang**- Email: ziandezhang@ntu.edu.sg
- Received by editor(s): September 20, 2009
- Received by editor(s) in revised form: August 6, 2010
- Published electronically: June 21, 2011
- Additional Notes: This research was supported in part by the National Research Foundation of Singapore under Research Grant NRF-CRP2-2007-03 and by the Nanyang Technological University under Research Grant M58110040.
- © Copyright 2011 American Mathematical Society
- Journal: Math. Comp.
**81**(2012), 585-603 - MSC (2010): Primary 05B05, 05B07, 05B40; Secondary 05C38, 68R05
- DOI: https://doi.org/10.1090/S0025-5718-2011-02473-7
- MathSciNet review: 2833510