Intersection Properties of Systems of Finite Sets (Q4193465)

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 3632483
Language Label Description Also known as
default for all languages
No label defined
    English
    Intersection Properties of Systems of Finite Sets
    scientific article; zbMATH DE number 3632483

      Statements

      Intersection Properties of Systems of Finite Sets (English)
      0 references
      0 references
      0 references
      0 references
      1978
      0 references
      intersection properties
      0 references
      systems of finite sets
      0 references
      The authors use a theorem of Erdős-Rado [\textit{P.Erdős} and \textit{R.Rado}, J. London Math. Soc. 35, 85-90 (1960; Zbl 0103.27901)] to generalize theorems of Erdős-Ko-Rado [\textit{P.Erdős, Chao Ko} and \textit{R.Rado}, Quart. J. Math., Oxford II. Ser. 12, 313-320 (1961; Zbl 0100.01902)] , \textit{M.Deza} [J. Comb. Theory, Ser. B 16, 166-167 (1974; Zbl 0263.05007)] , \textit{A.Hajnal} and \textit{R. Rothschild} [J. Comb. Theory, Ser. B 15, 359-362 (1973; Zbl 0269.05003)] and \textit{A.J.W.Hilton} and \textit{E.C.Milner} [Theorem 2 in Quart. J. Math. Oxford II. Ser. 18, 369-384 (1967; Zbl 0168.26205)]. \(X\) is a finite set with \(|X| =n\), \(L=\{l_1,\dots,l_r\}\), \(l_1< \dots< l_r\) and \(K=\{k_1,\dots,k_s\}\), \(k_1< \dots k_s\) are sets of integers: an \((n,L,K)\)-system is a collection \({\mathcal A}\) of subsets of X such that for each \(A_1,A_2\in {\mathcal A}\), \(|A_1|\) ,\(|A_2|\in K\) and \(|A_1cap A_2|\in L\). Define \(K_i=K\cap\{l_i*1,\dots,L_{i+1}\}\), \(0\leq i\leq r\), where \(l_0=-1, L_{r+1}=k_s\), and \(k_1^*=min\{k| k\in K_i\}\). Theorem 7. (1) If \(|{\mathcal A}|> k_sc(k_s,L)\prod_{i=2}^r(n-l_i)/(k_i^*-l_i)\) then there exists a set D such that \(|D|=l_1\) and \(D\subseteq A\) for every \(A\in {\mathcal A} \). (ii) If \(|{\mathcal A}|> k_s^32^{r-1}n^{r-1}\) then there exists a \(k\in K_r\) such that \(l_i-l_{i-1}\) divides \(l_{i+1}-l_i\), \(2\leq i\leq r\), \(l_{r+1}=k\). (iii) \(|{\mathcal A}|\leq\sum_{i=0}^r\varepsilon_1\prod(n-l_j)/(k_i^*-l_j)\) where \(\varepsilon=0\text{or}1\) according as \(K_i=\emptyset\) or not, and the product is taken over those j, \(1\leq j\leq r\) for which \(l_j< k_i^*\). Theorem 8. If \(K=\{k\}\) and for a fixed \(q\geq 1\) we can find, among any \(A_1,\dots,A_{q+1}\in{\mathcal A}\), two of them \(A_1,A_j\) such that \(|A_i\cap A_j|\in L\), then there is a constant \(c=c(k,q)\) such that if \(|{\mathcal A}|> (q-1)\prod_{i=1}^r(n-l_i)/(k-l_i)+cn^{r-1}\) then there are sets \(D_1,\dots,D_s\), each of cardinality \(l_1\), such that for every \(A\in{\mathcal A}\) there is an \(i\) for which \(D_i\subset A\). Further, if \(q_i\) is the maximum number of sets \(A_j\), \(1\leq j\leq q_i\), such that \(D_i\subset A_j\), but for \(h\neq i\), \(D_n\not\subset A_j\) and \(|A_{j_1}\cap A_{j_2}|\notin L\) for \(1\leq j_1< j_2\leq q_1\), then \(\sum_{i=1}^sq_i=q\). Also, for \(n> n_0(k,q)\), \(|{\mathcal A}|\leqq\prod_{i=1}^r(n-l_i)/(k-l_i)+0(n^{r-1})\). Theorem 9. If, for any t different members of \({\mathcal A}\), \( > |A_1\cap\dots\cap A_t|\in L\), then there is a constant \(c=c(k,t)\) such that if \(|{\mathcal A}|> cn^{r-1}\), then there is a set D, \(|D|=l_1\), \(D\subset A\) for every \(A\in{\mathcal A}\), and \(l_i-l_{i-1}\) divides \(l_{i+1}-l_i\), \(2\leq i\leq r\). Also, for \(n> n_0(k,t)\), \(|{\mathcal A}|\leq(t-1)\prod_{i=1}^r(n-l_i)/(k-l_i)\). The authors ask if it is true that \(L'\subset L\) implies the existence, for large enough \(n\), of \((n,L,k)\)- and \((n,L',k)\)-systems \({\mathcal A}\) and \({\mathcal A}'\), each of maximum cardinaly with \({\mathcal A}'\subseteq{\mathcal A}\). They note that Theorem 7 and 9 may be simultaneously generalized to the families called quasi-block-designs by \textit{Vera T. Sós} [Colloq. int. Teorie comb., Roma 1973, Tomo II, 223-233 (1976; Zbl 0261.05022)].
      0 references

      Identifiers