The intersection theorem for direct products (Q1272766)

From MaRDI portal
Revision as of 22:10, 17 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    Erdős-Ko-Rado theorem
    0 references
    complete intersection theorem
    0 references
    method of Ahlswede-Khachatrian
    0 references