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
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