Incompatible quartets, triplets, and 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-state characters such that every proper subset of C is compatible. This improves the previous lower bound of f(r)≥r given by Meacham (1983), and f(4)≥5 given by Habib and To (2011). For the case when r=3, Lam, Gusfield and Sridhar (2011) recently showed that f(3)=3. We give an independent proof of this result and completely characterize the sets of pairwise compatible 3-state characters by a single forbidden intersection pattern. Our lower bound on f(r) is proven via a result on quartet compatibility that may be of independent interest: For every n≥4, there exists an incompatible set Q of Ω(n(2)) quartets over n labels such that every proper subset of Q is compatible. We show that such a set of quartets can have size at most 3 when n=5, and at most O(n(3)) for arbitrary n. We contrast our results on quartets with the case of rooted 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.