Consistent character table

A character table is consistent if there exists a binary tree $T$ whose splits does not conflict with the characters encoded in the table.

Recall that the characters in a character table are represented in array notation, where $A[i] = 1$ if the $i$-th taxon possesses the character and $A[i] = 0$ otherwise. Given this notation, we can easily convert the character to its split notation.

Recall also that given a binary tree $T$, the removal of an edge $e$ divides $T$ into two disconnected subtrees. In particular, the taxa have been divided into a split $S_2 \mid S_2^{\textrm{c}}$, which can be used to label $e$.

We then say that a character table is consistent if there is a binary tree $T$ whose edge splits do not conflict with the splits deriving from the table's characters. Two splits $S_1 \mid S_1^{\textrm{c}}$ and $S_2 \mid S_2^{\textrm{c}}$ conflict when all four intersections $S_1 \cap S_2$, $S_1 \cap S_2^{\textrm{c}}$, $S_1^{\textrm{c}} \cap S_2$, and $S_1^{\textrm{c}} \cap S_2^{\textrm{c}}$ are nonempty.

As a simple example, consider the conflicting quartets $\{a, b\} \mid \{c, d\}$ and $\{a, c\} \mid \{b, d\}$, which correspond to distinct trees on the taxa $a$, $b$, $c$, and $d$.