Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T21:36:15.221Z Has data issue: false hasContentIssue false
  • English
  • Français

On families of finite sets no two of which intersect in a singleton

Published online by Cambridge University Press:  17 April 2009

Peter Frankl
Peter Frankl*
Affiliation:
Magyar Tudományos Akadémia, Matematikai Kutató Intézete, Budapest, Hungary.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let X be a finite set of cardinality n, and let F be a family of k-subsets of X. In this paper we prove the following conjecture of P. Erdös and V.T. Sós.

If n > n0(k), k ≥ 4, then we can find two members F and G in F such that |F ∩ G| = 1.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 17 , Issue 1 , August 1977 , pp. 125 - 134
Copyright
Copyright © Australian Mathematical Society 1977

References

[1] Erdös, P., “A problem on independent r-tuples”, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95.Google Scholar
[2] Erdös, P., “Problems and results in graph theory and combinatorial analysis”, Proa. Fifth British Combinatorial Conference, 1975, 169–172 (University of Aberdeen, Aberdeen, 1975. Congressus Numerantium, 15. Utilitas Mathematica, Winnipeg, 1976).Google Scholar
[3] Erdös, P. and Rado, R., “Intersection theorems for systems of sets”, J. London Math. Soc. 35 (1960), 85–90.CrossRefGoogle Scholar
[4] Erdös, P., Ko, Chao, and Rado, R., “Intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. 12 (1961), 313–320.CrossRefGoogle Scholar
[5] Katona, Gyula (unpublished).Google Scholar