In analogy to other concepts of a similar nature, we define the inducibility of a rooted binary tree. Given a fixed rooted binary tree $B$ with $k$ leaves, we let $\gamma(B,T)$ be the proportion of all subsets of $k$ leaves in $T$ that induce a tree isomorphic to $B$. The inducibility of $B$ is $\limsup_{|T| \to \infty} \gamma(B,T)$. We determine the inducibility in some special cases, show that every binary tree has positive inducibility and prove that caterpillars are the only binary trees with inducibility $1$. We also formulate some open problems and conjectures on the inducibility. Finally, we present an application to crossing numbers of random tanglegrams.

In this paper we study inverting random functions under the maximum likelihood estimation (MLE) criterion in the discrete setting. In particular, we consider how many independent evaluations of the random function at a particular element of the domain are needed for reliable reconstruction of that element. We provide explicit upper and lower bounds for MLE, both in the nonparametric and parametric setting, and give applications to coin-tossing and phylogenetic tree reconstruction.

The bipartite crossing number problem is studied and a connection between this problem and the linear arrangement problem is established. A lower bound and an upper bound for the optimal number of crossings are derived, where the main terms are the optimal arrangement values. Two polynomial time approximation algorithms for the bipartite crossing number are obtained. The performance guarantees are O(log n) and O(log 2 n ) times the optimal, respectively, for a large class of bipartite graphs on n vertices. No polynomial time approximation algorithm which could generate a provably good solution had been known. For a tree, a formula is derived that expresses the optimal number of crossings in terms of the optimal value of the linear arrangement and the degrees, resulting in an O(n 1.6 ) time algorithm for computing the bipartite crossing number. The problem of computing a maximum weight biplanar subgraph of an acyclic graph is also studied and a linear time algorithm for solving it is derived. No polynomial time algorithm for this problem was known, and the unweighted version of the problem had been known to be NP-hard, even for planar bipartite graphs of degree at most 3.

This paper presents the results of the authors’ investigation of a combinatorial problem arising from the study of evolutionary trees. In graph theoretic terms it can be expressed as a problem of colouring vertices of a binary tree. For a given colouring of the pendant vertices of a binary tree there is a simple algorithm for assigning colours to internal vertices minimising the number of edges of the tree whose end vertices have differing colours. This minimal number is called the length of the tree. The question posed is: For given numbers of pendant vertices of assigned colours, how many trees of a particular length can be constructed on those vertices? This question is answered in two special cases. Answers to this problem are needed to establish the distribution of lengths of evolutionary trees, by which the significance of the maximum parsimony principle for selecting evolutionary trees can be judged.