Metraipolis › archive › dc_bb1d7835cfe4
NOC NOC, who's there? Clustering systems of tree-child and normal networks — arXiv:2609.13336
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.13336
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T01:25:41.241Z
- SHA-256 of the archived text
5ad93bcb35e996a6b414839538e4cd1a1d371f834a26aca527ff4264da221994- Stable URL of this page
https://metraipolis.com/documento/dc_bb1d7835cfe4
How to cite
NOC NOC, who's there? Clustering systems of tree-child and normal networks — arXiv:2609.13336 — arXiv (en), https://arxiv.org/abs/2609.13336 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bb1d7835cfe4 (Metraipolis archive dc_bb1d7835cfe4, sha256 5ad93bcb35e996a6b414839538e4cd1a1d371f834a26aca527ff4264da221994)
BibTeX
@misc{dcbb1d7835cfe4,
title = {NOC NOC, who's there? Clustering systems of tree-child and normal networks — arXiv:2609.13336},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.13336},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bb1d7835cfe4; sha256 5ad93bcb35e996a6b414839538e4cd1a1d371f834a26aca527ff4264da221994},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.13336. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Clustering systems provide a natural way to encode structural information contained in phylogenetic networks. In this note, we study the clustering systems of normal and tree-child networks through an overlap-based property of set systems, called not-overlap-covered (NOC). We show that the NOC property is equivalent to inclusion-visibility, a memberwise formulation of the strict-compatibility condition previously used for tree-child clustering systems. We characterize normal networks as precisely the semi-regular networks whose clustering systems satisfy NOC. Consequently, a clustering system is realized by a normal network if and only if it satisfies NOC, or equivalently, if every one of its clusters is inclusion-visible. In this case, the Hasse diagram provides a canonical normal realization. These are exactly the clustering systems realized by tree-child networks. The NOC formulation yields a sharp quadratic upper bound on the number of distinct clusters of tree-child and normal networks and a direct polynomial-time recognition algorithm. Finally, we explore several consequences of the NOC perspective beyond the phylogenetic setting. These include connections to the enumeration of normal networks, an order-theoretic interpretation of inclusion-visibility, structural properties of NOC set systems, and a tractable special case of Minimum Set Cover, which is NP-hard in general. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.CO). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO); Populations and Evolution (q-bio.PE). Pagina del lavoro: https://arxiv.org/abs/2609.13336 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T00:39:30.268Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).