Abstract
Letf r(n, k) denote the maximum number ofk-subsets of ann-set satisfying the condition in the title. It is proved that
wheneverd=0, 1 ord≦r/2t 2 with equality holding iff there exists a Steiner systemS(t, r(t−1)+1,n−d). The determination off r(n, 2r) led us to a new generalization of BIBD (Definition 2.4). Exponential lower and upper bounds are obtained for the case if we do not put size restrictions on the members of the family.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Bollobás,On generalized graphs, Acta Math. Acad. Sci. Hungar.16 (1965), 447–452.
B. Bollobás, D. E. Daykin and P. Erdös,On the number of independent edges in a hypergraph, Quart. J. Math. Oxford (2)27 (1976), 25–32.
P. Erdös,A problem of independent r-tuples, Ann. Univ. Budapest8 (1965), 93–95.
P. Erdös, P. Frankl and Z. Füredi,Families of finite sets in which no set is covered by the union of two others, J. Comb. Theory, Ser. A33 (1982), 158–166.
P. Erdös and T. Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar.10 (1959), 337–356.
P. Erdös, C. Ko and R. Rado,An intersection theorem for finite sets, Quart. J. Math. Oxford (2)12 (1961), 313–320.
P. Erdös and E. Szemerédi,Combinatorial properties of a system of sets, J. Comb. Theory, Ser. A24 (1978), 308–311.
P. Frankl,On Sperner families satisfying an additional condition, J. Comb. Theory Ser. A20 (1976), 1–11.
P. Frankl,A general intersection theorem for finite sets, Ann. Discrete Math.8 (1980), 43–49.
V. Rödl,On a packing and covering problem, Eur. J. Combinatorics5 (1984).
J. Sperner,Ein Satz über Untermengen einer endlichen Menge, Math. Z.27 (1928), 544–548.
F. K. Hwang and V. T. Sós,Non-adaptive hypergeometric group testing, Studia Sci. Math. Hungar., to appear.
Author information
Authors and Affiliations
Additional information
This technical report is published as a result of an FCAC Foundation grant.
Rights and permissions
About this article
Cite this article
Erdös, P., Frankl, P. & Füredi, Z. Families of finite sets in which no set is covered by the union ofr others. Israel J. Math. 51, 79–89 (1985). https://doi.org/10.1007/BF02772959
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02772959