Cross-intersecting families of labeled sets (Q1953396): Difference between revisions

Summary: For two positive integers \(n\) and \(p\), let \(\mathcal{L}_{p}\) be the family of labeled \(n\)-sets given by \[ \mathcal{L}_{p} = \left\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}: \ell_i\in[p], i=1,2\ldots,n\right\}. \] Families \(\mathcal{A}\) and \(\mathcal{B}\) are said to be cross-intersecting if \(A\cap B\neq\emptyset\) for all \(A\in \mathcal{A}\) and \(B\in\mathcal{B}\). In this paper, we will prove that for \(p\geq 4\), if \(\mathcal{A}\) and \(\mathcal{B}\) are cross-intersecting subfamilies of \(\mathcal{L}_{\mathfrak{p}}\), then \(|\mathcal{A}|\,|\mathcal{B}| \leq p^{2n-2}\), and equality holds if and only if \(\mathcal{A}\) and \(\mathcal{B}\) are an identical largest intersecting subfamily of \(\mathcal{L}_{p}\).