The Erdős-Ko-Rado bound for the function lattice (Q1302151)

From MaRDI portal





scientific article; zbMATH DE number 1340630
Language Label Description Also known as
English
The Erdős-Ko-Rado bound for the function lattice
scientific article; zbMATH DE number 1340630

    Statements

    The Erdős-Ko-Rado bound for the function lattice (English)
    0 references
    0 references
    18 May 2000
    0 references
    Let \(F^n_\alpha:= \{x= (x_1,\dots, x_n): x_i\in \{0,1,\dots, \alpha\}\) for all \(i\}\). A family \({\mathcal F}\subseteq F^n_\alpha\) is called \(k\)-uniform \(t\)-intersecting if \(|\{i: x_i\neq 0\}|= k\) for all \(x\in{\mathcal F}\) and if \(|\{i: x_i= y_i\neq 0\}|\geq t\) for all \(x,y\in{\mathcal F}\). The family \({\mathcal F}_0\) containing all \(n\)-tuples \(x\) with \(k\) nonzero components and with \(x_1=\cdots= x_t= \alpha\) is an example of such a family. Let \(M_\alpha(n,k,t)\) be the maximum size of a \(k\)-uniform \(t\)-intersecting family. From a more general result of \textit{R. Ahlswede} and \textit{L. H. Khachatrian} [The diametric theorem in Hamming space---optimal anticodes, Adv. Appl. Math. 20, No. 4, 429-449 (1998; Zbl 0909.05044)] it follows that \(M_\alpha(n, n,t)= |F_0|\) iff \(\alpha\geq t+1\). Here the author considers the case \(n>k\) and proves that \(M_\alpha(n,k,t)= |F_0|\) iff \(n\geq \lfloor(k- t+\alpha)(t+ 1)/\alpha\rfloor\).
    0 references
    Erdős-Ko-Rado bound
    0 references
    function lattice
    0 references
    intersecting family
    0 references
    Wilson bound
    0 references
    Ahlswede-Khachatrian theorem
    0 references
    0 references

    Identifiers