Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-08T06:33:34.784Z Has data issue: false hasContentIssue false

On a Combinatorial Problem of Erdös and Hajnal

Published online by Cambridge University Press:  20 November 2018

H. L. Abbott
Affiliation:
University of Alberta, Edmonton
L. Moser
Affiliation:
University of Alberta, Edmonton
Rights & Permissions [Opens in a new window]

Extract

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.

In this note we consider some problems related to the following question: What is the smallest integer m(n) for which there exists a family Fn of sets A1, A2,…, Am(n) with the following properties, (i) each member of Fn has n elements and (ii) if S is a set which meets each member of Fn, then S contains at least one member of Fn?

Erdős and Hajnal [1] observed that

and that m(l) = 1, m(2) = 3, m(3) = 7.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1964

References

1. Erdös, P. and Hajnai, A., On a property of families of sets, Acta. Math. Acad. Hung. Sci. 12(1961) pp.87123.Google Scholar
2. Erdös, P., On a combinatorial problem, Nordisk Mat. Tidski. 2 (1963) pp.510.Google Scholar