Betweenness and Nonbetweenness

Abstract

The betweenness function $bet(n)$ is the minimum number of total orderings of $n$ objects such that for any three distinct objects $a$, $b$ and $c$, there is an ordering in which $b$ is between $a$ and $c$. The nonbetweenness function $nbet(n)$ is the minimum number of total orderings such that for any three distinct objects $a$, $b$ and $c$, there is an ordering in which $b$ is not between $a$ and $c$. We show that $nbet(n)=\lceil {\log }_2{\log }_{2}n\rceil +1$ and $bet(n)=\Theta (\log n)$. Betweenness and Nonbetweenness are specific cases of a more general extreme value function called the `extreme ternary constraint function'. The asymptotic value of this generalisation is computed using the values of $nbet(n)$ and $bet(n)$. This result demonstrates that the minimum size of a set of rooted phylogenetic trees is consistent with all phylogenetic triplets is $\Theta (\log \log n)$.

9 pages