An intersection theorem for weighted sets (Q5937926)

From MaRDI portal
scientific article; zbMATH DE number 1621235
Language Label Description Also known as
English
An intersection theorem for weighted sets
scientific article; zbMATH DE number 1621235

    Statements

    An intersection theorem for weighted sets (English)
    0 references
    25 August 2002
    0 references
    A family \(\mathcal F\) of subsets of \([ n ]:=\{1, \dots, n\}\) is called intersecting in \([ m ]\) if \(F\cap G\cap [ m ]\neq\varnothing\) for all \(F, G \in \mathcal F\). A function \(\omega\) which assigns to every subset of \([ n ]\) a nonnegative number is said to be shift-monotone in \([ n ] \setminus [ m ]\) if \(\omega(\{a_1, \dots, a_j\})\geq \omega(\{b_1, \dots, b_j\})\) holds for all \(\{a_1, \dots, a_j\}, \{b_1, \ldots b_j\} \subseteq [ n ]\) with \(a_i\leq b_i\), \(i=1,\dots ,j\), \(j=1, \dots ,n\) and if \(\omega(A)\geq \omega(B)\) holds for all \(A,B\subseteq [ n ]\) with \(A\subseteq B\) and \(B\setminus A\subseteq \{m+1, \dots, n\}\). Let \(\omega (\mathcal F)=\sum_{F \in \mathcal F} \omega (F)\). Using methods of Ahlswede and Khachatrian the author proves that the following equality holds for families \(\mathcal F\) of subsets of \([ n ]\) provided that \(\omega\) is shift-monotone in \([ n ] \setminus [ m ]\): \[ \max\{\omega (\mathcal F)\mid \mathcal F \text{ is intersecting in }[ n ]\}= \max\{ \omega (\mathcal F)\mid \mathcal F \text{ is intersecting in }[ m ]\}. \] The result is applied to the poset of colored subsets of a finite set.
    0 references
    0 references
    0 references
    intersecting family
    0 references
    extremal set problem
    0 references
    weighted sets
    0 references
    generating sets
    0 references
    colored sets
    0 references