EKR type inequalities for 4-wise intersecting families (Q880003)

From MaRDI portal
scientific article
Language Label Description Also known as
English
EKR type inequalities for 4-wise intersecting families
scientific article

    Statements

    EKR type inequalities for 4-wise intersecting families (English)
    0 references
    0 references
    10 May 2007
    0 references
    A family \(\mathcal{F}\subseteq 2^{[n]}\) is called \(r\)-wise \(t\)-intersecting if \(| F_1\cap \cdots\cap F_r| \geq t\) holds for all \(F_1,\dots,F_r\in\mathcal{F}\). Let \(\mathcal{F}_i(n,k,r,t)\) be the following \(r\)-wise \(t\)-intersecting family: \[ \mathcal{F}_i(n,k,r,t)=\bigg{\{}F\in \binom{[n]}{k}:\big{| }F\cap [t+ri]\big{| } \geq t+(r-1)i\bigg{\}}. \] Let \(m(n,k,r,t)\) be the maximal size of \(k\)-uniform \(r\)-wise \(t\)-intersecting families on \(n\) vertices. The main result of the paper is the following: Let \(t\) be an integer with \(1\leq t\leq 7\). Then there exist \(\varepsilon >0\) and \(n_0\) (depending on \(\varepsilon\)) such that \(m(n,k,4,t)=\binom{n-t}{k-t}\) holds for \(\big{| }\frac{k}{n}-\frac{1}{2}\big{| }< \varepsilon\) and \(n>n_0\). Moreover, \(\mathcal{F}_0(n,k,4,t)\) is the only optimal configuration (up to isomorphism).
    0 references
    intersecting family
    0 references
    Erdős-Ko-Rado theorem
    0 references
    random walk
    0 references

    Identifiers