2016/02/18 by Ross Atkins, Atkins, Ross
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1602.05798
9 pages
arxiv created 2016/02/18 · openalex publication_date 2016/02/18 · arxiv updated 2016/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 log2log2n \rceil+1 and bet(n) = Θ(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 Θ(loglog n).