Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2017; 54(3): 875-894

Online first article January 9, 2017      Printed May 31, 2017

https://doi.org/10.4134/BKMS.b160334

Copyright © The Korean Mathematical Society.

An Erd{\H o}s-Ko-Rado theorem for minimal covers

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