On separating families of bipartitions

DOI10.1016/J.DISC.2012.10.015MaRDI QIDQ1928449zbMATH OpenOpenAlexFDO

Authors Takahisa Toda, Ivo Vigan

Publication date 3 January 2013

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1376

zbMATH Keywords

bipartitionenumerationseparating familiesset partitionStirling number

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18)

Abstract: In this paper, we focus on families of bipartitions, i.e. set partitions consisting of at most two components. We say that a family of bipartitions is a separating family for a set $S$ if every two elements in $S$ can be separated by some bipartition. Furthermore, we call a separating family minimal if no proper subfamily is a separating family. We characterize the set of all minimal separating families of maximum size for arbitrary set $S$ as the set of all spanning trees on $S$ and enumerate minimal separating families of maximum size. Furthermore, we enumerate separating families of arbitrary size, which need not be minimal.

Recommendations

• On separating convex points with lines
• On generalizations of separating and splitting families
• Separating Partition Systems and Locally Different Sequences
• Separation with restricted families of sets
• On splitting and splittable families

Cited in

(6)

• Bisecting and \(D\)-secting families for set systems
• A matrix description of weakly bipartitive and bipartitive families
• On separating convex points with lines
• On generalizations of separating and splitting families
• On a bipartition problem of Bollobás and Scott
• A note on data structures for maintaining bipartitions

This page was built for publication: On separating families of bipartitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1928449)