×

Partitions of \(k\)-branching trees and the reaping number of Boolean algebras. (English) Zbl 0783.06009

Summary: The reaping number \({\mathfrak r}_{m,n}(\mathbb{B})\) of a Boolean algebra \(\mathbb{B}\) is defined as the minimum size of a subset \({\mathcal A}\subseteq\mathbb{B}\backslash\{0\}\) such that for each \(m\)-partition \(\mathcal P\) of unity, some member of \(\mathcal A\) meets less than \(n\) elements of \(\mathcal P\). We show that for each \(\mathbb{B}\), \({\mathfrak r}_{m,n}(\mathbb{B})={\mathfrak r}_{\lceil{m\over n-1}\rceil,2}(\mathbb{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 ae coloured with \(\ell\) colours contains an \(m\)-branching subtree using at most \(n\) colours if and only if \(\Bigl\lceil{\ell\over n}\Bigr\rceil<\Bigl\lceil{k\over m-1}\Bigr\rceil\).

MSC:

06E10 Chain conditions, complete algebras
05C05 Trees
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: EuDML