Some greedy \(t\)-intersecting families of finite sequences (Q1367107)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Some greedy \(t\)-intersecting families of finite sequences
scientific article

    Statements

    Some greedy \(t\)-intersecting families of finite sequences (English)
    0 references
    0 references
    0 references
    4 February 1998
    0 references
    Let \(S(k_1,\dots,k_n)= \{a=(a_1,\dots, a_n)\mid a_i\in\{0,\dots,k_i\}\) for all \(i\}\). The \(p\)-support of \(a\) is defined to be \(s_p(a)= \{i\in\{1,\dots,n\}\mid a_i\geq p\}\). If \(F\subseteq S(k_1,\dots,k_n)\) then let \(s_p(F)=\{s_p(a)\mid a\in F\}\). For \(A\subseteq\{1,\dots,n\}\) let \(w_p(A)= p^{n-|A|}\prod_{i\in A} (a_i-p)\). A subset \(F\) of \(S(k_1,\dots,k_n)\) is called \(I^p_t\)-intersecting if for all \(a,b\in F\) there are at least \(t\) indices \(i\) with \(a_i\geq p\) and \(b_i\geq p\). Moreover, \(F\) is called greedy (resp. proper greedy) \(I^p_t\)-intersecting if it is \(I^p_t\)-intersecting and \(w_p(A)\geq w_p(B\cup A^c)\) (resp. \(w_p(A)> w_p(B\cup A^c)\)) for all \(A\in s_p(F)\) and all \(B\subseteq A\) with \(|B|= t-1\) (\(A^c\) is the complement of \(A\) in \(\{1,\dots,n\}\)). The author determines the maximum size of proper greedy \(I^p_t\)-intersecting families and, in the case \(k_1> k_2>\cdots> k_n\geq 2p\), the maximum size of greedy \(I^p_t\)-intersecting families.
    0 references
    0 references
    chain product
    0 references
    intersecting family
    0 references
    Erdös-Ko-Rado theorem
    0 references
    greedy
    0 references
    0 references