  Given a rooted tree and a ranking of its leaves, what is the minimum number
of inversions of the leaves that can be attained by ordering the tree? This
variation of the problem of counting inversions in arrays originated in
mathematical psychology, with the evaluation of the Mann--Whitney statistic for
detecting differences between distributions as a special case.
  We study the complexity of the problem in the comparison-query model, used
for problems like sorting and selection. For many types of trees with $n$
leaves, we establish lower bounds close to the strongest known in the model,
namely the lower bound of $\log_2(n!)$ for sorting $n$ items. We show:
  (a) $\log_2((\alpha(1-\alpha)n)!) - O(\log n)$ queries are needed whenever
the tree has a subtree that contains a fraction $\alpha$ of the leaves. This
implies a lower bound of $\log_2((\frac{k}{(k+1)^2}n)!) - O(\log n)$ for trees
of degree $k$.
  (b) $\log_2(n!) - O(\log n)$ queries are needed in case the tree is binary.
  (c) $\log_2(n!) - O(k \log k)$ queries are needed for certain classes of
trees of degree $k$, including perfect trees with even $k$.
  The lower bounds are obtained by developing two novel techniques for a
generic problem $\Pi$ in the comparison-query model and applying them to
inversion minimization on trees. Both techniques can be described in terms of
the Cayley graph of the symmetric group with adjacent-rank transpositions as
the generating set. Consider the subgraph consisting of the edges between
vertices with the same value under $\Pi$. We show that the size of any decision
tree for $\Pi$ must be at least:
  (i) the number of connected components of this subgraph, and
  (ii) the factorial of the average degree of the complementary subgraph,
divided by $n$.
  Lower bounds on query complexity then follow by taking the base-2 logarithm.
