Maximum Hitting of a Set by Compressed Intersecting Families
Maximum Hitting of a Set by Compressed Intersecting Families
复制标题
压缩相交族对集合的最大命中
DOI：
10.1007/s00373-010-1001-2
复制
发表时间：
2011
影响因子：
0.7
通讯作者：
P. Borg
中科院分区：
文献类型：
--
作者：
P. Borg
For a family $${\mathcal{A}}$$ and a set Z, denote $${\{A \in \mathcal{A} \colon A \cap Z \neq \emptyset\}}$$ by $${\mathcal{A}(Z)}$$. For positive integers n and r, let $${\mathcal{S}_{n,r}}$$ be the trivial compressed intersecting family$${\{A \in \big(\begin{subarray}{c}[n]\\r \end{subarray}\big) \colon 1 \in A\}}$$, where $${[n] := \{1, \ldots, n\}}$$ and $${\big(\begin{subarray}{c}[n]\\r \end{subarray}\big) := \{A \subset [n] \colon |A| = r\}}$$. The following problem is considered: For r ≤ n/2, which sets $${Z \subseteq [n]}$$ have the property that $${|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|}$$ for any compressed intersecting family $${\mathcal{A}\subset \big(\begin{subarray}{c}[n]\\r \end{subarray}\big)}$$? (The answer for the case $${1 \in Z}$$ is given by the Erdős–Ko–Rado Theorem.) We give a complete answer for the case |Z| ≥ r and a partial answer for the much harder case |Z| < r. This paper is motivated by the observation that certain interesting results in extremal set theory can be proved by answering the question above for particular sets Z. Using our result for the special case when Z is the r-segment $${\{2, \ldots, r+1\}}$$, we obtain new short proofs of two well-known Hilton–Milner theorems. At the other extreme end, by establishing that $${|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|}$$ when Z is a final segment, we provide a new short proof of a Holroyd–Talbot extension of the Erdős-Ko-Rado Theorem.
For a family $${\mathcal{A}}$$ and a set Z, denote $${\{A \in \mathcal{A} \colon A \cap Z \neq \emptyset\}}$$ by $${\mathcal{A}(Z)}$$. For positive integers n and r, let $${\mathcal{S}_{n,r}}$$ be the trivial compressed intersecting family$${\{A \in \big(\begin{subarray}{c}[n]\\r \end{subarray}\big) \colon 1 \in A\}}$$, where $${[n] := \{1, \ldots, n\}}$$ and $${\big(\begin{subarray}{c}[n]\\r \end{subarray}\big) := \{A \subset [n] \colon |A| = r\}}$$. The following problem is considered: For r ≤ n/2, which sets $${Z \subseteq [n]}$$ have the property that $${|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|}$$ for any compressed intersecting family $${\mathcal{A}\subset \big(\begin{subarray}{c}[n]\\r \end{subarray}\big)}$$? (The answer for the case $${1 \in Z}$$ is given by the Erdős–Ko–Rado Theorem.) We give a complete answer for the case |Z| ≥ r and a partial answer for the much harder case |Z| < r. This paper is motivated by the observation that certain interesting results in extremal set theory can be proved by answering the question above for particular sets Z. Using our result for the special case when Z is the r-segment $${\{2, \ldots, r+1\}}$$, we obtain new short proofs of two well-known Hilton–Milner theorems. At the other extreme end, by establishing that $${|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|}$$ when Z is a final segment, we provide a new short proof of a Holroyd–Talbot extension of the Erdős-Ko-Rado Theorem.