×

zbMATH — the first resource for mathematics

A new extremal property of Steiner triple-systems. (English) Zbl 0553.05019
A family \({\mathcal F}\) of 3-subsets of an n-element set is union-free if, for any 4 subsets F,G,F’,G’\(\in {\mathcal F}\), \(F\cup G=F'\cup G'\) implies that \(\{F,G\}=\{F',G'\}.\) \({\mathcal F}\) is weakly union-free if, for any 4 distinct subsets F,G,F’,G’\(\in {\mathcal F}\), \(F\cup G\neq F'\cup G'.\) Denote by \(f_ 3(n)\) (respectively \(F_ 3(n))\) the maximum number of sets in a union-free (respectively weakly union-free) family. Theorem 1.4: \(f_ 3(n)=[n(n-1)/6].\) (If \(n\equiv 1\) or \(n\equiv 3\) (mod 6), \(n\geq 7\), Steiner triple systems realize the equality of Theorem 1.4; other examples exist.) Theorem 1.6: \(F_ 3(n)\leq n(n-1)/3,\) and any family for which equality holds is a Steiner triple system. Moreover, if \(n\equiv 1\) (mod 6), then equality holds for n sufficiently large. Corollary to Theorem 1.6: For n sufficiently large, \(n(n-1)/3-(10/3)n<F_ 3(n)\leq [n(n-1)/3].\)
Reviewer: W.G.Brown

MSC:
05B07 Triple systems
05A05 Permutations, words, matrices
03E05 Other combinatorial set theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Blanchard, (), 538
[2] Brown, W.G, On graphs that do not contain a thomsen graph, Bull. canad. math. soc., 9, 281-288, (1966) · Zbl 0178.27302
[3] Erdös, P, On sequences of integers no one of which divides the product of two others and some related prolems, Mitt. forschungsinst. math. und mech., 2, 74-82, (1938)
[4] Erdös, P, Problems and results in combinatorial analysis, (), 3-17
[5] Erdös, P, Problems and results in combinatorial analysis, (), 3-12
[6] Erdös, P; Simonovits, M, Compactness results in extremal graph theory, Combinatorica, 2, 275-288, (1982) · Zbl 0508.05043
[7] Erdös, P; Rényi, A; Sós, V.T, On a problem in graph theory, Studia sci. math. hungar., 1, 215-235, (1966) · Zbl 0144.23302
[8] Füredi, Z, Graphs without quadrilaterals, J. combin. theory (B), 34, 187-190, (1983) · Zbl 0505.05038
[9] Hanani, H, The existence and construction of balanced incomplete block designs, Ann. math. statist., 32, 361-386, (1961) · Zbl 0107.36102
[10] Hanani, H, On resolvable balanced incomplete block designs, J. combin. theory (A), 17, 275-289, (1974) · Zbl 0305.05010
[11] Ray-Chaudhuri, D.K; Wilson, R.M, Solution of Kirkman’s schoolgirl problem, (), 187-203 · Zbl 0248.05009
[12] Reiman, I, Über ein problem von zarankiewicz, Acta math. acad. sci. hungar., 9, 269-278, (1958) · Zbl 0084.01303
[13] Wilson, R.M; Wilson, R.M, An existence theory for pairwise balanced designs I-III, J. combin. theory (A), J. combin. theory (A), 18, 71-79, (1973) · Zbl 0295.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.