Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Authors: Yeow Meng Chee, San Ling, Yin Tan and Xiande Zhang
Journal: Math. Comp. 81 (2012), 585-603
MSC (2010): Primary 05B05, 05B07, 05B40; Secondary 05C38, 68R05
Published electronically: June 21, 2011
MathSciNet review: 2833510
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. A. Aggarwal and J. S. Vitter, The input/output complexity of sorting and related problems, Commun. ACM 31 (1988), no. 9, 1116-1127. MR 1021794 (90k:68029)
  • 2. B. Alspach, K. Heinrich, and B. 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 (91h:05079)
  • 3. J. R. Bitner, G. Ehrlich, and E. M. Reingold, Efficient generation of the binary reflected Gray code and its applications, Comm. ACM 19 (1976), no. 9, 517-521. MR 0424386 (54:12349)
  • 4. S. R. Blackburn and J. F. Mckee, Constructing $ k$-radius sequences, arXiv:1006.5812v1 (2010).
  • 5. A. E. Brouwer, A. Schrijver, and H. Hanani, Group divisible designs with block-size four, Discrete Math. 20 (1977), no. 1, 1-10. MR 0465894 (57:5780)
  • 6. F. Chung, P. Diaconis, and R. Graham, Universal cycles for combinatorial structures, Discrete Math. 110 (1992), no. 1-3, 43-59. MR 1197444 (93m:05018)
  • 7. C. J. Colbourn, D. G. Hoffman, and R. 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 (93f:05015)
  • 8. C. J. Colbourn and A. Rosa, Triple Systems, Oxford Mathematical Monographs, Oxford University Press, New York, 1999. MR 1843379 (2002h:05024)
  • 9. N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch., Proc. 49 (1946), 758-764 = Indagationes Math. 8, 461-467 (1946). MR 0018142 (8:247d)
  • 10. M. Dewar, Gray codes, universal cycles and configuration orderings for block designs, Ph.D. thesis, Carleton University, Ottawa, Ontario, Canada, ProQuest LLC, Ann Arbor, MI, 2007. MR 2711021
  • 11. P. Eades and B. 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 (86d:68058)
  • 12. M. K. Fort, Jr. and G. A. Hedlund, Minimal coverings of pairs by triples, Pacific J. Math. 8 (1958), 709-719. MR 0103831 (21:2595)
  • 13. S. P. Ghosh, Consecutive storage of relevant records with redundancy, Commun. ACM 18 (1975), no. 8, 464-471. MR 0383863 (52:4743)
  • 14. J. W. Gilkerson and J. W. Jaromczyk, Restoring the order of images in a sequence of MRI slices, unpublished manuscript (2002).
  • 15. J. W. Gilkerson, J. W. Jaromczyk, and Z. Lonc, On constructing sequences of radius $ k$ using finite geometries, unpublished manuscript.
  • 16. F. Gray, Pulse code communication, 1953 (file 1947), US Patent 2,632,058.
  • 17. 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 (96m:05023)
  • 18. D. R. Hare, Cycles in the block-intersection graph of pairwise balanced designs, Discrete Math. 137 (1995), no. 1-3, 211-221. MR 1312454 (95m:05027)
  • 19. P. Horák, D. A. Pike, and M. E. Raines, Hamilton cycles in block-intersection graphs of triple systems, J. Combin. Des. 7 (1999), no. 4, 243-246. MR 1691408 (2000b:05026)
  • 20. P. Horák and A. Rosa, Decomposing Steiner triple systems into small configurations, Ars Combin. 26 (1988), 91-105. MR 982111 (90a:05029)
  • 21. G. Hurlbert, On universal cycles for $ k$-subsets of an $ n$-set, SIAM J. Discrete Math. 7 (1994), no. 4, 598-604. MR 1299088 (95k:05038)
  • 22. B. Jackson, Universal cycles of $ 4$-subsets and $ 5$-subsets, unpublished manuscript.
  • 23. B. W. Jackson, Universal cycles of $ k$-subsets and $ k$-permutations, Discrete Math. 117 (1993), no. 1-3, 141-150. MR 1226137 (94d:05002)
  • 24. J. W. Jaromczyk and Z. 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 (2006d:68048)
  • 25. H. Lenz, Some remarks on pairwise balanced designs, Mitt. Math. Sem. Giessen (1984), no. 165, 49-62. MR 745869 (86g:05015)
  • 26. F. Ruskey, Adjacent interchange generation of combinations, J. Algorithms 9 (1988), no. 2, 162-180. MR 936104 (89d:68066)
  • 27. C. Savage, A survey of combinatorial Gray codes, SIAM Rev. 39 (1997), no. 4, 605-629. MR 1491049 (98m:94052)
  • 28. S. Sen, S. Chatterjee, and N. Dumir, Towards a theory of cache-efficient algorithms, J. Assoc. Comput. Mach. 49 (2002), no. 6, 828-858. MR 2145858 (2005m:68271)
  • 29. L. Storme, Finite geometry, The CRC Handbook of Combinatorial Designs (C. J. Colbourn and J. H. Dinitz, eds.), Chapman & Hall, Boca Raton, FL, 2007, pp. 702-729. MR 2246267 (2007i:05001)
  • 30. R. M. Wilson, An existence theory for pairwise balanced designs. I. Composition theorems and morphisms, J. Combin. Theory Ser. A 13 (1972), 220-245. MR 0304203 (46:3338)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05B05, 05B07, 05B40, 05C38, 68R05

Retrieve articles in all journals with MSC (2010): 05B05, 05B07, 05B40, 05C38, 68R05

Additional Information

Yeow Meng Chee
Affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

San Ling
Affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Yin Tan
Affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Xiande Zhang
Affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Keywords: Alternating Hamiltonian cycle, block intersection graph, group divisible design, minimum covering, sequence of radius two, Steiner triple system, universal cycle
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.
Article copyright: © Copyright 2011 American Mathematical Society

American Mathematical Society