Improved Lower Bounds on the Compatibility of Quartets, Triplets, and Multi-state Characters

摘要

We study a long standing conjecture on the necessary and sufficient conditions for the compatibility of multi-state characters: There exists a function f(r) such that, for any set C of r-state characters, C is compatible if and only if every subset of f(r) characters of C is compatible. We show that for every r ≥ 2, there exists an incompatible set C of [r/2] ·[r/2] + 1 r-state characters such that every proper subset of C is compatible. Thus, f(r) ≥ [r/2] · [r/2] + 1 for every r ≥ 2. This improves the previous lower bound of f(r) > r given by Meacham (1983), and generalizes the construction showing that f(4) ≥ 5 given by Habib and To (2011). We prove our result via a result on quartet compatibility that may be of independent interest: For every integer n ≥4, there exists an incompatible set Q of [(n-2)/2] · [(n-2)/2] + 1 quartets over n labels such that every proper subset of Q is compatible. We contrast this with a result on the compatibility of triplets: For every n ≥ 3, if R is an incompatible set of more than n-1 triplets over n labels, then some proper subset of R is incompatible. We show this bound is tight by exhibiting, for every n ≥ 3, a set of n-1 triplets over n taxa such that R is incompatible, but every proper subset of R is compatible.