Laminar set family

In combinatorics, a laminar set family is a set family in which each pair of sets are either disjoint or related by containment.^[1][2] Formally, a set family {S₁, S₂, ...} 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.

All hyperedges here are either disjoint or related by containment. Edge 1 contains edge 4, and edges 3 and 5 contain each other. The set of hyperedges therefore forms a laminar set family.

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 family {E} is laminar; if we partition E into some k pairwise-disjoint parts E₁,...,E_k, then {E, E₁,...,E_k} is laminar too; if we now partition e.g. E₁ into E₁₁, E₁₂, ... 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.

The same notion can be applied to hypergraphs to define "laminar hypergraphs" as those whose set of hyperedges forms a laminar set family.^[3]