Cross-intersecting families of labeled sets

Huajun Zhang¹

¹Zhejiang Normal University

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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}$.

Détail

DOI : 10.37236/3047

Classification : 05D05, 06A07
Mots-clés : EKR theorem, intersecting family, cross-intersecting family, labeled set