On A Combinatorial Problem III (Q5597541)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3317771
Language Label Description Also known as
default for all languages
No label defined
    English
    On A Combinatorial Problem III
    scientific article; zbMATH DE number 3317771

      Statements

      On A Combinatorial Problem III (English)
      0 references
      1969
      0 references
      combinatorics
      0 references
      0 references
      [Part I in Nordisk. Mat. Tidskr. 11, 5--10 (1963; Zbl 0116.01104)] \textit{E. W. Miller}, in C. R. Soc. Sci. Varsovie 30, 31--38 (1937; Zbl 0017.30003), defines a family of sets \(\{A\}\) to have property \(B\) if there exists a set \(S\) which meets all the sets \(A_k\) and contains none of them. The author and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 12, 87--123 (1961; Zbl 0201.32801)] define \(m(n)\) as the smallest integer for which there is a family of \(m(n)\) sets, each with cardinality \(n\), which do not have property B. In Part II [ibid. 15, 445--447 (1964; Zbl 0201.33704)], the author had found bounds for \(m(n)\). In this paper he considers the function \(m_N(n)\) which is the smallest integer for which there are \(m_N(n)\) sets \(A_k\) each with cardinality \(n\) which are all subsets of a set \(S\), \(|S| = N\), and which do not have property \(B\). It is shown that if \(N=(c+o(1))n\) then \[ \lim_{n \to \infty} m_N (n)^{1/n} = 2(c-2)^{(c-2)/2}(c-1)^{(1-c)}c^{c/2},\text{ if } c > 2 \text{ and } =4 \text{ if } c=2. \] To prove this, upper and lower bounds for \(m_N(n)\) are found, differing by only \(2N\). The author suggests that for large values of \(N\) the more appropriate function to consider would be \(m_N(n)\) being the smallest integer for which there is a family of sets not having property \(B\), satisfying \(A_k \subset S\), \(|S| = N\) with the restriction that the set of \(A_k\)'s contained in any proper subset of \(S\) has the property \(B\). Asymptotic formulae for \(m_N(n)\) and \(m_N'(n)\) are not known.
      0 references

      Identifiers