The size of 3-compatible, weakly compatible split systems
A split system on a finite set X is a set of bipartitions of X. Weakly compatible and k-compatible (k?1) split systems are split systems which satisfy special restrictions on all subsets of a certain fixed size. They arise in various areas of applied mathematics such as phylogenetics and multi-commodity flow theory. In this note, we show that the number of splits in a 3-compatible, weakly compatible split system on a set X of size n is linear inn.
compatibility split systems phylogenetic combinatorics extremal combinatorics of finite sets weak compatibility 05d05 03e05 92b05