Annals of Combinatorics 1 (1997) 215-225
Weakly Union-free Twofold Triple Systems
Yeow Meng Chee, Charles J. Colbourn, and Alan C.H. Ling
Department of Computer Science, University of Waterloo,
Waterloo, Ontario, Canada N2L 3G1
Department of Computer Science and Electrical Engineering, University of Vermont Burlington, VT 05405, USA
Department of Mathematics and Statistics, University of Vermont, Burlington, VT 05405, USA
Received February 2, 1997
AMS Subject Classification: 05D05, 05C65, 05B07
Abstract. In this paper, we settle a problem of Frankl and Füredi, which is a special case of a problem of Erdös, determining the maximum number of hyperedges in a 3-uniform hypergraph in which no two pairs of distinct hyperedges have the same union. The extremal case corresponds to the existence of weakly union-free twofold triple systems, which is settled here with six definite and four possible exceptions. An application to group testing is also given.
Keywords: union-free hypergraph, twofold triple system, group testing
1. R.J.R. Abel, A.E. Brouwer, C.J. Colbourn, and J.H. Dinitz, Mutually orthogonal Latin squares, In: CRC Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz, Eds., CRC Press, Boca Raton FL, 1996, pp. 111–142.
2. T. Berger, N. Mehravari, D. Towsley, and J. Wolf, Random multiple-access communications and group testing, IEEE Trans. Commun. 32 (1984) 769–778.
3. T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Cambridge University Press, 1986.
4. W.J. Bruno, D.J. Balding, E.H. Knill, D. Bruce, C. Whittaker, N. Doggett, R. Stallings, and D.C. Torney, Design of efficient pooling experiments, Genomics 26 (1995) 21–30.
5. C.J. Colbourn, M.J. Colbourn, J.J. Harms, and A. Rosa, A complete census of (10,3,2) block designs and of Mendelsohn triple systems of order ten. III. (10,3,2) block designs without repeated blocks, In: Proceedings of the Twelfth Manitoba Conference on Numerical Mathematics and Computing, 1982, pp. 211–234.
6. C.J. Colbourn and P.B. Gibbons, Uniform orthogonal group divisible designs with block size three, New Zealand J. Math., to appear.
7. C.J. Colbourn, P.B. Gibbons, R.A. Mathon, R.C. Mullin, and A. Rosa, The spectrum of orthogonal Steiner triple systems, Canadian J. Math. 46 (1994) 239–252.
8. D.-Z. Du and F.K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, Singapore, 1993.
9. P. Erdös, On sequences of integers no one of which divides the product of two others and some related results, Mitt. Forschungsint. Math. Mech. 2 (1938) 74–82.
10. P. Erdös, Problems and results in combinatorial analysis, Congressus Numer. 19 (1977) 3–12.
11. P. Frankl and Z. Füredi, A new extremal property of Steiner triple systems, Discrete Math. 48 (1984) 205–212.
12. H.D.O.F. Gronau and R.C. Mullin, PBDs: recursive constructions, In: CRC Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz, Eds., CRC, 1996, pp. 193–203.
13. F.K. Hwang and V.T. Sòs, Non-adaptive hypergeometric group testing, Studia Sci. Math. Hungar. 22 (1987) 257–263.
14. E. Knill and S. Muthukrishnan, Group testing problems in experimental molecular biology (preliminary report), Los Alamos Combinatorics E-print Server\footnotemark, LACES-94B-95-26, 1995.
15. R.M. Wilson, An existence theory for pairwise balanced designs I: composition theorems and morphisms, J. Combin. Theory Ser. A 13 (1971) 220–245.