Betweenness and Nonbetweenness

MaRDI QIDQ6270609zbMATH OpenFDO

Authors Ross Atkins

Publication date 18 February 2016

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)=leftlceillo{g}_{2}lo{g}_{2}nightceil+1$ and $bet(n)=Theta(logn)$. 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(loglogn)$.

This page was built for publication: Betweenness and Nonbetweenness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6270609)