The intersection theorem for direct products (Q1272766)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The intersection theorem for direct products
scientific article

    Statements

    The intersection theorem for direct products (English)
    0 references
    0 references
    0 references
    0 references
    23 April 1999
    0 references
    Let \(n=n_1+\cdots+n_m,\) \(k=k_1+\cdots+k_m\) (every item an integer) and let \(X_1,\dots,X_m\) pairwise disjoint sets with \(n_i\) elements, resp. Denote \(\mathcal H\) the set of those subsets of \(X\) which intersect \(X_i\) in \(k_i\) elements, resp. Finally let \(1\leq t_i \leq k_i\) for each \(i=1,\dots,m.\) A subset \({\mathcal A}\) of \({\mathcal H}\) is \((t_1,\dots,t_m)\)-intersecting if for every pair \(A,B \in {\mathcal A}\) there exists \(i\in \{1,\dots,m\}\) such that \(| A \cap B \cap X_i| \geq t_i.\) What can be the largest cardinality of an \((t_1,\dots,t_m)\)-intersecting subset? The problem for \(t_i=1\) was solved by P. Frankl. This paper solves the general case. The proof is based on the powerful method of Ahlswede and Khachatrian applied to the complete intersection theorem.
    0 references
    Erdős-Ko-Rado theorem
    0 references
    complete intersection theorem
    0 references
    method of Ahlswede-Khachatrian
    0 references

    Identifiers