×

zbMATH — the first resource for mathematics

Union-free families of sets and equations over fields. (English) Zbl 0589.05013
A collection \({\mathcal F}\) of k-element subsets of an n-element set is said to be union-free if the sets \(F_ 1\cup F_ 2(F_ 1,F_ 2\in {\mathcal F})\) are all distinct. Let \(F_ k(n)\) denote the size of the largest union-free \({\mathcal F}\). It is shown that \(F_ k(n)\) lies between two positive multiples of \(n^{\lceil 4k/3\rceil}\). The proof of the lower bound involves the use of elementary symmetric polynomials. A similar result is obtained for weakly union-free collections, where, for any four distinct sets A,B,A’,B’\(\in {\mathcal F}\), \(A\cup B=A'\cup B'\) implies \(\{A,B\}=\{A',B'\}\). A recent paper of the authors [Discrete Math. 48, 205-212 (1984; Zbl 0553.05019)] relates the case \(k=3\) to Steiner triple systems.
Reviewer: I.Anderson

MSC:
05A99 Enumerative combinatorics
05A05 Permutations, words, matrices
11B99 Sequences and sets
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Erdős, P, On sequences of integers no one of which divides the product of two others and some related problems, Mitt. forsch. math. mech., 2, 74, (1938) · JFM 64.0988.02
[2] Erdős, P, Problems and results in combinatorial analysis, (), 3-12
[3] Erdős, P; Kleitman, D.J, On coloring graphs to maximize the proportion of multicolored k-edges, J. combin. theory, 5, 164-169, (1968) · Zbl 0167.22302
[4] Frankl, P; Füredi, Z, A new extremal property of Steiner triple-systems, Discr. math., 48, 205-212, (1984) · Zbl 0553.05019
[5] Füredi, Z, Graphs without quadrilaterals, J. combin. theory sec. B, 34, 187-190, (1983) · Zbl 0505.05038
[6] Hardy, G.H; Wright, E.M, (), 371, formula (22.19.2)
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.