Skip to main content
SpringerLink
Log in

Families of finite sets in which no set is covered by the union ofr others

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

Letf r(n, k) denote the maximum number ofk-subsets of ann-set satisfying the condition in the title. It is proved that

$$f_1 (n,r(t - 1) + 1 + d)\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \leqslant } (_{ t}^{n - d} )/(_{ t}^{k - d} )$$

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. B. Bollobás,On generalized graphs, Acta Math. Acad. Sci. Hungar.16 (1965), 447–452.

    Article  MATH  MathSciNet  Google Scholar 

  2. 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.

    Article  MATH  Google Scholar 

  3. P. Erdös,A problem of independent r-tuples, Ann. Univ. Budapest8 (1965), 93–95.

    MATH  Google Scholar 

  4. 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.

    Article  MATH  Google Scholar 

  5. P. Erdös and T. Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar.10 (1959), 337–356.

    Article  MATH  MathSciNet  Google Scholar 

  6. P. Erdös, C. Ko and R. Rado,An intersection theorem for finite sets, Quart. J. Math. Oxford (2)12 (1961), 313–320.

    Article  MATH  Google Scholar 

  7. P. Erdös and E. Szemerédi,Combinatorial properties of a system of sets, J. Comb. Theory, Ser. A24 (1978), 308–311.

    Article  MATH  Google Scholar 

  8. P. Frankl,On Sperner families satisfying an additional condition, J. Comb. Theory Ser. A20 (1976), 1–11.

    Article  MATH  MathSciNet  Google Scholar 

  9. P. Frankl,A general intersection theorem for finite sets, Ann. Discrete Math.8 (1980), 43–49.

    Article  MathSciNet  Google Scholar 

  10. V. Rödl,On a packing and covering problem, Eur. J. Combinatorics5 (1984).

  11. J. Sperner,Ein Satz über Untermengen einer endlichen Menge, Math. Z.27 (1928), 544–548.

    Article  MathSciNet  MATH  Google Scholar 

  12. F. K. Hwang and V. T. Sós,Non-adaptive hypergeometric group testing, Studia Sci. Math. Hungar., to appear.

Download references

Author information

Authors and Affiliations

  1. Mathematical Institute of the Hungarian Academy of Science, 1364 Budapest, P.O.B. 127, Hungary

    P. Erdös & Z. Füredi

  2. CNRS, 15 Quai A. France, 75007, Paris, France

    P. Frankl

Authors
  1. P. Erdös
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Frankl
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Z. Füredi
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This technical report is published as a result of an FCAC Foundation grant.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02772959

Keywords

Search

Navigation