Cross-intersecting families of labeled sets

2013 
For two positive integers $n$ and $p$, let $\mathcal{L}_{p}$ be the family of labeled $n$-sets given by $$\mathcal{L}_{p}=\big\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}: \ell_i\in[p], i=1,2\ldots,n\big\}.$$ 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}$.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    26
    References
    8
    Citations
    NaN
    KQI
    []