Abstract. Consider a rooted tree [Formula: see text] with leaf-set [Formula: see text] and with all nonleaf vertices having out-degree 2, at least. A rooted tree [Formula: see text] with leaf-set [Formula: see text] is induced by [Formula: see text] in [Formula: see text] if [Formula: see text] is the lowest common ancestor subtree for [Formula: see text], with all its degree-2 vertices suppressed. A “maximum agreement subtree” (MAST) for a pair of two trees [Formula: see text] and [Formula: see text] is a tree [Formula: see text] with a largest leaf-set [Formula: see text] such that [Formula: see text] is induced by [Formula: see text] both in [Formula: see text] and [Formula: see text]. Bryant, McKenzie, and Steel [ BioConsensus, AMS, Providence, RI, 2003, pp. 55–65] and Bernstein et al. [ SIAM J. Discrete Math., 29 (2015), pp. 2065–2074] proved, among other results, that for [Formula: see text] and [Formula: see text] being two independent copies of a random binary (uniform or Yule–Harding distributed) tree [Formula: see text], the likely magnitude order of [Formula: see text] is [Formula: see text]. We prove this bound for a wide class of random rooted trees: [Formula: see text] is a terminal tree of a branching, Galton–Watson, process with an ordered-offspring distribution of mean 1, conditioned on “total number of leaves is [Formula: see text].”

Consider a group of n men and n women, each ranking the members of the opposite sex as a potential marriage partner. A matching (marriage) of men and women is called stable if there is no pair (man, woman) who are not matched but prefer each other to their partners in the matching. It is known that, for every instance of the rankings, there is at least one stable matching and that there are instances with exponentially many stable matchings. Assume that the instance is chosen uniformly at random among all $(n!)^{2n}$ possibilities. In this case the likely number of stable matchings is known to be $n^{1/2-o(1)}$, with high probability, and of order $n\ln n$, with probability $0.84$ at least. In this paper we show that the average number of fixed pairs (man, woman), i.e., pairs common to all stable matchings, is asymptotic to $\ln^2 n$. More generally, the average number of women (men) with k stable husbands (wives) is asymptotic to $(\ln ^{k+1} n)/(k-1)!$.

We consider the problem of partitioning n integers chosen randomly between 1 and 2^m into two subsets such that the discrepancy, the absolute value of the difference of their sums, is minimized. A partition is called perfect if the optimum discrepancy is 0 when the sum of all n integers in the original set is even, or 1 when the sum is odd. Parameterizing the random problem in terms of κ = m/n, we prove that the problem has a sharp threshold at κ = 1, in the sense that for κ < 1, there are many perfect partitions with probability tending to 1 as n \to \infty, while for κ 1, there are no perfect partitions with probability tending to 1. Moreover, we show that the derivative of the so-called entropy is discontinuous at κ=1.

The probable behavior of an instance of size n of the stable marriage problem, chosen uniformly at random, is studied. The expected number of stable matchings is shown to be asymptotic to $e^{ - 1} n \ln n$ for $n \to \infty $. The total rank of women by men in the male optimal (pessimal) matching is proved to be close to n In n (respectively, $n^2 $/$\ln n$, with high probability.

The distributions of the search times for an early-insertion form of coalesced hashing (first proposed by Vitter [11], [12]) are studied. It is demonstrated, in particular, that the largest search time is very close, in probability, to the one for the late-insertion coalesced hashing [8]. In addition, a formula for the expected successful search time obtained by Chen and Vitter [1] and, independently, by Knott [7] is shown to follow directly from the presented analysis.

Let $I = (1, \cdots ,m),\, J = (1, \cdots ,n)$ and $\Delta = (D_i )_{i \in I} $ be a family of subsets $D_i $ of J. A class of algorithms which find a minimum number of $D_i $’s covering $D = \cup _{i \in I} D_i $ is studied. A measure $T(\Delta )$ of the computation time is shown to grow exponentially with the size of the problem in the worst case, namely $\max _\Delta T(\Delta ) > (4^{1/5} )^{\min (m,n')} > 1.319^{\min (m,n')} ,\, n' = |D|$. For $m = n'$ and a large subclass of algorithms, an estimate $\max _\Delta T(\Delta ) < (3/4^{1/3} )^m < (1.890)^m $ is established, so they always perform better than the obvious trivial procedure. Let, on the other hand, be chosen at random. Under condition in $\ln n/\ln m \to \gamma \in (0,\infty )$, it is proven that \[ P\left(m^{c_1 (\gamma )\ln m} \leqq T(\Delta ) \leqq m^{c_2 (\gamma )\ln m} \right) \to 1. \] Hence, asymptotically almost certainly, the computation time is of a considerably lower order than that in Hence, asymptotically almost certainly, the computation time is of a considerably lower order than that in the worst case, but it is still far from being polynomially bounded.