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

In memory of Paul Erdös

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[1], 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.

Get the LaTex | DVI | PS file of this abstract.