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

$\lfloor\frac{r}{2}\rfloor\cdot\lceil\frac{r}{2}\rceil + 1$

r

-state characters such that every proper subset of

C

is compatible. Thus,

$f(r) \ge \lfloor\frac{r}{2}\rfloor\cdot\lceil\frac{r}{2}\rceil + 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

$\lfloor\frac{n-2}{2}\rfloor\cdot\lceil\frac{n-2}{2}\rceil + 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.