On cross-intersecting uniform sub-families of hereditary families

Peter Borg

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

A family $\mathcal{H}$ of sets is hereditary if any subset of any set in $\mathcal{H}$ is in $\mathcal{H}$. If two families $\mathcal{A}$ and $\mathcal{B}$ are such that any set in $\mathcal{A}$ intersects any set in $\mathcal{B}$, then we say that $(\mathcal{A}, \mathcal{B})$ is a cross-intersection pair (cip). We say that a cip $(\mathcal{A}, \mathcal{B})$ is simple if at least one of $\mathcal{A}$ and $\mathcal{B}$ contains only one set. For a family $\mathcal{F}$, let $\mu(\mathcal{F})$ denote the size of a smallest set in $\mathcal{F}$ that is not a subset of any other set in $\mathcal{F}$. For any positive integer $r$, let $[r] := \{1, 2, ..., r\}$, $2^{[r]} := \{A \colon A \subseteq [r]\}$, $\mathcal{F}^{(r)} := \{F \in \mathcal{F} \colon |F| = r\}$. We show that if a hereditary family $\mathcal{H} \subseteq 2^{[n]}$ is compressed, $\mu(\mathcal{H}) \geq r+s$ with $r \leq s$, and $(\mathcal{A}, \mathcal{B})$ is a cip with $\emptyset \neq \mathcal{A} \subset \mathcal{H}^{(r)}$ and $\emptyset \neq \mathcal{B} \subset \mathcal{H}^{(s)}$, then $|\mathcal{A}| + |\mathcal{B}|$ is a maximum if $(\mathcal{A}, \mathcal{B})$ is the simple cip $\left( \{[r]\}, \{B \in \mathcal{H}^{(s)} \colon B \cap [r] \neq \emptyset\} \right)$; Frankl and Tokushige proved this for $\mathcal{H} = 2^{[n]}$. We also show that for any $2 \leq r \leq s$ and $m \geq r + s$ there exist (non-compressed) hereditary families $\mathcal{H}$ with $\mu(\mathcal{H}) = m$ such that no cip $(\mathcal{A}, \mathcal{B})$ with a maximum value of $|\mathcal{A}| + |\mathcal{B}|$ under the condition that $\emptyset \neq \mathcal{A} \subset \mathcal{H}^{(r)}$ and $\emptyset \neq \mathcal{B} \subset \mathcal{H}^{(s)}$ is simple (we prove that this is not the case for $r=1$), and we suggest two conjectures about the extremal structures in general.

Détail

DOI : 10.37236/332

Classification : 05D05