Partitions of $k$-branching trees and the reaping number of Boolean algebras

Laflamme, Claude

Commentationes Mathematicae Universitatis Carolinae, Tome 34 (1993) no. 2, pp. 397-399.

Résumé

The reaping number $\frak r_{m,n}({\Bbb B})$ of a Boolean algebra ${\Bbb B}$ is defined as the minimum size of a subset ${\Cal A} \subseteq {\Bbb B}\setminus \{{\bold O}\}$ such that for each $m$-partition $\Cal P$ of unity, some member of $\Cal A$ meets less than $n$ elements of $\Cal P$. We show that for each ${\Bbb B}$, $\frak r_{m,n}(\Bbb B) = \frak r_{\lceil \frac{m}{n-1} \rceil,2}(\Bbb B)$ as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every $k$-branching tree whose maximal nodes are coloured with $\ell$ colours contains an $m$-branching subtree using at most $n$ colours if and only if $\lceil \frac{\ell}{n} \rceil \lceil \frac{k}{m-1} \rceil$.

Détail

Classification : 05C05, 05C15, 05C90, 06E05, 06E10
Keywords: Boolean algebra; reaping number; partition