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 {S1, S2, ...} is called laminar if for every i, j, the intersection of Si and Sj is either empty, or equals Si, or equals Sj.
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 E1,...,Ek, then {E, E1,...,Ek} is laminar too; if we now partition e.g. E1 into E11, E12, ... E1j, 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]
References
[edit]- ^ Cheriyan, Joseph; Jordán, Tibor; Ravi, R. (1999). "On 2-Coverings and 2-Packings of Laminar Families". In Nešetřil, Jaroslav (ed.). Algorithms - ESA' 99. Lecture Notes in Computer Science. Vol. 1643. Berlin, Heidelberg: Springer. pp. 510–520. doi:10.1007/3-540-48481-7_44. ISBN 978-3-540-48481-3.
- ^ Maduel, Yael; Nutov, Zeev (2010-07-06). "Covering a laminar family by leaf to leaf links". Discrete Applied Mathematics. 158 (13): 1424–1432. doi:10.1016/j.dam.2010.04.002. ISSN 0166-218X.
- ^ Rautenbach, Dieter; Szigeti, Zoltán (2012-08-01). "Greedy colorings of words". Discrete Applied Mathematics. 160 (12): 1872–1874. doi:10.1016/j.dam.2012.03.038. ISSN 0166-218X.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |