An Erd{\H o}s-Ko-Rado theorem for minimal covers
Bull. Korean Math. Soc. 2017 Vol. 54, No. 3, 875-894
https://doi.org/10.4134/BKMS.b160334
Published online May 31, 2017
Cheng Yeaw Ku and Kok Bin Wong
National University of Singapore, University of Malaya
Abstract : Let $[n]=\{1,2,\dots, n\}$. A set $\mathbf A=\{A_1,A_2,\dots ,A_l\}$ is a minimal cover of $[n]$ if $\bigcup_{1\leq i\leq l} A_i =[n]$ and \[ \bigcup_{\substack{1\leq i\leq l,\\ i\neq j_0}} A_i \neq [n] \quad\textnormal{for all $j_0\in [l]$}. \] Let $\mathcal{C}(n)$ denote the collection of all minimal covers of $[n]$, and write $C_{n} = \vert \mathcal{C}(n)\vert$. Let $\mathbf A \in \mathcal{C}(n)$. An element $u \in [n]$ is critical in $\mathbf A$ if it appears exactly once in $\mathbf A$. Two minimal covers $\mathbf A$, $\mathbf B \in \mathcal{C}(n)$ are said to be restricted $t$-intersecting if they share at least $t$ sets each containing an element which is critical in both $\mathbf A$ and $\mathbf B$. A family $\A \subseteq \mathcal{C}(n)$ is said to be restricted $t$-intersecting if every pair of distinct elements in $\A$ are restricted $t$-intersecting. In this paper, we prove that there exists a constant $n_{0}=n_{0}(t)$ depending on $t$, such that for all $n \ge n_{0}$, if $\A \subseteq \mathcal{C}(n)$ is restricted $t$-intersecting, then $|\A| \le C_{n-t}$. Moreover, the bound is attained if and only if $\A$ is isomorphic to the family $\mathcal{D}_{0}(t)$ consisting of all minimal covers which contain the singleton parts $\{1\}$, $\ldots$, $\{t\}$. A similar result also holds for restricted $r$-cross intersecting families of minimal covers.
Keywords : $t$-intersecting family, Erd{\H o}s-Ko-Rado, set partitions
MSC numbers : 05D05
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd