In
combinatorics, a laminar set family is a
set family
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set f ...
in which each pair of sets are either
disjoint or related by containment.
Formally, a set family is called laminar if for every ''i'', ''j'', the intersection of ''S
i'' and ''S
j'' is either empty, or equals ''S
i'', or equals ''S
j''.
Let ''E'' be a ground-set of elements. A laminar set-family on ''E'' can be constructed by recursively
partitioning ''E'' into parts and sub-parts. In particular, the
singleton
Singleton may refer to:
Sciences, technology Mathematics
* Singleton (mathematics), a set with exactly one element
* Singleton field, used in conformal field theory Computing
* Singleton pattern, a design pattern that allows only one instance ...
family is laminar; if we partition ''E'' into some ''k'' pairwise-disjoint parts ''E''
1,...,''E
k'', then is laminar too; if we now partition e.g. ''E''
1 into ''E''
11, ''E''
12, ''... E''
1j, then adding these sub-parts yields another laminar family; etc. Hence, a laminar set-family can be seen as a partitioning of the ground-set into categories and sub-categories.
References
Families of sets
{{Combin-stub