# Query Complexity of Inversion Minimization on Trees

Ivan Hu  Dieter van Melkebeek  Andrew Morgan

###### Abstract

We consider the following computational problem: 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 well-known
problem of counting inversions in arrays originated in mathematical
psychology. It has 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, the
standard model for problems like sorting, selection, and heap construction.
The complexity depends heavily on the shape of the tree: for trees of unit
depth, the problem is trivial; for many other shapes, we establish lower
bounds close to the strongest known in the model, namely the lower bound of
$\log_{2}(n!)$ for sorting $n$ items. For trees with $n$ leaves we show, in
increasing order of closeness to the sorting lower bound:

  * (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, or equivalently, in terms of the edge graph of the
permutahedron, the polytope spanned by all permutations of the vector
$(1,2,\dots,n)$. 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.
Technique (i) represents a discrete analog of a classical technique in
algebraic complexity and allows us to establish (c) and a tight lower bound
for counting cross inversions, as well as unify several of the known lower
bounds in the comparison-query model. Technique (ii) represents an analog of
sensitivity arguments in Boolean complexity and allows us to establish (a) and
(b).

Along the way to proving (b), we derive a tight upper bound on the maximum
probability of the distribution of cross inversions, which is the distribution
of the Mann–Whitney statistic in the case of the null hypothesis. Up to
normalization the probabilities alternately appear in the literature as the
coefficients of polynomials formed by the Gaussian binomial coefficients, also
known as Gaussian polynomials.

##  1 Overview

The result of a hierarchical cluster analysis on a set $X$ of items can be
thought of as an unordered rooted tree $T$ with leaf set $X$. To visualize the
tree, or to spell out the classification in text, one needs to decide for
every internal node of $T$ in which order to visit its children. Figure 1(a)
represents an example of a classification of eight body parts from the
psychology literature [Deg82]. It is obtained by repeatedly clustering nearest
neighbors where the distance between two items is given by the number of
people in a survey who put the items into different classes [Mil69]. The
ordering of the resulting binary tree in Figure 1(a) is the output produced by
a particular implementation of the clustering algorithm.

kneethightoechestwaistcheekmouthear (a) Initial tree ordering

earcheekmouthchestwaistthighkneetoe (b) Optimal tree ordering

Figure 1: Classification of body parts

Another ordering is given in Figure 1(b); black marks the nodes whose children
have been swapped from the ordering in Figure 1(a). Figure 1(b) has the
advantage over Figure 1(a) that the leaves now appear in an interesting global
order, namely head-to-toe: ear, cheek, mouth, chest, waist, thigh, knee, toe.
Indeed, Figure 1(b) makes apparent that the anatomical order correlates
perfectly with the clustering. In general, given a tree $T$ and a ranking
$\rho$ of its leaves, one might ask “how correlated” is $T$ with $\rho$?
Degerman [Deg82] suggests evaluating the orderings of $T$ in terms of the
number of inversions of the left-to-right ranking $\sigma$ of the leaves with
respect to the given ranking $\rho$, and use the minimum number over all
orderings as a measure of (non)correlation.

###### Definition 1 (ranking, inversion, $\operatorname{Inv}_{\cdot}(\cdot)$).

A _ranking_ $\rho$ of a set $X$ of $n$ items is a bijection from $X$ to $[n]$.
Given two rankings $\sigma$ and $\rho$, an _inversion_ of $\sigma$ with
respect to $\rho$ is a pair of items $x_{1},x_{2}\in X$ such that
$\rho(x_{1})<\rho(x_{2})$ but $\sigma(x_{1})>\sigma(x_{2})$. The number of
inversions is denoted by $\operatorname{Inv}_{\rho}(\sigma)$. An inversion in
an array $A$ of values is an inversion of $\sigma$ with respect to $\rho$
where $\sigma$ denotes the ranking by array index and $\rho$ the ranking by
value; in this setting we write $\operatorname{Inv}(A)$ for
$\operatorname{Inv}_{\rho}(\sigma)$.

The minimum number of inversions can be used to compare the quality of
different trees $T$ for a given ranking $\rho$, or of different rankings
$\rho$ for a given tree $T$. This mimics the use of the number of inversions
in applications like collaborative filtering in recommender systems, rank
aggregation for meta searching the web, and Kendall’s test for dependencies
between two random variables. In particular, the Mann–Whitney test for
differences between random variables can be viewed as a special case of our
optimization problem. The test is widely used because of its nonparametric
nature, meaning that no assumptions need to be made about the distribution of
the two variables; the distribution of the statistic in the case of the null
hypothesis (both variables have the same distribution) is always the same. The
test achieves this property by only considering the relative order of the
samples. It takes a sequence $A$ of $a$ samples from a random variable $Y$, a
sequence $B$ of $b$ samples from another random variable $Z$, and computes the
statistic $U\doteq\min(\operatorname{XInv}(A,B),\operatorname{XInv}(B,A))$
that is the minimum of the number $\operatorname{XInv}(A,B)$ of cross
inversions from $A$ to $B$, and vice versa.

###### Definition 2 (cross inversions,
$\operatorname{XInv}_{\cdot}(\cdot,\cdot)$).

Let $\rho$ be a ranking of $X$, and $A,B\subseteq X$. A _cross inversion_ from
$A$ to $B$ with respect to $\rho$ is a pair $(x_{1},x_{2})\in A\times B$ that
is out of order with respect to $\rho$, i.e., such that
$\rho(x_{1})>\rho(x_{2})$. The number of cross inversions is denoted by
$\operatorname{XInv}_{\rho}(A,B)$. For two arrays $A$ and $B$ of values, a
cross inversion from $A$ to $B$ is a cross inversion from the set of entries
in $A$ to the set of entries in $B$ where $\rho$ denotes the ranking by value;
in this setting we write $\operatorname{XInv}(A,B)$ for
$\operatorname{XInv}_{\rho}(A,B)$.

The statistic $U$ coincides with the optimum value of our optimization problem
on input the tree $T$ in Figure 2, where the leftmost $a$ leaves correspond to
the samples $A$, the rightmost $b$ leaves to the samples $B$, and the ranking
$\rho$ to the value order of the combined $a+b$ samples.

$\cdots$$\cdots$$a$ leaves$b$ leaves Figure 2: Mann–Whitney instance

We mainly study the value version of our optimization problem, which we denote
by $\operatorname{MinInv}$.

###### Definition 3 (inversion minimization on trees,
$\operatorname{MinInv}(\cdot,\cdot)$, $\Pi_{\cdot}$).

Inversion minimization on trees is the computational problem with the
following specification:

Input:

A rooted tree $T$ with leaf set $X$ of size $n$, and a ranking $\rho$ of $X$.

Output:

$\operatorname{MinInv}(T,\rho)$, the minimum of
$\operatorname{Inv}_{\rho}(\sigma)$ over all possible orderings of $T$, where
$\sigma$ denotes the left-to-right ranking of $X$ induced by the ordering of
$T$.

For any fixed tree $T$ with leaf set $X$, we use the short-hand $\Pi_{T}$ to
denote the computational problem that takes as input a ranking $\rho$ of $X$
and outputs $\operatorname{MinInv}(T,\rho)$.

Degerman [Deg82] observes that the ordering at each internal node can be
optimized independently in a greedy fashion. In the setting of binary trees,
for each node $v$, we can count the cross inversions from the leaves in the
left subtree of $v$ to the leaves in the right subtree of $v$. Between the two
possible orderings of the children of a node $v$, we choose the one that
yields the smaller number of cross inversions. Based on his observation,
Degerman presents a polynomial-time algorithm for the case of binary trees
$T$. A more refined implementation and analysis yields a running time of
$O(0pt_{\mathrm{avg}}(T)\cdot n)$, where $0pt_{\mathrm{avg}}(T)$ denotes the
average depth of a leaf in $T$. For balanced binary trees the running time
becomes $O(n\log n)$. All of this can be viewed as variants of the well-known
$O(n\log n)$ divide-and-conquer algorithm for counting inversions in arrays of
length $n$.

For trees of degree $\deg(T)>2$, the local greedy optimization at each
internal node becomes more complicated, as there are many ways to order the
children of each internal node. Exhaustive search results in a running time of
$O((\deg(T)!+\deg(T)\cdot 0pt_{\mathrm{avg}}(T))\cdot n)$, which can be
improved to $O((\deg(T)^{2}2^{\deg(T)}+\deg(T)\cdot
0pt_{\mathrm{avg}}(T))\cdot n)$ using dynamic programming. The problem is
closely related to the classical problem of minimum arc feedback set, and
becomes NP-hard without any constraints on the degree. We refer to Section 10
for more details.

#### Query complexity.

Rather than running time in the Turing machine model, our focus lies on query
complexity in the comparison-query model. There we can only access the ranking
$\rho:X\to[n]$ via queries of the form: Is $\rho(x_{1})<\rho(x_{2})$? For any
fixed tree $T$, we want to determine the minimum number of queries needed to
solve the problem.

The comparison-query model represents the standard model for analyzing
problems like sorting, selection, and heap construction. Sorting represents
the hardest problem in the comparison-query model as it is tantamount to
knowing the entire ranking $\rho$. Its query complexity has a well-known
information-theoretic lower bound of
$\log_{2}(n!)=n\log_{2}(n/e)+\frac{1}{2}\log_{2}(n)+O(1)$. Standard algorithms
such as mergesort and heapsort yield an upper bound of $\log_{2}(n!)+O(n)$,
which has been improved to $\log_{2}(n!)+o(n)$ recently [Ser21]. We refer to
Section 2 for an overview of results and techniques for lower bounds in the
model.

Information theory only yields a very weak lower bound on the query complexity
of inversion minimization on trees: $\log_{2}\binom{n}{2}=2\log_{2}(n)-O(1)$.
The complexity of the problem critically depends on the shape of the tree $T$
and can be significantly lower than the one for sorting. For starters, the
problem becomes trivial for trees of depth one as their leaves can be arranged
freely in any order. More precisely, the trees $T$ for which the answer is
identically zero, irrespective of the ranking $\rho$, are exactly those such
that all root-to-leaf paths have only the root in common.

Arguably, the simplest nontrivial instances of inversion minimization are for
trees $T$ of the Mann–Whitney type in Figure 2 with $a=1$ and $b=n-1$.
Depending on the rank $r$ of the isolated leaf, an optimal ordering of $T$ is
either the left or the right part in Figure 3, where the label of each leaf is
its rank under $\rho$.

$r$$1$$2$$\dots$$n$

$r$$1$$2$$\dots$$n$

Figure 3: Rank instance

As the ordering on the left has $r-1$ inversions and the one on the right
$n-r$, the answer is $\min(r-1,n-r)$. Thus, this instance of inversion
minimization on trees is essentially equivalent to rank finding, which has
query complexity exactly $n-1$.

#### Results.

We prove that for many trees $T$, inversion minimization on $T$ is nearly as
hard as sorting. First, we exhibit a common structure that guarantees high
complexity, namely a subtree that contains a fairly balanced fraction of the
leaves. We make use of the following notation.

###### Definition 4 (leaf set, $\operatorname{L}(\cdot)$, and subtree).

For a tree $T$, the leaf set of $T$, denoted $\operatorname{L}(T)$, is the set
of leaves of $T$. For a node $v$ to $T$, $T_{v}$ denotes the subtree of $T$
rooted at $v$.

The quantitative statement references the gamma function $\Gamma$, which is a
proxy for any convex real function that interpolates the factorial function on
the positive integers. More precisely, we have that $\Gamma(n+1)=n!$ for every
integer $n\geq 1$.

###### Theorem 5 (lower bound for general trees).

Let $T$ be a tree with $n$ leaves, and $v$ a node with
$\lvert\operatorname{L}(T_{v})\rvert=\ell$. The query complexity of inversion
minimization on $T$ is at least $\log_{2}(\Gamma(\frac{\ell(n-\ell)}{n}+1))$.
In particular, the complexity is at least
$\log_{2}(\Gamma(\frac{k}{(k+1)^{2}}\cdot n+1))$ where $k$ denotes the degree
of $T$.

For trees of constant degree, Theorem 5 yields a lower bound that is as strong
as the one for sorting up to a constant multiplicative factor. For the
important case of binary trees (like the classification trees from the
motivating example), we obtain a lower bound that is only a logarithmic
additive term shy of the lower bound for sorting.

###### Theorem 6 (lower bound for binary trees).

For binary trees $T$ with $n$ leaves, the query complexity of inversion
minimization on $T$ is at least $\log_{2}(n!)-O(\log n)$.

The logarithmic loss can be reduced to a constant for certain restricted
classes of trees. The full statement is somewhat technical. First, it assumes
that the tree has no nodes of degree 1. This is without loss of generality, as
we can short-cut all degree-1 nodes in the tree without affecting the minimum
number of inversions. For example, trivial trees for inversion minimization
have depth 1 without loss of generality. Second, the strength of the lower
bound depends on the maximum size of a leaf child set, defined as follows.

###### Definition 7 (leaf child set, $\operatorname{LC}(\cdot)$).

The _leaf child set_ $\operatorname{LC}(v)$ of a vertex $v$ in a tree $T$ is
the set $\operatorname{LC}(v)$ of all the children of $v$ that are leaves in
$T$.

Most importantly, the result requires certain fragile parity conditions to
hold. That said, there are interesting classes satisfying all requirements,
and the bounds are very tight.

###### Theorem 8 (lower bound for restricted classes).

Let $T$ be a tree without nodes of degree 1 such that the leaf child sets have
size at most $k$, at most one of them is odd, and if there exists an odd one,
say $\operatorname{LC}(v^{*})$, then all ancestors of $v^{*}$ have empty leaf
child sets. The query complexity of inversion minimization on $T$ is at least
$\log_{2}(n!)-O(k\log k)$. In particular, the lower bound applies to:

  * $\circ$

perfect trees of even degree $k$, and

  * $\circ$

full binary ($k=2$) trees with at most one leaf without a sibling leaf.

Recall that a tree of degree $k$ is full if every node has degree 0 or $k$. It
is perfect if it is full and all leaves have the same depth.

For the Mann–Whitney statistic, Theorem 5 provides an $\Omega(n\log n)$ lower
bound for balanced instances, i.e., when $a$ and $b$ are $\Theta(n)$. For
unbalanced instances there is a more efficient way to count cross inversions
and thus evaluate the statistic: Sort the smaller of the two sides, and then
do a binary search for each item of the larger side to find its position
within the sorted smaller side so as to determine the number of cross
inversions that it contributes. For $a\leq b$ the approach makes
$b\log_{2}(a)+O(a\log a)$ comparisons. We establish a lower bound that shows
the approach is optimal up to a constant multiplicative factor.

###### Theorem 9 (lower bound for counting cross inversions).

Counting cross inversions from a set $A$ of size $a$ to a set $B$ of size
$b\geq a$ with respect to a ranking $\rho$ of $X\doteq A\sqcup B$ requires
$\Omega((a+b)\log(a))$ queries in the comparison-query model, as does
inversion minimization on the tree of Figure 2.

#### Techniques.

We obtain our results by developing two new query lower bound techniques for
generic problems $\Pi$ in the comparison-query model, and then instantiating
them to the problem $\Pi_{T}$ of inversion minimization on a fixed tree $T$.
Both techniques follow the common pattern of lower bounding the number of
distinct execution traces that any algorithm for $\Pi$ needs to have.

###### Definition 10 (execution trace, complexity measures
$\operatorname{D}(\cdot)$ and $\operatorname{Q}(\cdot)$).

Consider an algorithm $A$ for a problem $\Pi$ in the comparison-query model.
An execution trace of $A$ is the sequence of comparisons that $A$ makes on
some input $\rho$, as well as the outcomes of the comparisons. The complexity
$\operatorname{D}(\Pi)$ is the minimum over all possible algorithms for $\Pi$
of the number of distinct traces the algorithm has over the set of all inputs
$\rho$. The complexity $\operatorname{Q}(\Pi)$ is the minimum, over all
possible algorithms for $\Pi$ of the maximum number of comparisons that the
algorithm makes over the set of all inputs $\rho$.

The complexity measure $\operatorname{Q}$ is what we refer to as query
complexity. Since the maximum number of queries that an algorithm $A$ makes is
at least the base-2 logarithm of the number of execution traces, we have that
$\operatorname{Q}(\Pi)\geq\log_{2}(\operatorname{D}(\Pi))$. Note that, in
order to avoid confusion with the tree $T$ specifying an instance of inversion
minimization, we refrain from the common terminology of decision trees in the
context of the complexity measure $\operatorname{D}$. In those terms, we lower
bound the number of leaves of any decision tree for $\Pi$, and use the fact
that the depth of this binary decision tree is at least the base-2 logarithm
of the number of leaves.

Both techniques proceed by considering the effect on the output of
perturbations to the input ranking $\rho$ that are hard for queries to
observe. More specifically, we consider the following perturbations:

###### Definition 11 (adjacent-rank transposition, affected items).

An _adjacent-rank transposition_ is a permutation $\tau$ of $[n]$ of the form
$\tau=(r,r+1)$, where $r\in[n-1]$ and $n$ denotes the number of items. Given
$\tau$ and a ranking $\rho:X\to[n]$, the _affected items_ are the two elements
$x\in X$ for which $\tau(\rho(x))\neq\rho(x)$, i.e., the items with ranks $r$
and $r+1$ under $\rho$.

As with any permutation of the set of ranks, the effect of $\tau$ on a ranking
$\rho$ is the ranking $\tau\rho$. Adjacent-rank transpositions are the least
noticeable perturbations one can apply to a ranking in the following sense: If
two rankings differ by an adjacent-rank transposition, then the only query
that distinguishes them is the query that compares the affected items.

#### Sensitivity.

Our first technique turns this observation around to obtain a lower bound on
query complexity. We adopt the terminology of sensitivity from Boolean query
complexity.

###### Definition 12 (sensitivity, average sensitivity, $s(\cdot)$).

Let $\Pi$ be a computational problem in the comparison-query model on a set
$X$ of items. For a fixed ranking $\rho$ and adjacent-rank transposition
$\tau$, we say that $\Pi$ is _sensitive_ to $\tau$ at $\rho$ if
$\Pi(\rho)\neq\Pi(\tau\rho)$. The sensitivity of $\Pi$ at $\rho$ is the number
of adjacent-rank transpositions $\tau$ such that $\Pi$ is sensitive to $\tau$
at $\rho$. The _average sensitivity_ of $\Pi$, denoted $s(\Pi)$, is the
average sensitivity of $\Pi$ at $\rho$ when $\rho$ is drawn uniformly at
random from all rankings of $X$.

On input a ranking $\rho$, any algorithm for $\Pi$ needs to make a number of
queries that is at least the sensitivity of $\Pi$ at $\rho$. Indeed, consider
an adjacent-rank transposition $\tau$ to which $\Pi$ is sensitive at $\rho$.
If the algorithm does not make the query that compares the affected items,
then it must output the same answer on input $\tau\rho$ as on input $\rho$.
Since the value of $\Pi$ differs on both inputs, this means the algorithm
makes a mistake on at least one of the two. It follows that the average number
of queries that any algorithm for $\Pi$ makes is at least the average
sensitivity $s(\Pi)$. A fortiori, $\operatorname{Q}(\Pi)\geq s(\Pi)$.

As sensitivity cannot exceed $n-1$, the best lower bound on query complexity
that we can establish based on the above basic observation alone, is $n-1$.
The following improvement yields a the lower bound $\operatorname{D}(\Pi)\geq
n!/n=(n-1)!$, and therefore
$\operatorname{Q}(\Pi)\geq\log_{2}(n!)-\log_{2}(n)$ for problems $\Pi$ of
maximum average sensitivity $s(\Pi)=n-1$. The argument hinges on an efficient
encoding of rankings that share the same execution trace. See Section 3 for
more details.

###### Lemma 13 (Sensitivity Lemma).

For any problem $\Pi$ in the comparison-query model with $n$ items,
$\operatorname{D}(\Pi)\geq\Gamma(s(\Pi)+2)/n$.

The lower bound for general trees $T$ in Theorem 5 and the strengthening for
binary trees in Theorem 6 follow from corresponding lower bounds on the
average sensitivity $s(\Pi_{T})$. Theorem 5 only requires a short analysis to
establish the sensitivity lower bound needed for the application of the
Sensitivity Lemma; this illustrates the power of the lemma and of the lower
bound technique. Theorem 6 requires a more involved sensitivity analysis, but
then yields a very tight lower bound. Owing to the average-case nature of the
underlying measure, the technique also exhibits some degree of robustness. For
the particular problem of inversion minimization on trees, we show that small
changes to the tree $T$ do not affect the average sensitivity $s(\Pi_{T})$ by
much. See Section 4 and Section 5.

For sorting, counting inversions, and inversion parity, the average
sensitivity reaches its maximum value of $n-1$, and Lemma 13 recovers the
standard lower bounds up to a small loss. In contrast, for selection, the
average sensitivity equals 1 for ranks 1 and $n$, and 2 for other ranks, so
the bound from Lemma 13 is no good. This reflects that, just like in the
Boolean setting, (average) sensitivity is sometimes too rough of a measure and
not always capable of proving strong lower bounds. Our second technique looks
at a more delicate structural aspect, which enables it to sometimes yield
stronger lower bounds.

Figure 4: Permutahedron for $n=4$ items

#### Permutahedron graph.

Before introducing our second technique, we cast our first technique in graph
theoretic terms. In fact, both our techniques can be expressed naturally in
subgraphs of the graph with the rankings as vertices and adjacent-rank
transpositions as edges. The latter graph can be viewed as the Cayley graph of
the symmetric group with adjacent-rank transpositions as the generating set.
It is also the edge graph of the permutahedron, the convex polytope spanned by
all permutations of the vertex $(1,2,\dots,n)$ in $\mathbb{R}^{n}$. The
permutahedron resides inside the hyperplane where the sum of the coordinates
equals $\binom{n}{2}$, has positive volume inside that hyperplane, and can
thus be represented naturally in dimension $n-1$; see Figure 4 for a rendering
of the instance with $n=4$ [Epp07].

We think of coloring the vertices of the permutahedron with their values under
$\Pi$ and make use of the subgraph with the same vertex set but only
containing the monochromatic edges, i.e., the edges whose end points have the
same value under $\Pi$. We also consider the the complementary subgraph
containing all bichromatic edges.

###### Definition 14 (permutahedron graph, $G(\cdot)$, $\overline{G}(\cdot)$).

Let $\Pi$ be a computational problem in the comparison-query model on a set
$X$ of items. The _permutahedron graph_ of $\Pi$, denoted $G(\Pi)$, has the
rankings of $X$ as vertices, and an edge between two rankings $\rho_{1}$ and
$\rho_{2}$ if $\Pi(\rho_{1})=\Pi(\rho_{2})$ and there exists an adjacent-rank
transposition such that $\rho_{2}=\tau\rho_{1}$. The _complementary
permutahedron graph_ of $\Pi$, denoted $\overline{G}(\Pi)$, is defined
similarly by replacing the condition $\Pi(\rho_{1})=\Pi(\rho_{2})$ by its
complement, $\Pi(\rho_{1})\neq\Pi(\rho_{2})$.

Our first technique looks at degrees in the complementary permutahedron graph
$\overline{G}(\Pi)$, and more specifically at the _average degree_
$\deg_{\mathrm{avg}}(\overline{G}(\Pi))\doteq\mathbb{E}(\deg_{\overline{G}(\Pi)}(\rho))$,
where the expectation is with respect to a uniform choice of the ranking
$\rho$. Our second technique looks at the connected components of the
permutahedron graph $G(\Pi)$.

#### Connectivity.

Our second technique is reminiscent of a result in algebraic complexity
theory, where the number of execution traces of an algorithm for a problem
$\Pi$ in the algebraic comparison-query model is lower bounded in terms of the
number of connected components that $\Pi$ induces in its input space
$\mathbb{R}^{n}$ [BO83]. In the comparison-query setting, we obtain the
following lower bound.

###### Lemma 15 (Connectivity Lemma).

For any problem $\Pi$ in the comparison-query model, $\operatorname{D}(\Pi)$
is at least the number of connected components of $G(\Pi)$.

The Connectivity Lemma allows for a simple and unified exposition of many of
the known lower bounds. For counting inversions and inversion parity the
argument goes as follows. Every adjacent-rank transposition changes the number
of inversions by exactly one (up or down), and therefore changes the output of
$\Pi$, so all $n!$ vertices in $G(\Pi)$ are isolated. This means that any
algorithm for $\Pi$ actually needs to sort and has to make at least
$\log_{2}(n!)$ queries. See Section 7 for a proof of the Connectivity Lemma
and more applications to classical problems, including the $\Omega(n)$ lower
bound for median finding.

The Connectivity Lemma also enables us to establish strong lower bounds for
inversion minimization on special types of trees $T$, namely those of Theorem
6 and the Mann–Whitney instances in Theorem 9, closely related to counting
inversions. Both theorems involve an analysis of the size of the connected
component of a random ranking $\rho$ in $G(\Pi_{T})$, and Theorem 6 uses the
delicate parity conditions of its statement to keep $G(\Pi_{T})$ as sparse as
possible. See Section 8 for more details.

The Mann–Whitney setting illustrates well the relative power of our
techniques. In the Mann–Whitney instances of inversion minimization, the
leaves are naturally split between a subtree containing $a$ of them and a
subtree containing $b$ of them. The argument behind Theorem 5 yields a lower
bound of $\frac{ab}{a+b}$ on the sensitivity $s(\Pi_{T})$. The true
sensitivity is just $O(1)$ below the one for counting cross inversions, which
is $\frac{2ab}{a+b}$. The resulting lower bounds on the query complexity in
case $a\leq b$ are $\Theta(a\log a)$, which roughly account for sorting the
smaller side but not for the $b\log_{2}(a)$ comparisons used in the subsequent
binary searches for counting cross inversions. Our approach based on the
Connectivity Lemma yields a lower bound that includes both terms. On the other
hand, it is easier to estimate and obtain the lower bound via the Sensitivity
Lemma than to argue the query lower bound via the Connectivity Lemma or from
scratch.

#### Other modes of computation.

We stated our lower bounds for the standard, deterministic mode of
computation. Both of our techniques provide lower bounds for the number of
distinct execution traces that are needed to cover all input rankings,
irrespective of whether these execution traces derive from a single algorithm.
Such execution traces can be viewed as certificates or witnesses for the value
of $\Pi$ on a given input $\rho$, or as valid execution traces of a
nondeterministic algorithm for $\Pi$. We define the minimum number of traces
needed to cover all input rankings for a problem $\Pi$ as the nondeterministic
complexity of $\Pi$ and denote it by $\operatorname{N}(\Pi)$, along the lines
of the Boolean setting [JRSW99]. All of our lower bounds on
$\operatorname{D}(\Pi)$ actually hold for $\operatorname{N}(\Pi)$. See Remark
19 and Remark 44 for further discussion.

Since randomized algorithms with zero error are also nondeterministic
algorithms, all of our lower bounds apply verbatim to the former mode of
computation, as well. As for randomized algorithms with bounded error, we
argue in Section 6 that our lower bounds on the query complexity of inversion
minimization on trees that follow from the Sensitivity Lemma carry over modulo
a small loss in strength. We do so by showing generically that high average
sensitivity implies high query complexity against such algorithms.

The fact that our techniques yield lower bounds on $\operatorname{N}(\Pi)$ and
not just $\operatorname{D}(\Pi)$ also explains why our approaches sometimes
fail. For example, for the problem $\Pi$ of finding the minimum of $n$ items,
a total of $n$ certificates suffice and are needed, namely one for each
possible item being the minimum. This means that our techniques cannot give a
lower bound on the query complexity of $\Pi$ that is better than
$\log_{2}(n)$. In contrast, as reviewed in Section 2,
$\operatorname{D}(\Pi)=2^{n-1}$ and the number of queries needed is $n-1$.

#### Cross-inversion distribution.

As a technical result in the sensitivity analysis for inversion minimization
on binary trees (Theorem 6), we need a strong upper bound on the probability
that the number of cross inversions $\operatorname{XInv}_{\rho}(A,B)$ takes on
any particular value when the ranking $\rho$ of the set $X=A\sqcup B$ is
chosen uniformly at random. This is the distribution of the Mann–Whitney
statistic under the null hypothesis. Mann and Whitney [MW47] argued that it
converges to a normal distribution with mean $\mu=ab/2$ and variance
$\sigma^{2}=ab(a+b+1)/12$ as $a\doteq|A|$ and $b\doteq|B|$ grow large. Since
the normal distribution has a maximum density of $1/(\sqrt{2\pi}\sigma)$,
their result suggests that the maximum of the underlying probability
distribution is $O(1/\sigma)=O(1/\sqrt{ab(a+b+1)})$. Takács [Tak86] managed to
formally establish such a bound for all pairs $(a,b)$ with
$|a-b|=O(\sqrt{a+b})$, Stanley and Zanello [SZ16] for all pairs $(a,b)$ with
$\min(a,b)$ bounded, and Melczer, Panova, and Pemantle [MPP20] for all pairs
$(a,b)$ with $|a-b|\leq\alpha\cdot(a+b)$ for some constant $\alpha<1$.
However, these results do not cover all regimes and leave open a single bound
of the same form that applies to all pairs $(a,b)$, which is what we need for
Theorem 6. We establish such a bound in Section 9. The counts of the rankings
$\rho$ with a particular value for $\operatorname{XInv}_{\rho}(A,B)$ appear as
the coefficients of the _Gaussian polynomials_. Our bound can be stated
equivalently as a bound on those coefficients.

#### Organization.

We have organized the material so as to provide a shortest route to a full
proof of Theorem 5. Here are the sections needed for the different main
results:

  * $\circ$

Theorem 5 (lower bound for general trees): 3, 4.

  * $\circ$

Theorem 6 (lower bound for binary trees): 3, 5, 9.

  * $\circ$

Theorem 8 (lower bound for restricted classes): 7, 8 up to 8.2 inclusive.

  * $\circ$

Theorem 9 (lower bound for counting cross inversions): 7, 8 but not 8.1 nor
8.2.

In Section 2, we provide some background on known lower bounds in the
comparison-query model, several of which are unified by the Sensitivity Lemma
and Connectivity Lemma. In Section 6, we present our lower bounds against
randomized algorithms with bounded error. The tight bound on maximum
probability of the cross-inversion distribution is covered in Section 9. For
completeness, we end in Section 10 with proofs of the results we stated on the
Turing complexity of inversion minimization on trees.

##  2 The Comparison-Query Model

In this section we provide an overview of known results and techniques for
lower bounds in the comparison-query model. This section can be skipped
without a significant loss in continuity.

Tight bounds have been established for problems like sorting, selection, and
heap construction.

  * $\circ$

We already discussed the central problem of sorting in Section 1.

  * $\circ$

In _selection_ we are told a rank $r$, and must identify the item with rank
$r$. The query complexity is known to be $\Theta(n)$ [BFP+73, DZ99, DZ01].
There is also _multiple selection_ , in which one is given multiple ranks
$r_{1},\dots,r_{k}$, and must identify each of the corresponding items. The
query complexity of multiple selection is likewise known up to a $\Theta(n)$
gap between the upper and lower bounds [KMMS05].

  * $\circ$

In _heap construction_ we must arrange the items as nodes in a complete binary
tree such that every node has a rank no larger than its children. The query
complexity is known to be $\Theta(n)$.

All the problems above can be cast as instantiations of a general framework
known as _partial order production_ [Sch76]. Here, in addition to query access
to the ranking $\rho$ of the items, we are given $n$ _slots_ and regular
access to a partial order $<_{\mathrm{slot}}$ on the slots. The objective is
to put each item into a slot, one item per slot, so that whenever two slots,
$s_{1}$ and $s_{2}$, are related by $s_{1}<_{\mathrm{slot}}s_{2}$, we also
have $\rho(s_{1})<\rho(s_{2})$. Sorting coincides with the case where
$<_{\mathrm{slot}}$ is a total order. In selection of rank $r$, there is a
designated slot $s^{*}$, and there are exactly $r-1$ slots $s$ with
$s<_{\mathrm{slot}}s^{*}$ and exactly $n-r$ slots $s$ with
$s^{*}<_{\mathrm{slot}}s$; there are no other relations in
$<_{\mathrm{slot}}$. Multiple selection is similar. For heap construction,
$<_{\mathrm{slot}}$ matches the complete binary tree arrangement.

There is a generic lower bound for partial order production, the information-
theoretic limit. For each way of putting items into slots, the number of input
rankings $\rho$ for which that way is a correct answer is bounded by
$e(<_{\mathrm{slot}})$, the number of ways to extend $<_{\mathrm{slot}}$ to a
total order. Therefore, there must be at least $n!/e(<_{\mathrm{slot}})$
distinct execution traces. Since each execution trace is determined by the
outcomes of its queries, and each query has only two outcomes, we conclude
that $\lambda(<_{\mathrm{slot}})\doteq\log_{2}(n!/e(<_{\mathrm{slot}}))$
queries are necessary to solve partial order production. Complementing this
lower bound there exists an upper bound of
$(1+o(1))\cdot\lambda(<_{\mathrm{slot}})+O(n)$ queries [CFJ+10]. One may
assume without loss of generality the relationship
$\lambda(<_{\mathrm{slot}})\geq n-1$, in which case
$O(\lambda(<_{\mathrm{slot}}))$ queries always suffices. Thus, the complexity
of partial order production is $\Theta(\lambda)$.

Not every problem of interest in the comparison model is an instance of
partial order production. Here are a few examples.

  * $\circ$

In _rank finding_ there is a designated item $x^{*}$, and we have to compute
its rank. The rank can be computed by comparing $x^{*}$ with each of the $n-1$
other items. Any combination of less than $n-1$ queries leaves at least one
item of which the relative ranking with $x^{*}$ remains undetermined. Thus,
the query complexity is exactly $n-1$.

  * $\circ$

In _counting inversions_ the items are arranged in some known order $\sigma$
and the objective is to count the number of inversions of $\sigma$ with
respect to $\rho$. As we reviewed in Section 1, counting inversions has
exactly the same query complexity as sorting.

  * $\circ$

The problem of _inversion parity_ is the same as counting inversions except
that one need only count the number of inversions modulo 2. This problem, as
well as counting inversions modulo $m$ for any integer $m>1$, also has exactly
the same complexity as sorting.

For each of the three problems above, information theory does not provide a
satisfactory lower bound. For example, in the inversion parity problem there
are only two possible outputs, which yields a lower bound of $\log_{2}(2)=1$.
It so happens that for each of the preceding three examples, the query
complexity is known quite precisely; however, the known arguments are rather
problem-specific.

_Inversion minimization on trees_ is another example that does not fit the
framework of partial order generation, and for which information theory only
yields a weak lower bound: $\log_{2}\binom{n}{2}=2\log_{2}(n)-\Theta(1)$. In
contrast to the above examples, a strong lower bound does not seem to follow
from a simple ad-hoc argument nor from a literal equivalence to sorting.

##  3 Sensitivity Lemma

In this section we develop Lemma 13. We actually prove a somewhat stronger
version.

###### Lemma 16 (Strong Sensitivity Lemma).

Consider an algorithm $A$ in the comparison-based model with $n$ items, color
each vertex of the permutahedron with its execution trace under $A$, and let
$\overline{H}$ denote the subgraph with the same vertex set but only
containing the bichromatic edges. The number of distinct execution traces of
$A$ is at least $g(\deg_{\mathrm{avg}}(\overline{H})+1)/n$, where
$g:[1,\infty)\to\mathbb{R}$ is any convex function with $g(x)=x!$ for
$x\in[n]$.

The Sensitivity Lemma follows from Lemma 16 because the coloring with
execution traces of an algorithm $A$ for $\Pi$ is a refinement of the coloring
with $\Pi$, so every edge of the permutahedron that is bichromatic under $\Pi$
is also bichromatic under $A$, and

$s(\Pi)\doteq\mathbb{E}(\deg_{\overline{G}(\Pi)}(\rho))\leq\mathbb{E}(\deg_{\overline{H}}(\rho))\doteq\deg_{\mathrm{avg}}(\overline{H}).$

Provided $g$ is nondecreasing, it follows that $\operatorname{D}(\Pi)\geq
g(\deg_{\mathrm{avg}}(\overline{H})+1)/n\geq g(s(\Pi)+1)/n$.

In the Sensitivity Lemma we set $g(x)=\Gamma(x+1)$. An optimal (but less
elegant) choice for $g$ is the piece-wise linear function that interpolates
the prescribed values at the integral points in $[n]$, namely

$g(x)\doteq(x-\left\lfloor x\right\rfloor)\cdot(\left\lceil
x\right\rceil!)+(1-(x-\left\lfloor x\right\rfloor))\cdot(\left\lfloor
x\right\rfloor!).$

For the proof of Lemma 16 we take intuition from a similar result in the
Boolean setting [O’D14, Exercise 8.43], where the hypercube plays the role of
the permutahedron in our setting.

###### Fact 17.

Let $A$ be a query algorithm on binary strings of length $n$. Color each
vertex of the $n$-dimensional hypercube by its execution trace under $A$, and
let $\overline{H}$ denote the subgraph with the same vertex set but only
containing the bichromatic edges. Then the number of distinct execution traces
is at least $2^{\deg_{\mathrm{avg}}(H)}$.

One way to argue Fact 17 is to think of assigning a weight $w(x)$ to each
$x\in\\{0,1\\}^{n}$ so as to maximize the total weight on all inputs, subject
to the constraint that the total weight on each individual execution trace is
at most 1. Then the number of distinct execution traces must be at least the
sum of all the weights. If the weight only depends on the degree, i.e., if we
can write $w(x)=f(\deg_{\overline{H}}(x))$ for some function
$f:[0,\infty)\to\mathbb{R}$, then we can lower bound the number $k$ of
distinct execution traces as follows:

$k\geq\sum_{x}w(x)=\sum_{x}f(\deg_{\overline{H}}(x))\geq 2^{n}\cdot
f(\mathbb{E}(\deg(x)))=2^{n}\cdot f(\deg_{\mathrm{avg}}(\overline{H})),$ (1)

where the last inequality holds provided $f$ is convex.

In the Boolean setting, the set $R$ of inputs $x\in\\{0,1\\}^{n}$ with a
particular execution trace forms a subcube of dimension $n-\ell$, where $\ell$
denotes the length of the execution trace, i.e., the number of queries. Each
$x\in R$ has degree $\ell$ in $H$; this is because a change in a single
queried position results in a different execution trace, and a change in
another position does not. Therefore, a natural choice for the weight of $x\in
R$ is $w(x)=f(\ell)$ where $f(x)=1/2^{n-\ell}$. It satisfies the constraint
that the total weight on $R$ is (at most) one, and $f$ is convex. We conclude
by (1) that the number of distinct execution traces is at least $2^{n}\cdot
f(\deg_{\mathrm{avg}}(\overline{H}))=2^{\deg_{\mathrm{avg}}(\overline{H})}$,
as desired.

###### Proof of Lemma 16.

Let $k$ denote the number of distinct execution traces of $A$, and let
$R_{1},\dots,R_{k}$ denote the corresponding sets of rankings. Following a
similar strategy, we want to find a convex function
$f:[0,\infty)\to\mathbb{R}$ such that the weight function
$w(\rho)=f(\deg_{\overline{H}}(\rho))$ does not assign weight more than 1 to
any one of the sets $R_{i}$. The following claim, to be proven later, is the
crux of this.

###### Claim 18.

Let $R$ denote the set of all rankings $\rho$ that follow a particular
execution trace on $A$, and let $d\in\\{0,\dots,n-1\\}$. The number of
rankings $\rho\in R$ with $\deg_{\overline{H}}(\rho)=d$ is at most
$\frac{n!}{(d+1)!}$.

Based on Claim 18, a natural choice for $f$ is any convex function that
satisfies $f(x)=\frac{1}{n}\frac{(x+1)!}{n!}$ for $x\in\\{0,\dots,n-1\\}$. The
factor of $\frac{1}{n}$ comes from the fact that there are $n$ terms to sum
together after the weights have been normalized. For every $i\in[k]$ we then
have

$\sum_{\rho\in R_{i}}w(\rho)=\sum_{d=0}^{n-1}\left|\\{\rho\in
R_{i}\,:\,\deg_{\overline{H}}(\rho)=d\\}\right|\cdot
f(d)\leq\sum_{d=0}^{n-1}\frac{1}{n}\frac{(d+1)!}{n!}\cdot\frac{n!}{(d+1)!}=\sum_{d=0}^{n-1}\frac{1}{n}=1.$

Similar to (1) we conclude

$k\geq\sum_{i=1}^{k}\sum_{\rho\in
R_{i}}w(\rho)=\sum_{\rho}w(\rho)=\sum_{\rho}f(\deg_{\overline{H}}(\rho))\geq
n!\cdot f(\mathbb{E}(\deg_{\overline{H}}(\rho)))=n!\cdot
f(\deg_{\mathrm{avg}}(\overline{H})).$ (2)

Setting $f(x)=\frac{1}{n}\frac{g(x+1)}{n!}$ turns the requirements for $f$
into those for $g$ in the statement of the lemma, and yields that $k\geq
n!\cdot
f(\deg_{\mathrm{avg}}(\overline{H}))=g(\deg_{\mathrm{avg}}(\overline{H})+1)/n$.
∎

We now turn to proving Claim 18. The comparisons and outcomes that constitute
a particular execution trace of $A$ can be thought of as directed edges
between the items in $X$. We refer to the resulting digraph on the vertex set
$X$ as the comparison graph $C$. Since the outcomes of the comparisons are
consistent with some underlying ranking, the digraph $C$ is acyclic. The
rankings in $R$ are in one-to-one and onto correspondence with the linear
orderings of the DAG $C$. For a given ranking $\rho\in R$, the degree
$\deg_{\overline{H}}(\rho)$ equals the number of $r\in\\{2,\dots,n\\}$ such
that swapping ranks $r-1$ and $r$ in $\rho$ results in a ranking
$\rho^{\prime}=\tau\rho$ that is not in $R$, where $\tau$ denotes the
adjacent-rank transposition $(r-1,r)$. The ranking $\rho^{\prime}$ not being
in $R$ means that it is inconsistent with the combined comparisons and
outcomes of the underlying execution trace, which happens exactly when there
is a path in $C$ from the item $\rho^{-1}(r-1)$ of rank $r-1$ in $\rho$ to the
item $\rho^{-1}(r)$ with rank $r$ in $\rho$. Thus, the degree
$\deg_{\overline{H}}(\rho)$ equals the number of $r\in\\{2,\dots,n\\}$ such
that there is a path from $\rho^{-1}(r-1)$ to $\rho^{-1}(r)$ in $C$. See
Figure 5 for an illustration, where a squiggly edge $u\leadsto v$ denotes that
there exists a path from $u$ to $v$ in $C$. We only draw squiggly edges from
one position to the next, so $\deg_{\overline{H}}(\rho)$ equals the number of
squiggly edges in Figure 5.

rank$1$$2$$3$$4$$5$$\dots$$r-1$$r$$\dots$$n$$\rho^{-1}$ Figure 5: Ranking
encoding

Our strategy is to give a _compressed encoding_ of the rankings in $R$ such
that there is more compression as the number of squiggly edges increases. Our
encoding is based on the well-known algorithm to compute a linear order of a
DAG. Algorithm 1 provides pseudocode for the algorithm, which we refer to as
BuildRanking.

Algorithm 1 BuildRanking$(C)$

1:DAG $C$ on vertex set $X$

2:ranking of $X$ that is a linear order of $C$

3:$T\leftarrow\varnothing$

4:for $r=1$ to $n$ do

5: $x\leftarrow$ arbitrary element of $S\doteq\\{v\in X\;\mid\;\text{there is
no }u\in X\setminus T\text{ with }u\leadsto v\text{ in }G\\}$

6: $\rho^{-1}(r)\leftarrow x$

7: $T\leftarrow T\cup\\{x\\}$

In our formulation, BuildRanking is nondeterministic: There is a choice to
make in step 5 for each $r=1,\dots,n$. The possible executions of BuildRanking
are in one-to-one and onto correspondence with the linear orders of $C$, and
thus with the rankings in $R$.

Our encoding is a compressed description of how to make the decisions in
BuildRanking such that the output is $\rho$. Note that if
$\rho^{-1}(r-1)\leadsto\rho^{-1}(r)$, then the item $x$ with rank $r$ cannot
enter the set $S$ before iteration $r$. This is because before
$\rho^{-1}(r-1)$ is removed from $T$ at the end of iteration $r-1$, the edge
$\rho^{-1}(r-1)\leadsto\rho^{-1}(r)$ prevents $x$ from being in $S$. Thus,
whenever $\rho^{-1}(r-1)\leadsto\rho^{-1}(r)$, the item $x=\rho^{-1}(r)$ is
_lucky_ in the sense that it gets picked in step 5 as soon as it enters the
set $S$. In fact, the lucky items with respect to a ranking $\rho\in R$ are
exactly those for which $\rho^{-1}(r-1)\leadsto\rho^{-1}(r)$ for some
$r\in\\{2,\dots,n\\}$, as well as the item $\rho^{-1}(1)$ with rank 1. In
Figure 5 the lucky items are marked black. Their number equals
$\deg_{\overline{H}}(\rho)+1$.

In order to generate a ranking $\rho$ using BuildRanking, it suffices to know:

  * (a)

the lucky items (as a the set, not their relative ordering), and

  * (b)

the ordering of the non-lucky items (given which items they are).

This information suffices to make the correct choices in step 5 of Algorithm
1:

  * $\circ$

If the set $S$ contains a lucky item, there will be a unique lucky item in
$S$; pick it as the element $x$.

  * $\circ$

Otherwise, pick for $x$ the first item in the ordering of the non-lucky items
that is not yet in $T$. Such an element will exist, and all the items that
come after it in the ordering are not yet in $T$ either.

If $\rho$ has degree $d=\deg_{\overline{H}}(\rho)$, then there are $d+1$ lucky
items, so there are at most $\binom{n}{d+1}$ choices for (a), and at most
$(n-d-1)!$ choices for (b), resulting in a total of at most
$\binom{n}{d+1}\cdot(n-d-1)!=\frac{n!}{(d+1)!}$ choices. This proves Claim 18.

###### Remark 19.

Suppose we allow an algorithm $A$ to have multiple valid execution traces on a
given input $\rho$, and let $R_{i}$ denote the set of rankings on which the
$i$-th execution trace is valid. The proof of Claim 18 carries over as it
considers individually sets $R_{i}$, and only depends on the DAG that the
comparisons in $R_{i}$ induce. The rest of the proof of Lemma 16 carries
through modulo the first equality in (2), which no longer holds as the sets
$R_{i}$ may overlap. However, the equality can be replaced by the inequality
$\geq$, which does hold and is sufficient for the argument. This means that we
can replace $\operatorname{D}(\Pi)$ in the statement of the Sensitivity Lemma
by its nondeterministic variant $\operatorname{N}(\Pi)$.

##  4 Sensitivity Approach for General Trees

In this section we analyze the average sensitivity of the problem $\Pi_{T}$ of
inversion minimization on a tree $T$ with a general shape. In Section 4.1 we
show that the existence of a subtree containing a fair fraction of the leaves
implies high sensitivity. The lower bound on query complexity for $\Pi_{T}$ in
Theorem 5 then follows from the Sensitivity Lemma. In Section 4.3 we prove
that the average sensitivity measure is Lipschitz continuous. For the
analysis, we make use of the decomposition of the objective of inversion
minimization on trees mentioned earlier. We describe the decomposition in more
detail in Section 4.2; it will be helpful in later parts of this paper, as
well.

###  4.1 Subtree-induced sensitivity

$v$$\operatorname{L}(T_{v})$$\operatorname{L}(T)$ Figure 6: Subtree rooted at
$v$

We first introduce a sensitivity bound for inversion minimization based on the
size of a subtree.

###### Lemma 20 (subtree-induced sensitivity).

Consider a tree $T$ with $n\doteq\lvert\operatorname{L}(T)\rvert$ leaves, and
some node $v$ in $T$ with $\ell\doteq\lvert\operatorname{L}(T_{v})\rvert$
leaves. We have

$s(\Pi_{T})\geq\frac{\ell(n-\ell)}{n}-1.$

Note that $v$ is not necessarily a direct child of the root, as shown in Fig.
6.

We now prove Lemma 20. Let $\rho$ be a ranking of the leaves of $T$, and let
$\sigma_{\min}$ be a tree ordering that minimizes the number of inversions
with respect to $\rho$.

###### Claim 21.

$\rho$ is sensitive to the transposition $\tau=(r,r+1)$ if
$\sigma_{\min}(\rho^{-1}(r))>\sigma_{\min}(\rho^{-1}(r+1))$.

###### Proof.

If $\sigma_{\min}(\rho^{-1}(r))>\sigma_{\min}(\rho^{-1}(r+1))$, then
$\operatorname{Inv}_{\tau\rho}(\sigma_{\min})=\operatorname{Inv}_{\rho}(\sigma_{\min})-1$.
Since
$\operatorname{Inv}_{\rho}(\sigma_{\min})=\operatorname{MinInv}(T,\rho)$, this
means that $\operatorname{MinInv}(T,\tau\rho)<\operatorname{MinInv}(T,\rho)$,
or that $\rho$ is sensitive to $\tau$. ∎

In the case of general trees, a tree ordering $\sigma$ that minimizes the
number of inversions with respect to $\rho$ is difficult to find (see the
discussion on NP-hardness in Section 10). Our strategy is to find a lower
bound on the number of $r$ for which
$\sigma(\rho^{-1}(r))>\sigma(\rho^{-1}(r+1))$ that applies regardless of
$\sigma$.

###### Claim 22.

For any ordering $\sigma$, the number of $r$ such that
$\sigma(\rho^{-1}(r))>\sigma(\rho^{-1}(r+1))$ is at least one less than the
number of $s$ such that $\rho^{-1}(s)\in\operatorname{L}(T_{v})$ and
$\rho^{-1}(s+1)\not\in\operatorname{L}(T_{v})$.

###### Proof.

For all except at most one value of $s$ (the maximum $s$ for which
$\rho^{-1}(s)\in\operatorname{L}(T_{v})$), there exists a minimal
$s^{\prime}>s$ such that $\rho^{-1}(s^{\prime})\in\operatorname{L}(T_{v})$. We
claim that at least one value of $r=s,\dots,s^{\prime}-1$ satisfies
$\sigma(\rho^{-1}(r))>\sigma(\rho^{-1}(r+1))$. If not, then $\sigma$ would
rank $\rho^{-1}(s),\rho^{-1}(s+1),\dots,\rho^{-1}(s^{\prime})$ in increasing
order. Because $\sigma$ is a tree ordering, the leaves of
$\operatorname{L}(T_{v})$ must be mapped into a contiguous range by $\sigma$,
as shown in Fig. 7. However, we have
$\rho^{-1}(s),\rho^{-1}(s^{\prime})\in\operatorname{L}(T_{v})$ but
$\rho^{-1}(s+1)\not\in\operatorname{L}(T_{v})$, which violates this property
since $\sigma$ ranks a leaf outside $\operatorname{L}(T_{v})$ between two
leaves inside $\operatorname{L}(T_{v})$.

Because each value of $r$ is found between consecutive pairs of values in
$\operatorname{L}(T_{v})$, the values of $r$ are distinct. ∎

$2$$7$$v$$1$$5$$4$$6$$8$$3$$9$ (a) Leaves in $\sigma$-order, labeled with
$\rho$-ranks.

$\rho$$\sigma$$\operatorname{L}(T_{v})$$r_{1}$$r_{2}$112233445566778899$s_{1}$$s^{\prime}_{1}$$s_{2}$$s^{\prime}_{2}$
(b) Corresponding plot of $\rho,\sigma$ for each leaf.

Figure 7: $\sigma$ maps leaves of $\operatorname{L}(T_{v})$ in a contiguous
range.

###### Claim 23.

Over a uniformly random $\rho$, the expected number of $s$ such that
$\rho^{-1}(s)\in\operatorname{L}(T_{v})$ and
$\rho^{-1}(s+1)\not\in\operatorname{L}(T_{v})$ is $\frac{\ell(n-\ell)}{n}$.

###### Proof.

For $s=1,\dots,n-1$, the probability that
$\rho^{-1}(s)\in\operatorname{L}(T_{v})$ is $\frac{\ell}{n}$, and the
probability that $\rho^{-1}(s+1)\not\in\operatorname{L}(T_{v})$ given that
$\rho^{-1}(s)\in\operatorname{L}(T_{v})$ is $\frac{n-\ell}{n-1}$. Using
linearity of expectation on the indicator random variables for
$\rho^{-1}(s)\in\operatorname{L}(T_{v})$ and
$\rho^{-1}(s+1)\not\in\operatorname{L}(T_{v})$, the expected number of $s$
satisfying this property is

$(n-1)\left(\frac{\ell(n-\ell)}{n(n-1)}\right)=\frac{\ell(n-\ell)}{n}.$

∎

Combining 21, 22, and 23, we can conclude with Lemma 20.

#### Bounded degree.

We apply our analysis to the case of trees of degree $k$. Observe that for
fixed $n$, Lemma 20 is strongest when $\ell=n/2$. Not every tree $T$ has a
subtree with exactly $n/2$ leaves, but Lemma 20 still gives a useful bound for
subtrees that do not contain too few or too many leaves. In the case of trees
of bounded degree, there always exists a subtree $T_{v}$ that contains a
fairly balanced fraction of the leaves. The following quantification is
folklore. We include a proof for completeness.

###### Fact 24.

If $T$ is a tree of degree $k$ with $n$ leaves, there exists a node $v$ in $T$
such that $\ell\doteq\lvert\operatorname{L}(T_{v})\rvert=\alpha\cdot n$, where
$\frac{1}{k+1}\leq\alpha\leq\frac{k}{k+1}$.

###### Proof.

Let $r$ be the root of $T$ and construct a sequence
$v_{1}=r,v_{2},v_{3},\dots$ such that $v_{i}$ is a child of $v_{i-1}$ that
maximizes $\ell_{i}\doteq\lvert\operatorname{L}(T_{v_{i}})\rvert$, with ties
broken arbitrarily. Notice that $\\{\ell_{i}\\}$ is a decreasing sequence, and
since $T$ has degree $k$, $\ell_{i}\leq k\ell_{i+1}$ for all $i$. We claim
that some $v_{i}$ in this sequence satisfies the conditions of the claim. If
not, then for some $i$, $\ell_{i}>\frac{k}{k+1}\cdot n$ and
$\ell_{i+1}<\frac{1}{k+1}\cdot n$, which contradicts the fact that
$\ell_{i}\leq k\ell_{i+1}$. ∎

By choosing a subtree satisfying 24, we can apply Lemma 20 and conclude that
$s(\Pi_{T})\geq\frac{k}{(k+1)^{2}}\cdot n-1$. The Sensitivity Lemma then gives
the “in particular” part of Theorem 5.

###  4.2 Decomposition of the objective function

For use in this section as well as later parts of the paper, we now explain
how the objective of inversion minimization on trees decomposes. We introduce
the notion of root inversion along the way, and observe the effect of
adjacent-rank transpositions on the decomposition.

The objective $\operatorname{MinInv}(T,\rho)$ can be written as the sum of
contributions from each of the individual nodes. A node $v$ contributes those
inversions that reside in the subtree $T_{v}$ and go through the root $v$ of
$T_{v}$. We refer to them as the root inversions in $T_{v}$.

###### Definition 25 (root inversions,
$\operatorname{RInv}(\cdot,\cdot,\cdot)$,
$\operatorname{MinRInv}(\cdot,\cdot)$).

Given a tree $T$, a ranking $\rho$ of the leaves of $T$, and an ordering
$\sigma$ of $T$, a root inversion of $\sigma$ with respect to $\rho$ is an
inversion $(\ell_{1},\ell_{2})$ of $\sigma$ with respect to $\rho$ for which
the lowest common ancestor $\operatorname{LCA}(\ell_{1},\ell_{2})$ is the root
of $T$. The number of root inversions of $\sigma$ with respect to $\rho$ in
$T$ is denoted by $\operatorname{RInv}(T,\rho,\sigma)$. The minimum number of
root inversion in $T$ with respect to $\rho$ is denoted

$\operatorname{MinRInv}(T,\rho)\doteq\min_{\sigma}\operatorname{RInv}(T,\rho,\sigma),$
(3)

where $\sigma$ ranges over all possible orderings of $T$.

The only aspect of the ordering $\sigma$ of $T_{v}$ that affects
$\operatorname{RInv}(T_{v},\rho,\sigma)$ is the relative order of the children
of $v$. For a node $v$ with $k$ children $u_{1},\dots,u_{k}$, by abusing
notation and using $\sigma$ to also denote the ranking of the children induced
by the ordering of the tree, we have

$\operatorname{RInv}(T,\rho,\sigma)\doteq\sum_{1\leq i<j\leq
k}\operatorname{XInv}_{\rho}(L_{\sigma(i)},L_{\sigma(j)}),$ (4)

where $L_{i}$ is a short-hand for the leaf set $L(T_{u_{i}})$. The
contributions of the nodes can be optimized independently:

$\operatorname{MinInv}(T,\rho)=\sum_{v}\operatorname{MinRInv}(T_{v},\rho),$
(5)

where $v$ ranges over all nodes of $T$ with degree $\deg_{T}(v)>1$.

When we apply an adjacent-rank transposition $\tau$ to a ranking $\rho$, at
most one of terms in the decomposition (5) can change, and the change is at
most one unit. We capture this obervation for future reference as it will be
helpful in several sensitivity analyses.

###### Proposition 26.

Let $\rho$ be a ranking of the leaf set $X$ of a tree $T$, $\tau$ an adjacent-
rank transposition, and $\ell_{1}$ and $\ell_{2}$ be the affected leaves. Then

$\operatorname{MinRInv}(T_{v},\rho)=\operatorname{MinRInv}(T_{v},\tau\rho)$

for all nodes $v$ in $T$ except possibly
$v=\operatorname{LCA}(\ell_{1},\ell_{2})$. Moreover, the difference is at most
1 in absolute value.

###### Proof.

Since the ranks of $\ell_{1}$ and $\ell_{2}$ under $\rho$ are adjacent, for
any leaf $\ell$ other than $\ell_{1}$ and $\ell_{2}$, the relative order of
$\ell$ under $\rho$ is the same with respect to $\ell_{1}$ as it is with
respect to $\ell_{2}$. This means that the adjacent-rank transposition $\tau$
does not affect whether a pair of leaves constitutes an inversion unless that
pair equals $\\{\ell_{1},\ell_{2}\\}$. As a result, the only term on the
right-hand side of (5) that can be affected by the transposition $\tau$ is the
one corresponding to the node $v$, and it can change by at most one unit. ∎

###  4.3 Lipschitz continuity

Average-case notions typically do not change much under small changes to the
input. This is indeed the case for the average sensitivity when “small” is
interpreted as affecting few of the subtrees. The following lemma quantifies
the property and can be viewed as a form of Lipschitz continuity.

$v$$v^{*}$$\ell_{1}$$\ell_{2}$$X$$Y$ Figure 8: Effects of changing $T_{v^{*}}$

###### Lemma 27.

Given a tree $T$, if a subtree $T_{v^{*}}$ with $\ell$ leaves is replaced with
a tree $T^{\prime}_{v^{*}}$ with the same number of leaves, resulting in the
tree $T^{\prime}$, then

$|s(\Pi_{T})-s(\Pi_{T^{\prime}})|\leq\frac{\ell(\ell-1)}{n}.$

###### Proof.

We think of the leaf sets of $T$ and $T^{\prime}$ as being the same set
$X=\operatorname{L}(T)=\operatorname{L}(T^{\prime})$, and fix a ranking $\rho$
of $X$. Consider an ordering of $T$ and the ranking $\sigma$ of $X$ that it
induces. Outside of $T^{\prime}_{v^{*}}$ we can order $T^{\prime}$ in the same
way as $T$. Irrespective of how we order $T^{\prime}$ inside
$T^{\prime}_{v^{*}}$, the induced ranking $\sigma^{\prime}$ of $X$ agrees with
$\sigma$ on all leaves in $X$ except possibly those in
$Y\doteq\operatorname{L}(T_{v^{*}})=\operatorname{L}(T^{\prime}_{v^{*}})$.
Moreover, under both $\sigma$ and $\sigma^{\prime}$, the set $Y$ gets mapped
to the same contiguous interval. It follows that for all pairs
$(\ell_{1},\ell_{2})$ of distinct leaves of which at least one lies outside of
$Y$, $(\ell_{1},\ell_{2})$ constitutes an inversion of $\sigma$ with respect
to $\rho$ if and only if $(\ell_{1},\ell_{2})$ constitutes an inversion of
$\sigma^{\prime}$ with respect to $\rho$. For any node $v$ outside of
$T_{v^{*}}$, root inversions in $T_{v}$ cannot involve leaves that are both in
$Y\doteq\operatorname{L}(T_{v^{*}})$. See Figure 8 for an illustration. Thus,
for such nodes $v$,
$\operatorname{RInv}(T_{v},\rho,\sigma)=\operatorname{RInv}(T^{\prime}_{v},\rho,\sigma^{\prime})$.
By taking the minimum over all orderings, we conclude:

###### Claim 28.

$\operatorname{MinRInv}(T_{v},\rho)=\operatorname{MinRInv}(T^{\prime}_{v},\rho)$
holds for every node $v$ outside of $T_{v^{*}}$ (or equivalently, outside of
$T^{\prime}_{v^{*}}$).

Consider a ranking $\rho$ and an adjacent-rank transposition $\tau=(r,r+1)$.
We claim that, unless
$(\ell_{1},\ell_{2})\doteq(\rho^{-1}(r),\rho^{-1}(r+1))\in Y\times Y$,
$\Pi_{T}$ is sensitive to $\tau$ at $\rho$ if and only if $\Pi_{T^{\prime}}$
is sensitive to $\tau$ at $\rho$. This is because by Proposition 26 the only
term in the decomposition (5) of $\operatorname{MinInv}(T,\rho)$ that can be
affected by $\tau$ is the contribution $\operatorname{MinRInv}(T_{v},\rho)$
for $v=\operatorname{LCA}(\ell_{1},\ell_{2})$. If at least one of $\ell_{1}$
or $\ell_{2}$ is not inside $T_{v^{*}}$, then $v$ is not inside $T_{v^{*}}$
either, so by Claim 28,
$\operatorname{MinRInv}(T_{v},\rho)=\operatorname{MinRInv}(T^{\prime}_{v},\rho)$.
By the same token,
$\operatorname{MinRInv}(T_{v},\tau\rho)=\operatorname{MinRInv}(T^{\prime}_{v},\tau\rho)$.
It follows that
$\operatorname{MinInv}(T,\rho)\neq\operatorname{MinInv}(T,\tau\rho)$ if and
only if
$\operatorname{MinInv}(T^{\prime},\rho)\neq\operatorname{MinInv}(T^{\prime},\tau\rho)$.

We bound the expected number of values of $r$ for which
$(\rho^{-1}(r),\rho^{-1}(r+1))\in Y\times Y$ with
$Y\doteq\operatorname{L}(T_{v})$ when $\rho$ is chosen uniformly at random.
For $r\in[n-1]$, the probability that $\rho^{-1}(r)\in Y$ is $\frac{\ell}{n}$,
and the probability that $\rho^{-1}(r+1)\in Y$ given that $\rho^{-1}(r)\in Y$
is $\frac{\ell-1}{n-1}$. Using linearity of expectation on the indicators, the
expected number of said $r$ is

$(n-1)\left(\frac{\ell(\ell-1)}{n(n-1)}\right)=\frac{\ell(\ell-1)}{n}.$

∎

Lemma 27 helps to extend query lower bounds based on average sensitivity to
larger classes. Suppose we have established a good lower bound on the
sensitivity $s(\Pi_{T})$ for a class $C$ of trees. Consider a class
$C^{\prime}$ obtained by taking a tree $T$ in class $C$ and replacing some of
the subtrees $T_{v}$ by other subtrees $T^{\prime}_{v}$ on the same number of
leaves. For this new class $C^{\prime}$ the same lower bound on the
sensitivity of inversion minimization applies modulo the Lipschitz loss. For
example, Theorem 6 holds by virtue of a lower bound of the form
$s(\Pi_{T})\geq(n-1)-c\log(n)$ for every binary tree $T$ with $n$ leaves,
where $c$ is a universal constant. If we allow some of the subtrees of $T$ to
be replaced by, say freely arrangeable ones on the same leaves, applying Lemma
27 for each of the modified subtrees in sequence shows that the resulting new
tree $T^{\prime}$ has

$s(\Pi_{T^{\prime}})\geq s(\Pi_{T})-\frac{\alpha n(\alpha
n-1)}{n}\geq(n-1)-c\log(n)-\alpha^{2}(n-1)=(1-\alpha^{2})(n-1)-c\log(n),$

where $\alpha$ denotes the fraction of leaves that belong to one of the
replaced subtrees.

In fact, the notion of average sensitivity is robust with respect to the
following, more refined type of surgery. From any tree $T$, let $R$ be a
connected subset of $T$ that includes no leaves. Let $T^{\prime}$ be the
subtree rooted at the LCA of $R$ ($T^{\prime}$ contains all of $R$), and let
$T^{\prime}_{1},\dots,T^{\prime}_{k}$ be the disjoint maximal subtrees of
$T^{\prime}$ that are strictly below $R$. Let $R^{\prime}$ be any tree that
has $k$ leaves. Replace $T^{\prime}$ by $R^{\prime}$, and then replace the
leaves of $R^{\prime}$ by $T^{\prime}_{1},\dots,T^{\prime}_{k}$.

The effect is that the region $R$ has been “reshaped” to look like
$R^{\prime}$, but the rest of $T$ is unaffected. The cost of such a surgery is
at most $(n-1)$ times the probability that a uniformly random pair of distinct
leaves has their LCA in $R$. The bound follows from thinking of sensitivity as
$(n-1)$ times the probability that a uniformly random edge in the full
permutahedron is bichromatic. Provided the LCA of the affected leaves is
outside $R$, then we get sensitivity before the surgery if and only if we get
it after the surgery. Surgeries can be iterated, and the costs accumulate
additively. In combination with our strong lower bound on the average
sensitivity of binary trees (Lemma 35), this allows for a robust sense in
which “mostly-binary” trees have high average sensitivity.

##  5 Refined Sensitivity Approach for Binary Trees

In this section we show how to refine the sensitivity approach for lower
bounds on the query complexity of the problem $\Pi_{T}$ of inversion
minimization on trees in the important special case of binary trees $T$. In
Section 5.1 we first develop a criterion for when a particular ranking $\rho$
is sensitive to a particular adjacent-rank transposition $\tau$. We then
analyze the root sensitivity of binary trees in Section 5.2 and finally
establish a strong lower bound on the average sensitivity in Section 5.3. An
application of the Sensitivity Lemma then yields Theorem 6.

###  5.1 Sensitivity criterion

Recall the decomposition of the objective function
$\operatorname{MinInv}(T,\rho)$ into contributions attributed to each node $v$
of degree $\deg_{T}(v)>1$, as given by (5) in Section 4.2. In the case of
binary trees, the contribution of node $v$ can be calculated simply as

$\operatorname{MinRInv}(T_{v},\rho)=\min(\operatorname{XInv}_{\rho}(L_{1},L_{2}),\operatorname{XInv}_{\rho}(L_{2},L_{1})),$
(6)

where $u_{1}$ and $u_{2}$ denote the two children of $v$, and
$L_{1}\doteq\operatorname{L}(T_{u_{1}})$ and
$L_{2}\doteq\operatorname{L}(T_{u_{2}})$ their leaf sets. This simplicity
makes a precise analysis of sensitivity feasible, as we will see next.

For a given ranking $\rho$ of $T$ and a given adjacent-rank transposition
$\tau$, we would like to figure out the effect of $\tau$ on the objective
$\operatorname{MinInv}(T,\cdot)$, in particular when
$\operatorname{MinInv}(T,\tau\rho)=\operatorname{MinInv}(T,\rho)$. Let
$\ell_{\mathrm{lo}}$ and $\ell_{\mathrm{hi}}$ denote the two leaves that are
affected by the transposition $\tau$ on the ranking $\rho$, where the
subscript “$\mathrm{lo}$” indicates the lower of the two leaves with respect
to $\rho$, and “$\mathrm{hi}$” the higher of the two. Let $v$ be the lowest
common ancestor $\operatorname{LCA}(\ell_{\mathrm{lo}},\ell_{\mathrm{hi}})$.
We use the same subscripts “$\mathrm{lo}$” and “$\mathrm{hi}$” for the two
children of $v$: $u_{\mathrm{lo}}$ denotes the child whose subtree contains
$\ell_{\mathrm{lo}}$, and $u_{\mathrm{hi}}$ its sibling. Similarly, we denote
by $L_{\mathrm{lo}}$ the leaf set of $T_{u_{\mathrm{lo}}}$, and by
$L_{\mathrm{hi}}$ the leaf set of $T_{u_{\mathrm{hi}}}$. See Figure 9 for the
subsequent analysis.

$v$$u_{\mathrm{lo}}$$u_{\mathrm{hi}}$$\ell_{\mathrm{lo}}$$\ell_{\mathrm{hi}}$$L_{\mathrm{lo}}$$L_{\mathrm{hi}}$$L_{\mathrm{lo}}=\\{\ell_{\mathrm{lo}}\\}\sqcup
A$$A=A_{<}\sqcup
A_{>}$$\rho(A_{<})<\rho(\ell_{\mathrm{lo}})<\rho(A_{>})$$L_{\mathrm{hi}}\doteq\\{\ell_{\mathrm{hi}}\\}\sqcup
B$$B=B_{<}\sqcup B_{>}$$\rho(B_{<})<\rho(\ell_{\mathrm{hi}})<\rho(B_{>})$
Figure 9: Sensitivity analysis for binary trees

By Proposition 26, the situation before and after the application of $\tau$ is
as follows, where
$x\doteq\operatorname{XInv}_{\rho}(L_{\mathrm{lo}},L_{\mathrm{hi}})$ and
$y\doteq\operatorname{XInv}_{\rho}(L_{\mathrm{hi}},L_{\mathrm{lo}})$.

$\begin{array}[]{c|cc|c}\text{ranking}&\operatorname{RInv}(T_{v},\cdot,\sigma(\ell_{\mathrm{lo}})<\sigma(\ell_{\mathrm{hi}}))&\operatorname{RInv}(T_{v},\cdot,\sigma(\ell_{\mathrm{hi}})<\sigma(\ell_{\mathrm{lo}}))&\operatorname{MinRInv}(T_{v},\cdot)\\\
\hline\cr\rho&x&y&\min(x,y)\\\ \tau\rho&y-1&x+1&\min(y-1,x+1)\end{array}$

The objective function remains the same iff $\min(x,y)=\min(y-1,x+1)$, which
happens iff $x-y=-1$, or equivalently iff

$\operatorname{DInv}_{\rho}(L_{\mathrm{lo}},L_{\mathrm{hi}})=\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},\\{\ell_{\mathrm{hi}}\\}),$
(7)

where we introduce the following short-hand:

###### Definition 29 (cross inversion difference,
$\operatorname{DInv}_{\cdot}(\cdot,\cdot)$).

For a ranking $\rho$ of a set $X$, and two subsets $A,B\subseteq X$,

$\operatorname{DInv}_{\rho}(A,B)\doteq\operatorname{XInv}_{\rho}(A,B)-\operatorname{XInv}_{\rho}(B,A).$

We can split $L_{\mathrm{lo}}$ as
$L_{\mathrm{lo}}=\\{\ell_{\mathrm{lo}}\\}\sqcup
A=A_{<}\sqcup\\{\ell_{\mathrm{lo}}\\}\sqcup A_{>}$, where $A_{<}$ contains all
leaves in $L_{\mathrm{lo}}$ that $\rho$ ranks before $\ell_{\mathrm{lo}}$, and
$A_{>}$ contains all the leaves in $L_{\mathrm{lo}}$ that $\rho$ ranks after
$\ell_{\mathrm{lo}}$. We similarly split $L_{\mathrm{hi}}$, as indicated in
Figure 9. We have that

$\operatorname{DInv}_{\rho}(L_{\mathrm{lo}},L_{\mathrm{hi}})=\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},\\{\ell_{\mathrm{hi}}\\})+\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},B)+\operatorname{DInv}_{\rho}(A,\\{\ell_{\mathrm{hi}}\\})+\operatorname{DInv}_{\rho}(A,B).$

Since the ranks of $\ell_{\mathrm{lo}}$ and $\ell_{\mathrm{hi}}$ under $\rho$
are adjacent, we have that
$\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},B)=|B_{<}|-|B_{>}|$ and
$\operatorname{DInv}_{\rho}(A,\\{\ell_{\mathrm{hi}}\\})=|A_{>}|-|A_{<}|$.
Plugging everything into (7) we conclude:

###### Proposition 30.

Let $T$ be a binary tree, $\rho$ a ranking of the leaves of $T$, $\tau$ an
adjacent-rank transposition, $\ell_{\mathrm{lo}}$ and $\ell_{\mathrm{hi}}$ the
two leaves affected by $\tau$ under $\rho$ such that $\rho$ ranks
$\ell_{\mathrm{lo}}$ before $\ell_{\mathrm{hi}}$. Referring to the notation in
Figure 9, we have that

$\displaystyle\operatorname{MinInv}(T,\rho)=\operatorname{MinInv}(T,\tau\rho)$
$\displaystyle\Leftrightarrow\operatorname{DInv}_{\rho}(L_{\mathrm{lo}},L_{\mathrm{hi}})=\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},\\{\ell_{\mathrm{hi}}\\})$
(8)
$\displaystyle\Leftrightarrow\operatorname{DInv}_{\rho}(A,B)=|A_{<}|-|A_{>}|+|B_{>}|-|B_{<}|.$
(9)

###  5.2 Root sensitivity

Given a ranking $\rho$ and an adjacent-rank transposition $\tau$, we know by
Proposition 26 that at most one of the terms in the decomposition (5) of
$\operatorname{MinInv}(T,\rho)$ is affected by the transposition, namely
$\operatorname{MinRInv}(T_{v},\rho)$ where $v$ is the lowest common ancestor
of the affected leaves $\ell_{\mathrm{lo}}$ and $\ell_{\mathrm{hi}}$. It
follows that we can write the average sensitivity of
$\Pi_{T}\doteq\operatorname{MinInv}(T,\cdot)$ as the following convex
combination:

$\displaystyle s(\Pi_{T})$
$\displaystyle=(n-1)\cdot\mathbb{P}[\operatorname{MinInv}(T,\rho)\neq\operatorname{MinInv}(T,\tau\rho)]$
$\displaystyle=(n-1)\sum_{v}\mathbb{P}[v=\operatorname{LCA}(\ell_{\mathrm{lo}},\ell_{\mathrm{hi}})]\cdot\mathbb{P}[\operatorname{MinRInv}(T_{v},\rho)\neq\operatorname{MinRInv}(T_{v},\tau\rho)\,|\,v=\operatorname{LCA}(\ell_{\mathrm{lo}},\ell_{\mathrm{hi}})],$
(10)

where the probability is over a uniformly random choice of the ranking $\rho$
and the adjacent-rank transposition $\tau$, and $\ell_{\mathrm{lo}}$ and
$\ell_{\mathrm{hi}}$ denote the affected leaves. The conditional probability
on the right-hand side of (5.2) only depends on the subtree $T_{v}$. The
ranking $\rho$ of all leaves induces a ranking $\rho^{\prime}$ of the leaves
of $T_{v}$ that is uniform under the conditioning. Similarly, the adjacent-
rank transposition $\tau$ for $\rho$ induces an adjacent-rank transposition
$\tau^{\prime}$ for $\rho^{\prime}$; the distribution of $\tau^{\prime}$ under
the conditioning is independent of $\rho^{\prime}$ and uniform among all
adjacent-rank transpositions such that the affected leaves live in subtrees of
different children of $v$. Thus, the probability on the right-hand side of
(5.2) coincides with the following notion for the subtree $T_{v}$.

###### Definition 31 (root sensitivity).

Let $T$ be a tree. The _root sensitivity_ of $T$ is the probability that
$\operatorname{MinRInv}(T_{v},\rho)\neq\operatorname{MinRInv}(T_{v},\tau\rho)$
when $\rho$ is a uniform random ranking of $\operatorname{L}(T)$, and $\tau$ a
uniform random adjacent transposition with the condition that the affected
leaves are in subtrees of different children of the root of $T$.

Note that the only nodes $v$ that need to be considered in the sum on the
right-hand side of (5.2) are those that can appear as lowest common ancestor
of two leaves, and such that $T_{v}$ is not freely arrangeable. In the case of
binary trees, this means that we only need to consider nodes $v$ of degree 2
such that $T_{v}$ contains more than 2 leaves. In this section we prove a
strong lower bound on the root sensitivity of such trees $T_{v}$.

Consider the binary tree $T$ with root $v$ in Figure 9. The distribution
underlying Definition 31 can be generated as follows: Pick a leaf on each side
of the root $v$ uniformly at random, and let $\rho$ be a ranking of the leaves
of $T$ that is uniform random with the condition that the selected leaves
receive adjacent ranks; $\tau$ then is the adjacent-rank transposition that
swaps the two selected leaves. The root sensitivity of $T$ is the complement
of the probability that the right-hand side of (9) holds under this
distribution. Let us analyze the left-hand side of (9) further. As
$A=A_{<}\sqcup A_{>}$ and $B=B_{<}\sqcup B_{>}$, we have that

$\operatorname{DInv}_{\rho}(A,B)=\operatorname{DInv}_{\rho}(A_{<},B_{<})+\operatorname{DInv}_{\rho}(A_{<},B_{>})+\operatorname{DInv}_{\rho}(A_{>},B_{<})+\operatorname{DInv}_{\rho}(A_{>},B_{>}).$

By the defining properties of the sets involved (see Figure 9), we know that
$\operatorname{DInv}_{\rho}(A_{<},B_{>})=-a_{<}\,b_{>}$ and
$\operatorname{DInv}_{\rho}(A_{>},B_{<})=a_{>}\,b_{<}$, where
$a_{<}\doteq|A_{<}|$, $a_{>}\doteq|A_{>}|$, $b_{<}\doteq|B_{<}|$, and
$b_{>}\doteq|B_{>}|$. Thus, we can rewrite criterion (9) as:

$\operatorname{DInv}_{\rho}(A_{<},B_{<})+\operatorname{DInv}_{\rho}(A_{>},B_{>})=a_{<}\,b_{>}-a_{>}\,b_{<}+a_{<}-a_{>}+b_{>}-b_{<}.$
(11)

A critical observation that helps us to bound the probability of (11) is that,
conditioned on all four values $a_{\cdot}$ and $b_{\cdot}$, the right-hand
side of (11) is fixed, but the left-hand side still contains a lot of
randomness. In fact, under the conditioning stated, the ranking that $\rho$
induces on $A_{<}\sqcup B_{<}$ is still distributed uniformly at random, the
same holds for the ranking that $\rho$ induces on $A_{>}\sqcup B_{>}$, and
both distributions are independent. This means that, under the same
conditioning, the left-hand side of (11) has the same distribution as the sum
$X_{a_{<},b_{<}}+X_{a_{>},b_{>}}$ of two independent random variables of the
following type:

###### Definition 32 (cross inversion distribution, $X_{\cdot,\cdot}$).

For nonnegative integers $a$ and $b$, $X_{a,b}$ denotes the random variable
$\operatorname{XInv}(A,B)$ that counts the number of cross inversions from $A$
to $B$, where $A$ is an array of length $a$, $B$ an array of length $b$, and
the concatenation $AB$ is a random permutation of $[a+b]$.

In Section 9 we establish the following upper bound on the probability that
the number of cross inversions takes on any specific value.

###### Lemma 33.

There exists a constant $C$ such that for all integers $a,b\geq 1$ and $0\leq
k\leq ab$,

$\mathbb{P}[X_{a,b}=k]\leq\frac{C}{\sqrt{ab(a+b)}}.$ (12)

Using Lemma 33 we can establish an upper bound of the same form as the right-
hand side of (12) for the probability that (11) holds: For some constant
$C^{\prime}$

$\mathbb{P}[X_{a_{<},b_{<}}+X_{a_{>},b_{>}}=a_{<}\,b_{>}-a_{>}\,b_{<}+a_{<}-a_{>}+b_{>}-b_{<}]\leq\frac{C^{\prime}}{\sqrt{ab(a+b)}},$
(13)

where $a\doteq a_{<}+a_{>}\geq 1$ and $b\doteq b_{<}+b_{>}\geq 1$. We consider
several cases based on the relative sizes of $a_{<}$ vs $a_{>}$, and $b_{<}$
vs $b_{>}$.

  * (i)

In case both $a_{<}\geq\eta a$ and $b_{<}\geq\eta b$, the bound (13) follows
from (12) as long as $C^{\prime}\geq C/\eta^{3/2}$.

  * (ii)

By reverting the order in (i), the same holds true in case both $a_{>}\geq\eta
a$ and $b_{>}\geq\eta b$.

  * (iii)

In case $a_{>}\leq\eta a$ and $b_{<}\leq\eta b$, the left-hand side of (11) is
at most $2\eta ab$, whereas the right-hand side is at least

$(1-\eta)^{2}ab-\eta^{2}ab+(1-\eta)a-\eta a+(1-\eta)b-\eta
b=(1-2\eta)(ab+a+b).$

As long as $2\eta\leq 1-2\eta$, or equivalently, $\eta\leq 1/4$, this case
cannot occur.

  * (iv)

By reverting the role of $A$ and $B$ in (iii), the same holds true in case
$b_{>}\leq\eta b$ and $a_{<}\leq\eta a$.

As long as $\eta\leq 1/2$, it holds that either $a_{<}\geq\eta a$ or
$a_{>}\geq\eta a$, and either $b_{<}\geq\eta b$ or $b_{>}\geq\eta b$.
Distributing the “and” over the “or”, we obtain the four cases we considered,
which are therefore exhaustive. We conclude that (13) holds for
$C^{\prime}=4^{3/2}C$ whenever $a\doteq|A|\geq 1$ and $b\doteq|B|\geq 1$.

In the case where $a=0$ and $b\geq 1$, the right-hand side of (9) vanishes, as
do $|A_{<}|$ and $|A_{>}|$, so (9) holds if and only if $|B_{<}|=|B_{>}|$, or
equivalently, the leaf $\ell_{\mathrm{hi}}$ is ranked exactly in the middle of
the leaf set $L_{\mathrm{hi}}$. As the ranking $\rho$ is chosen uniformly at
random, this happens with probability $1/(b+1)$ where
$b\doteq|B|=|L_{\mathrm{hi}}|-1$. The case where $a\geq 1$ and $b=0$ is
symmetric. The remaining case, $a=b=0$, is one we do not need to consider as
the tree $T$ then only has two leaves. In all other cases we obtain a strong
upper bound on the probability that (9) holds, and by complementation a strong
lower bound on the root sensitivity. We capture the lower bound in the
following single expression that holds for all cases under consideration.

###### Lemma 34.

There exists a constant $c$ such that for every binary tree $T$ with at leaves
3 leaves and a root of degree 2, the root sensitivity of $T$ is at least

$1-\frac{c}{\sqrt{n_{1}n_{2}(n_{1}+n_{2})}},$ (14)

where $n_{1}$ and $n_{2}$ denote the number of leaves in the subtrees rooted
by the two children of the root.

###  5.3 Average sensitivity

We are now ready to establish that, except for trivial cases, the average
sensitivity of a binary tree is close to maximal. The trivial cases are those
where the tree has at most two leaves, in which case the sensitivity is zero.

###### Lemma 35.

The average sensitivity of $\Pi_{T}$ for binary trees $T$ with $n\geq 2$
leaves is $n-O(1)$.

###### Proof.

We use the expression (5.2) for the average sensitivity of $\Pi_{T}$, where
$v$ ranges over all nodes of degree 2 such that $T_{v}$ contains as least two
leaves. Consider a node $v$ of degree 2 such that $T_{v}$ contains $n_{v,1}$
leaves one one side and $n_{v,2}$ leaves on the other side, where
$n_{v,1}+n_{v,2}\geq 3$. If we choose the ranking $\rho$ and the adjacent-rank
transposition $\tau$ uniformly at random, each of the $\binom{n}{2}$ pairs of
leaves are equally likely to be the affected pair. As there are $n_{v,1}\cdot
n_{v,2}$ choices that result in $v$ as their lowest common ancestor, we have
that
$\mathbb{P}[v=\operatorname{LCA}(\ell_{\mathrm{lo}},\ell_{\mathrm{hi}})]=\frac{2n_{v,1}n_{v,2}}{n(n-1)}$.
Combining this with the root sensitivity lower bound given by (14), we have
that

$\displaystyle s(\Pi_{T})$
$\displaystyle\geq(n-1)\sum_{v}\frac{2n_{v,1}n_{v,2}}{n(n-1)}\cdot\left(1-\frac{c}{\sqrt{n_{v,1}n_{v,2}(n_{v,1}+n_{v,2})}}\right)$
$\displaystyle=(n-1)-\frac{2c}{n}\sum_{v}\sqrt{\frac{n_{v,1}n_{v,2}}{n_{v,1}+n_{v,2}}}.$

The following claim then completes the proof. ∎

###### Claim 36.

There is a constant $c^{\prime}$ such that for all binary trees $T$ with $n$
leaves

$\sum_{v}\sqrt{\frac{n_{v,1}n_{v,2}}{n_{v,1}+n_{v,2}}}\leq c^{\prime}n,$ (15)

where the sum ranges over all nodes $v$ of degree 2 such that $T_{v}$ contains
at least 3 leaves.

###### Proof of Claim 36.

We use structural induction to prove a somewhat stronger claim, namely that

$\sum_{v}\sqrt{\frac{n_{v,1}n_{v,2}}{n_{v,1}+n_{v,2}}}\leq
c^{\prime}n-d^{\prime}\sqrt{n}$ (16)

for some constants $c^{\prime}$ and $d^{\prime}$ to be determined. As the base
case we consider binary trees $T$ with at most two leaves. In this case, the
left-hand side of (16) is zero and the right-hand side is non-negative
provided $c^{\prime}\geq d^{\prime}$, so (16) holds.

For the inductive step, the case where the root of $T$ has degree 1
immediately follows from the inductive hypothesis for the subtree $T_{u}$
rooted by the child $u$ of the root of $T$. The remaining case is where the
root of $T$ has degree 2. Let $u_{1}$ and $u_{2}$ be the two children for the
root, $n_{1}=\lvert\operatorname{L}(T_{u_{1}})\rvert$, and
$n_{2}=\lvert\operatorname{L}(T_{u_{2}})\rvert$. The sum on the left-hand side
of (16) has three contributions: $\sqrt{\frac{n_{1}n_{2}}{n_{1}+n_{2}}}$ from
the root, and the contributions from $T_{u_{1}}$ and $T_{u_{2}}$, to which we
can individually apply the inductive hypothesis. This gives us an upper bound
of

$\sqrt{\frac{n_{1}n_{2}}{n_{1}+n_{2}}}+(c^{\prime}n_{1}-d^{\prime}\sqrt{n_{1}})+(c^{\prime}n_{2}-d^{\prime}\sqrt{n_{2}})=\sqrt{\frac{n_{1}n_{2}}{n_{1}+n_{2}}}+c^{\prime}(n_{1}+n_{2})-d^{\prime}(\sqrt{n_{1}}+\sqrt{n_{2}}),$

which we want to upper bound by

$c^{\prime}n-d^{\prime}\sqrt{n}=c^{\prime}(n_{1}+n_{2})-d^{\prime}\sqrt{n_{1}+n_{2}}.$

Writing $n_{1}=\alpha n$ for some $\alpha\in[0,1]$ and rearranging terms, the
upper bound holds if and only if

$\sqrt{\alpha(1-\alpha)}\leq d^{\prime}(\sqrt{\alpha}+\sqrt{1-\alpha}-1).$

We claim that the upper bound holds for $d^{\prime}=(\sqrt{2}+1)/2$. Let

$F(\alpha)\doteq
d^{\prime}(\sqrt{\alpha}+\sqrt{1-\alpha}-1)-\sqrt{\alpha(1-\alpha)}.$

It suffices to show that $F(\alpha)\geq 0$. Since $F$ is continuous on
$[0,1]$, it attains a minimum on $[0,1]$. On $(0,1)$, $F$ is differentiable.
It can be verified that $F^{\prime}$ has a unique zero in $(0,1/2)$, which
needs to be a maximum as $F$ is increasing at $\alpha=0$. By the symmetry
$F(\alpha)=F(1-\alpha)$, it follows that the minimum of $F$ on $[0,1]$ is
attained at the midpoint $\alpha=1/2$ or at one of the endpoint $\alpha=0$ or
$\alpha=1$. At all three points $F(\alpha)=0$. We conclude that (16) holds for
any constants $d^{\prime}\geq(\sqrt{2}+1)/2$ and $c^{\prime}\geq d^{\prime}$.

∎

##  6 Sensitivity Approach for Bounded Error

In this section, we apply the sensitivity approach to obtain lower bounds on
the query complexity of problems in the comparison-query model against
randomized algorithms with bounded error. We derive a generic result that
query lower bounds against deterministic algorithms that are based on the
Sensitivity Lemma, also hold against bounded-error randomized algorithms with
a small loss in strength. The approach works particularly well when we have
linear lower bounds on the average sensitivity, in which case there is only a
constant-factor loss in the strength of the query lower bound. Among others,
this applies to the $\Omega(n\log n)$ query lower bound for inversion
minimization on trees of bounded degree.

#### Generic lower bound.

Our approach is based on Yao’s minimax principle [Yao77], which lower bounds
worst-case complexity against randomized algorithms with bounded error by
average-case complexity against deterministic algorithms with bounded
distributional error. We view a deterministic algorithm with small
distributional error for a problem $\Pi$ as an exact deterministic algorithm
for a slightly modified problem $\Pi^{\prime}$. The idea is to then apply the
sensitivity approach to $\Pi^{\prime}$, and capitalize on the closeness of the
average sensitivities of $\Pi$ and $\Pi^{\prime}$ to obtain a lower bound in
terms of the sensitivity of $\Pi$. By using the Sensitivity Lemma as a black-
box, the approach yields a lower bound on the query complexity of bounded-
error algorithms that is worst-case with respect to the input and with respect
to the randomness, i.e., the lower bound holds for some input and some
computation path on that input. By delving into the proof of the Sensitivity
Lemma, we are able to obtain a lower bound that is worst-case with respect to
the input but average-case with respect to the randomness, i.e., the lower
bound holds for the expected number of queries on some input.111In fact, the
approach yields a lower bound that is average-case with respect to the input
(chosen uniformly at random) as well as the randomness. This follows because
the proof of Yao’s minimax principle allows us to replace the left-hand side
of (17) by the average of the expected number of queries with respect to the
distribution $\operatorname{\mathcal{D}}$, which we pick to be uniform in our
application of the principle.

We first define the notions of randomized complexity and distributional
complexity.

###### Definition 37 (randomized query complexity,
$\operatorname{RQ}_{\cdot}(\cdot)$, and distributional query complexity,
$\operatorname{DistQ}_{\cdot}(\cdot,\cdot)$).

Let $\Pi$ be a problem in the comparison-query model and
$\varepsilon\in[0,1]$.

A randomized algorithm $R$ for $\Pi$ is said to have error $\varepsilon$ if on
every input $\rho$, the algorithm outputs $\Pi(\rho)$ with probability at
least $1-\varepsilon$. The query complexity of $R$ is the maximum, over all
inputs $\rho$, of the expected number of queries that $R$ makes on input
$\rho$. The _$\varepsilon$ -error randomized query complexity_ of $\Pi$,
denoted $\operatorname{RQ}_{\varepsilon}(\Pi)$, is the minimum query
complexity of $R$ over all $\varepsilon$-error randomized algorithms $R$ for
$\Pi$.

Let $\operatorname{\mathcal{D}}$ be a probability distribution on the inputs
$\rho$. A deterministic algorithm $A$ for $\Pi$ has error $\varepsilon$ with
respect to $\operatorname{\mathcal{D}}$ if the probability that
$A(\rho)=\Pi(\rho)$ is at least $1-\varepsilon$ where the input $\rho$ is
chosen according to $\operatorname{\mathcal{D}}$. The query complexity of $A$
with respect to $\operatorname{\mathcal{D}}$ is the expected number of queries
that $A$ makes on input $\rho$ when $\rho$ is chosen according to
$\operatorname{\mathcal{D}}$. The _$\varepsilon$ -error distributional query
complexity_ of $\Pi$ with respect to $\operatorname{\mathcal{D}}$, denoted
$\operatorname{DistQ}_{\varepsilon}(\Pi,\operatorname{\mathcal{D}})$, is the
minimum query complexity of $A$ with respect to $\operatorname{\mathcal{D}}$
over all deterministic algorithms $A$ for $\Pi$ that have error $\varepsilon$
with respect to $\operatorname{\mathcal{D}}$.

The relationship between randomized complexity and distributional complexity
is described by Yao’s principle.

###### Lemma 38 (Yao’s minimax principle [Yao77]).

Let $\Pi$ be a problem in the comparison-query model, $\varepsilon\in[0,1/2]$,
and $\operatorname{\mathcal{D}}$ a distribution on the inputs $\rho$.

$\operatorname{RQ}_{\varepsilon}(\Pi)\geq\frac{1}{2}\operatorname{DistQ}_{2\varepsilon}(\Pi,\operatorname{\mathcal{D}}).$
(17)

We now prove lower bounds on the distributional query complexity, and thus on
randomized query complexity, of comparison-query problems $\Pi$ based on
average sensitivity bounds. For these bounds, we always set
$\operatorname{\mathcal{D}}$ to be the uniform distribution, the distribution
underlying the notion of average sensitivity.

We start by studying average-case query complexity, i.e., zero-error
distributional query complexity, and its relationship to the average
sensitivity. We follow a strategy similar to the one in the proof of the
Sensitivity Lemma. Whereas a bound on deterministic complexity
$\operatorname{Q}$ follows purely from the number of execution traces
$\operatorname{D}$, here, the execution traces are weighted by their depth and
their probability of occurring.

Recall that $g$ in the statement of the Strong Sensitivity Lemma denotes any
convex function $g:[1,\infty)\to\mathbb{R}$ with $g(x)=x!$ for $x\in[n]$; for
deriving the Sensitivity Lemma from the Strong Sensitivity Lemma we also need
$g$ to be nondecreasing. One such function is $g(x)=\Gamma(x+1)$. To prove a
lower bound on the zero-error distributional complexity, we need the function
$g$ to be not only convex, but _log-convex_ , i.e., $\log_{2}g(x)$ needs to be
convex. The function $g(x)=\Gamma(x+1)$ satisfies this constraint, as well.

###### Proposition 39.

Let $\Pi$ be a problem in the comparison-query model with $n$ items,
$\operatorname{\mathcal{D}}$ the uniform distribution on the inputs $\rho$,
and $g:[1,\infty)\to\mathbb{R}$ a nondecreasing log-convex function with
$g(x)=x!$ for $x\in[n]$.

$\operatorname{DistQ}_{0}(\Pi,\operatorname{\mathcal{D}})\geq\log_{2}(g(s(\Pi)+1)/n)$

###### Proof.

Let $k$ be the number of distinct execution traces of a deterministic
algorithm $A$ for $\Pi$, and let $R_{1},\dots,R_{k}$ denote the corresponding
sets of rankings. Interpreting $A$ as a binary decision tree, let $0pt(R_{i})$
be the depth of the execution trace corresponding to $R_{i}$. By Kraft’s
inequality,

$\sum_{i=1}^{k}2^{-0pt(R_{i})}\leq 1.$

Let $f(x)=\frac{1}{n}\frac{g(x+1)}{n!}$ and define the weight function
$w(\rho)=f(\deg_{\overline{H}}(\rho))$, where $\overline{H}$ refers to the
notation of the Strong Sensitivity Lemma: $\overline{H}$ denotes the subgraph
of the full permutahedron that only consists of the bichromatic edges when the
vertices are colored with their execution trace under $A$. By Claim 18, the
sum of the weights of all rankings $\rho$ in $R_{i}$ is at most $1$.
Therefore,

$\sum_{\rho}2^{-0pt(\rho)}w(\rho)\leq 1.$

Dividing both sides by $n!$ and taking the logarithm of both sides, we get
that

$\log_{2}\mathbb{E}\left[2^{-0pt(\rho)}w(\rho)\right]\leq\log_{2}(1/n!),$ (18)

where the expectation is with respect to a uniform distribution over the
inputs $\rho$. By Jensen’s inequality, since $\log$ is concave, we get

$\log_{2}\mathbb{E}\left[2^{-0pt(\rho)}w(\rho)\right]\geq\mathbb{E}\left[\log_{2}\left(2^{-0pt(\rho)}w(\rho)\right)\right]=\mathbb{E}[-0pt(\rho)]+\mathbb{E}[\log_{2}w(\rho)],$

which, in combination with (18), implies

$\mathbb{E}[\log_{2}w(\rho)]\leq\mathbb{E}[0pt(\rho)]+\log_{2}(1/n!).$

Note that since $g$ is log-convex, so is $f$. By applying Jensen’s inequality
again,

$\mathbb{E}[\log_{2}w(\rho)]=\mathbb{E}[\log_{2}f(\deg_{\overline{H}}(\rho))]\geq\log_{2}f(\mathbb{E}[\deg_{\overline{H}}(\rho)]),$

implying

$\log_{2}\left(\frac{1}{n}\cdot\frac{g(\mathbb{E}[\deg_{\overline{H}}(\rho)]+1)}{n!}\right)\leq\mathbb{E}[0pt(\rho)]+\log_{2}(1/n!),$

or equivalently,

$\mathbb{E}[0pt(\rho)]\geq\log_{2}(g(\mathbb{E}[\deg_{\overline{H}}(\rho)]+1)/n).$

The result follows since $A$ is an arbitrary deterministic algorithm for
$\Pi$, $\mathbb{E}[0pt(\rho)]$ equals the query complexity of $A$ with respect
to the uniform distribution $\operatorname{\mathcal{D}}$,
$\mathbb{E}[\deg_{\overline{H}}(\rho)]\geq\mathbb{E}[\deg_{\overline{G}(\Pi)}(\rho)]=s(\Pi)$,
and $g$ is nondecreasing. ∎

Proposition 39 allows us to prove a lower bound on the $\varepsilon$-error
distributional query complexity of $\Pi$ with respect to the uniform
distribution. In order to do so, we view a deterministic algorithm with
distributional error $\varepsilon$ for $\Pi$ as an exact deterministic
algorithm for a modified problem $\Pi^{\prime}$, apply Proposition 39, and
lower bound the sensitivity of $\Pi^{\prime}$ in terms of the sensitivity of
$\Pi$.

###### Proposition 40.

Let $\Pi$ be a problem in the comparison-query model with $n$ items,
$\operatorname{\mathcal{D}}$ the uniform distribution on the inputs $\rho$,
$\varepsilon\in[0,1]$, and $g:[1,\infty)\to\mathbb{R}$ a nondecreasing log-
convex function with $g(x)=x!$ for $x\in[n]$.

$\operatorname{DistQ}_{\varepsilon}(\Pi,\operatorname{\mathcal{D}})\geq\log_{2}\left(\frac{g(s(\Pi)+1-2(n-1)\varepsilon)}{n}\right)$
(19)

###### Proof.

Consider any algorithm $A$ with error $\varepsilon$ for $\Pi$, or in other
words, $\mathbb{P}[A(\rho)\neq\Pi(\rho)]\leq\varepsilon$. Let $\Pi_{A}$ be the
problem of determining the output of $A$. We prove that

$s(\Pi_{A})\geq s(\Pi)-2(n-1)\varepsilon,$

which implies the desired result by Proposition 39, since $A$ is a
deterministic algorithm for $\Pi_{A}$ and $g$ is nondecreasing.

Let $G$ denote the full permutahedron graph for $n$ items. We use the fact
that $s(\Pi)=(n-1)\cdot\mathbb{P}_{e\in G}[e\in G(\Pi)]$, and similarly,
$s(\Pi_{A})=(n-1)\cdot\mathbb{P}_{e\in G}[e\in G(\Pi_{A})]$, where all the
underlying distributions are uniform. Suppose the endpoints of $e$ are
$\rho_{1}$ and $\rho_{2}$. Note that if $e\in G$ is picked uniformly at
random, then the marginal distributions of both $\rho_{1}$ and $\rho_{2}$ are
also uniform. If $A(\rho_{1})=\Pi(\rho_{1})$, $A(\rho_{2})=\Pi(\rho_{2})$, and
$e\in G(\Pi_{A})$, then $e\in G(\Pi)$, as well. By a union bound, the
probability that $A(\rho_{1})\neq\Pi(\rho_{1})$ or
$A(\rho_{2})\neq\Pi(\rho_{2})$ is at most $2\varepsilon$.

$\displaystyle\mathbb{P}_{e\in G}[e\in G(\Pi_{A})]$
$\displaystyle\geq\mathbb{P}_{e\in G}[e\in G(\Pi)]-\mathbb{P}_{e\in
G}[A(\rho_{1})\neq\Pi(\rho_{1})\text{ or }A(\rho_{2})\neq\Pi(\rho_{2})]$
$\displaystyle\geq\mathbb{P}_{e\in G}[e\in G(\Pi)]-2\varepsilon.$

Multiplying both sides by $n-1$ gives $s(\Pi_{A})\geq
s(\Pi)-2(n-1)\varepsilon$. ∎

Since $s(\Pi)\leq n-1$, Proposition 40 only yields nontrivial lower bounds for
small $\varepsilon$. In order to establish lower bounds for the standard
$\varepsilon=1/3$, we first reduce the error using standard techniques. Doing
so such that the argument of $g$ on the right-hand side of (19) remains
$\Omega(s(\Pi))$, and picking $g(x)=\Gamma(x+1)$, we conclude:

###### Lemma 41 (Bounded-Error Sensitivity Lemma).

For any problem $\Pi$ in the comparison-query model with $n$ items,

$\operatorname{RQ}_{1/3}(\Pi)=\Omega\left(\frac{s\log s}{\log(2n/s)}\right),$

where $s\doteq s(\Pi)$.

###### Proof.

By taking the majority vote of multiple independent runs and a standard
analysis, e.g, based on Chernoff bounds, we have that
$\operatorname{RQ}_{\varepsilon}(\Pi)=O(\log(1/\varepsilon))\operatorname{RQ}_{1/3}(\Pi)$
for any $\varepsilon\leq 1/3$. Combining this with Lemma 38 and Proposition
40, we have:

$\operatorname{RQ}_{1/3}(\Pi)=\Omega\left(\frac{\operatorname{RQ}_{\varepsilon}(\Pi)}{\log(1/\varepsilon)}\right)=\Omega\left(\frac{\operatorname{DistQ}_{2\varepsilon}(\Pi)}{\log(1/\varepsilon)}\right)=\Omega\left(\frac{\log(g(s+1-4(n-1)\varepsilon)/n)}{\log(1/\varepsilon)}\right).$

Setting $\varepsilon$ such that $4n\varepsilon=s/2$ yields

$\operatorname{RQ}_{1/3}(\Pi)=\Omega\left(\frac{\log(g(s/2+1)/n)}{\log(8n/s)}\right).$

Picking $g(x)=\Gamma(x+1)$ and using the fact that $\Gamma(x)\geq\sqrt{2\pi
x}\left(\frac{x}{e}\right)^{x}$, we obtain

$\operatorname{RQ}_{1/3}(\Pi)=\Omega\left(\frac{(s/2)\log(s/(2e))-\log
n}{\log(8n/s)}\right)=\Omega\left(\frac{s\log s}{\log(2n/s)}\right),$

where the simplification can be verified by considering the cases of large $s$
(say $s\geq\sqrt{n}$) and small $s$ separately. ∎

We can apply Lemma 41 to the sensitivity lower bounds of Lemma 20 and produce
randomized lower bounds for inversion minimization on bounded-degree trees.
Using 24 we obtain:

###### Theorem 42 (lower bound against bounded-error for inversion
minimization on trees).

Let $T$ be a tree with $\deg(T)\leq k$. The query complexity of $\Pi_{T}$ for
bounded-error randomized algorithms is $\Omega(\frac{n\log(n/k)}{k\log(k)})$.

##  7 Connectivity Lemma

In this section we establish Lemma 15 and use it to present some of the known
lower bounds in a unified framework. We actually prove the following somewhat
stronger result.

###### Lemma 43 (Strong Connectivity Lemma).

Consider an algorithm $A$ in the comparison-based model, color each vertex of
the permutahedron with its execution trace under $A$, and let $H$ denote the
subgraph with the same vertex set but only containing the monochromatic edges.
The number of distinct execution traces of $A$ equals the number of connected
components of $H$.

The Connectivity Lemma follows from Lemma 43 because the coloring with
execution traces of an algorithm $A$ for $\Pi$ is a refinement of the coloring
with $\Pi$. Note that the counterpart of Lemma 43 in the Boolean setting is
trivial. This is because an execution trace in the Boolean setting is
specified by values for a subset of the input bits, so the set of inputs that
follow a particular execution trace form a subcube of the hypercube, the
Boolean counterpart of the permutahedron. Subcubes are trivially connected
inside the hypercube. In the comparison-query model, the sets of inputs that
follow a particular execution trace can be more complicated, and their
connectedness is no longer trivial but still holds.

###### Proof of Lemma 43.

Two rankings $\rho_{1}$ and $\rho_{2}$ that have distinct execution traces
under $A$ cannot be connected because any path between them needs to contain
at least one bichromatic edge. For the remainder of the proof, we consider two
rankings $\rho_{1}$ and $\rho_{2}$ that have the same execution trace under
$A$, and construct a path from $\rho_{1}$ to $\rho_{2}$ in $H$.

If $\rho_{1}=\rho_{2}$, we do not need to make any move and use an empty path.

Otherwise, there exists a rank $r<n$ such that $\rho_{1}$ and $\rho_{2}$ agree
on ranks less than $r$ and disagree on rank $r$. We have the following
situation, where the item $y_{r}$ with rank $r$ under $\rho_{2}$, has rank
$s>r$ under $\rho_{1}$.

$\begin{array}[]{r|ccccccccc}\text{rank}&1&\cdots&r-1&r&\cdots&s-1&s&\cdots&n\\\
\hline\cr\rho_{1}^{-1}&x_{1}&\cdots&x_{r-1}&x_{r}&\cdots&x_{s-1}&x_{s}=y_{r}&\cdots&\\\
&{\scriptstyle=}&{\scriptstyle=}&{\scriptstyle=}&{\scriptstyle\neq}&&&&&\\\
\rho_{2}^{-1}&y_{1}&\cdots&y_{r-1}&y_{r}&\cdots&&&\cdots&\end{array}$

Considering ranking $\rho_{1}$, we have that
$\rho_{1}(x_{s-1})=s-1<s=\rho_{1}(x_{s})$. Considering ranking $\rho_{2}$,
since $x_{s-1}$ differs from $y_{i}=x_{i}$ for every $i\in[r-1]$ and also
differs from $y_{r}$, we have that
$\rho_{2}(x_{s-1})>r=\rho_{2}(y_{r})=\rho_{2}(x_{s})$. Thus, the relative
ranks of $x_{s-1}$ and $x_{s}$ under $\rho_{1}$ and $\rho_{2}$ differ. As
$\rho_{1}$ and $\rho_{2}$ have the same execution trace, this means that the
algorithm does not compare $x_{s-1}$ and $x_{s}$ on either input, and on
$\rho_{1}$ in particular. Let $\rho^{\prime}_{1}$ be the ranking obtained from
ranking $\rho_{1}$ by applying the adjacent-rank transposition $\tau=(s-1,s)$.
Since the algorithm does not compare the affected items, the execution trace
for $\rho^{\prime}_{1}$ and $\rho_{1}$ are the same, so the edge from
$\rho_{1}$ to $\rho_{1}$ is monochromatic and in $H$. We use this edge as the
first on the path from $\rho_{1}$ to $\rho_{2}$ in $H$. What remains is to
find a path from $\rho^{\prime}_{1}$ to $\rho_{2}$ in $H$. The situation is
the same as the one depicted above but with $r$ increased by one in case
$s=r+1$, and with the same $r$ and $s$ decreased by one, otherwise. The proof
then follows by induction on the ordered pair $(r,n-s)$. ∎

###### Remark 44.

Suppose we allow an algorithm $A$ to have multiple valid execution traces on a
given input $\rho$, and let $R$ denote the set of rankings on which a
particular execution trace is valid. The construction in the proof of Lemma 43
yields a path in the permutahedron between any two rankings in $R$ such that
the path entirely stays within $R$. This means that we can replace
$\operatorname{D}(\Pi)$ in the statement of the Connectivity Lemma by its
nondeterministic variant $\operatorname{N}(\Pi)$.

We already explained in Section 1 how the Connectivity Lemma shows that
counting inversions and inversion parity amount to sorting, and require at
least $\log(n!)$ queries. We now illustrate its use for a classical problem
that is easier than sorting, namely median finding.

Let $\Pi$ denote the selection problem with rank $r=\left\lceil
n/2\right\rceil$. For any ranking, the adjacent-rank transpositions $\tau$
that change the item with rank $r$ are the two that involve rank $r$:
$\tau=(r-1,r)$ and $\tau=(r,r+1)$. Those transpositions are the ones that
correspond to missing edges in the permutahedron graph $G(\Pi)$. As a result,
for any two rankings, there exists a path between them in $G(\Pi)$ if and only
if they have the same median as well as the same set of items with rank less
than $r$ (and also the same set of items with rank greater than $r$). As there
are $n$ possibilities for the median and, for each median, $\binom{n-1}{r-1}$
possibilities for the set of items that have rank less than $r$, $G(\Pi)$ has
$n\cdot\binom{n-1}{r-1}$ connected components. It follows that any algorithm
for $\Pi$ has at least $n\cdot\binom{n-1}{r-1}=\Omega(\sqrt{n}\cdot 2^{n})$
distinct execution paths, and therefore needs to make at least
$n+\frac{1}{2}\log(n)-O(1)$ queries.

As a side note, this example clarifies a subtlety in the equivalence between
ordinary selection and the instantiation of partial order production that is
considered equivalent to selection. Whereas selection of rank $r$ ordinarily
requires outputting only the item of rank $r$, the instantiation of partial
order production additionally requires partitioning the remaining items
according to whether their ranks are less than or greater than $r$. The above
analysis implies that it is impossible for the algorithm to know the item of
rank $r$ without also knowing how to partition the remaining items into those
of rank less than and greater than $r$. It follows that, in the comparison-
based model, ordinary selection and the instantiation of partial order
production are equivalent.

##  8 Connectivity Approach

In this section we develop the connectivity approach to obtain query lower
bounds for problems $\Pi$ in the comparison-query model. Our main focus is the
problem $\Pi_{T}$ of inversion minimization on certain types of trees $T$, for
which we derive the very strong query lower bounds of Theorem 8. While
developing the application, we observe that some parts carry through for a
broader class of problems. This allows us to apply the same ideas to the
problem of counting cross inversions, for which we obtain the query lower
bound of Theorem 9, as well as the closely related problem of inversion
minimization on the Mann–Whitney trees of Figure 2.

In order to obtain good lower bounds on $\operatorname{D}(\Pi_{T})$ using the
Connectivity Lemma, it is sufficient to find good upper bounds on the size of
the connected components of a typical vertex in $G(\Pi_{T})$. Assume without
loss of generality that $T$ has no internal nodes of degree 1, i.e., no nodes
with exactly one child. $\Pi_{T}$ is always insensitive to an adjacent-rank
transposition $\tau$ at a ranking $\rho$ when the affected leaves are siblings
in $T$. Thus, the corresponding edges from the permutahedron are always
present in $G(\Pi_{T})$. From the perspective of ensuring small connected
components in $G(\Pi_{T})$, the ideal situation would be if there were no
other edges in $G(\Pi_{T})$. That is to say, $\Pi_{T}$ is _sensitive_ at
$\rho$ to _every_ adjacent-rank transposition $\tau$ _except_ when the
affected leaves are siblings. We will investigate conditions on $T$ that
guarantee this situation in the next subsections. For now, let us investigate
the size of the connected components of $G(\Pi_{T})$ when $T$ is of the
desired type.

To facilitate the analysis, recall our notation for the maximal sets of
sibling leaves.

###### Definition 45 (leaf child set, $\operatorname{LC}$).

The _leaf child set_ $\operatorname{LC}(v)$ of a vertex $v$ in a tree $T$ is
the set $\operatorname{LC}(v)$ of all the children of $v$ that are leaves in
$T$.

Let $\operatorname{LC}_{1},\operatorname{LC}_{2},\dots$ denote the leaf child
sets in $T$. See Figure 10(a) for an example. As the only steps we can take in
$G(\Pi_{T})$ correspond to adjacent-rank transpositions $\tau$ that swap
leaves in the same leaf child set $\operatorname{LC}_{i}$, the sets
$\operatorname{LC}_{i}$ remain invariant, irrespective of the ranking $\rho$
we start from.

Depending on $\rho$, there may be more structure inside each leaf child set
$\operatorname{LC}_{i}$; the leaf child set may be broken up into smaller sets
that are each invariant. Figure 10(b) illustrates how this happens for a
particular leaf child set containing 7 leaves. We list the elements of the
child leaf set in order of increasing rank under $\rho$, and include an edge
between elements that have successive ranks. We introduce the term “successor
graph” to capture this structure, viewed as a graph with the ranks as
vertices.

###### Definition 46 (successor graph, $S(\cdot,\cdot)$).

Let $\Pi$ be a computational problem in the comparison-query model on a set
$X$ of $n$ items, and $\rho$ a ranking of $X$. The successor graph of $\Pi$ on
$\rho$, denoted $S(\Pi,\rho)$, has vertex set $[n]$ and contains all edges of
the form $(r,r+1)$ with $r\in[n-1]$ such that $\Pi(\rho)=\Pi(\tau\rho)$, where
$\tau$ denotes the adjacent-rank transposition $(r,r+1)$.

$4$$12$$6$$5$$10$$11$$2$$3$$9$$14$$7$$8$$1$$13$$\operatorname{LC}_{1}$$\operatorname{LC}_{2}$$\operatorname{LC}_{3}$$\operatorname{LC}_{4}$
(a) Leaf child sets and leaf ranks under $\rho$

$r$$2$$3$$7$$8$$9$$11$$14$$\rho(r)$ (b) Inside leaf child set
$\operatorname{LC}_{3}$

Figure 10: Connected component analysis

The connected components of the successor graph $S(\Pi,\rho)$ in Figure 10(b)
correspond to subsets of $\operatorname{LC}_{i}$ that each remain invariant.
Within each of the subsets, every possible ordering can be reached,
independently for each subset. This is because for any adjacent-rank
transposition $\tau$, the successor graphs $S(\Pi,\rho)$ and $S(\Pi,\tau\rho)$
are the same, and every ordering can be realized by a sequence of swaps of
adjacent elements. Thus, if the sizes of the connected components of
$S(\Pi,\rho)$ over all possible leaf child sets $\operatorname{LC}_{i}$ are
$n_{1},n_{2},\dots$, the size of the connected component of $\rho$ in
$G(\Pi_{T})$ equals $\prod_{j}(n_{j}!)$.

For future reference, we abstract the property that we need for the above
analysis the carry through.

###### Definition 47 (partition property).

A computational problem $\Pi$ in the comparison-query model on a set $X$ of
$n$ items has the _partition property_ if the set $X$ can be partitioned into
sets $X_{i}$ such that for any ranking $\rho$ of $X$ and adjacent-rank
transposition $\tau=(r,r+1)$ with $r\in[n-1]$, $\Pi(\rho)=\Pi(\tau\rho)$ if
and only if $\rho^{-1}(r)$ and $\rho^{-1}(r+1)$ belong to the same partition
class $X_{i}$.

In the case of the problem $\Pi_{T}$, the partition classes $X_{i}$ correspond
to the leaf child sets $\operatorname{LC}_{i}$. We have shown:

###### Proposition 48.

Let $\Pi$ be a computational problem in the comparison-query model on the set
$X$, and let $\rho$ be a ranking of $X$. If $\Pi$ has the partition property,
then the connected component of $\rho$ in $G(\Pi)$ has size
$\prod_{j}(n_{j}!)$, where the $n_{j}$’s denote the sizes of the connected
components of $S(\Pi,\rho)$.

Returning to instances of the problem $\Pi_{T}$ with the partition property,
if each leaf child set $\operatorname{LC}_{i}$ has size at most $k$, then each
of the connected components of $S(\Pi,\rho)$ has size $n_{j}\leq k$,
irrespective of $\rho$. The maximum value that $\prod_{j}(n_{j}!)$ can take
under the constraints $\sum_{j}n_{j}=n$ and $n_{j}\leq k$ is no more than
$(k!)^{n/k}$. By the Connectivity Lemma, we conclude that
$\operatorname{D}(\Pi_{T})\geq n!/(k!)^{n/k}$, and that the query complexity
is at least $\log_{2}(n!)-O(n\log(k))$.

We can do better by observing that, for a random ranking $\rho$, the number of
adjacent-rank transpositions $\tau$ that do not jump from one leaf child set
to another one, is not much larger than the average size of the leaf child
sets. More precisely, for any rank $r\in[n-1]$, the probability that
$\rho^{-1}(r)$ and $\rho^{-1}(r+1)$ belong to the same leaf child set equals
$\sum_{i}\frac{|\operatorname{LC}_{i}|}{n}\frac{|\operatorname{LC}_{i}|-1}{n-1}$,
which is at most $\frac{k-1}{n-1}$ when each leaf child set
$\operatorname{LC}_{i}$ is of size at most $k$. It follows that the expected
number of adjacent-rank transpositions $\tau$ that do not change leaf child
sets, is at most $k-1$, so for a fraction at least half of the rankings $\rho$
the number is at most $2(k-1)$.

The number of adjacent-rank transpositions $\tau$ that do not change leaf
child sets for a given ranking $\rho$ equals the number of edges in the
successor graph $S(\Pi_{T},\rho)$. This is the number of edges in Figure
10(b), summed over all leaf child sets $\operatorname{LC}_{i}$. In terms of
the sizes $n_{j}$, the number equals $\sum_{j}(n_{j}-1)$. We are considering
rankings $\rho$ for which the sum is at most $2(k-1)$. The maximum of
$\prod_{j}(n_{j}!)$ under the constraints that $\sum_{j}(n_{j}-1)\leq 2(k-1)$
and that each individual $n_{j}\leq k$, is reached when two of the $n_{j}$’s
equal $k$ and the rest are 1. Thus, if each of the leaf child sets
$\operatorname{LC}_{i}$ are of size at most $k$, for a fraction at least half
of the rankings $\rho$, the size of the connected component of $\rho$ in
$G(\Pi_{T})$ is at most $(k!)^{2}$. It follows that the number of connected
components of $G(\Pi)$ is at least $n!/(2(k!)^{2})$. By the Connectivity
Lemma, we conclude:

###### Lemma 49.

Let $T$ be a tree with $n$ leaves. If $\Pi_{T}$ satisfies the partition
property, then $\operatorname{D}(\Pi)\geq n!/(2(k!)^{2})$.

This yields a lower bound of $\log(n!)-O(k\log(k))$ on the query complexity of
$\Pi_{T}$ whenever $\Pi_{T}$ satisfies the partition property.

Next we find sufficient conditions on the tree $T$ that guarantee that
$\Pi_{T}$ has the partition property. For didactic reasons we first develop
the conditions for binary trees, and then generalize them to arbitrary trees.

###  8.1 Binary trees

In the case of binary trees $T$, the sensitivity analysis of Section 5.1 leads
to a simple sufficient condition for the partition property to hold for
$\Pi_{T}$. Recall that we are assuming without loss of generality that $T$ has
no internal nodes of degree 1, which in the case of binary trees is equivalent
to saying that the tree is full: Every internal node has the maximum degree of
2.

Consider criterion 8 in Proposition 30. The right-hand side is always $-1$. As
for the left-hand side, we know the following.

###### Fact 50.

For all disjoint sets $A,B\subseteq X$ and any ranking $\rho$ of $X$,
$\operatorname{DInv}_{\rho}(A,B)=|A|\cdot|B|\bmod 2$.

###### Proof.

As every pair in $A\times B$ constitutes a cross-inversion for either $A$ to
$B$, or $B$ to $A$, we have
$\operatorname{XInv}_{\rho}(A,B)+\operatorname{XInv}_{\rho}(B,A)=|A|\cdot|B|$.
Thus,

$\displaystyle\operatorname{DInv}_{\rho}(A,B)$
$\displaystyle\doteq\operatorname{XInv}_{\rho}(A,B)-\operatorname{XInv}_{\rho}(B,A)$
$\displaystyle=(\operatorname{XInv}_{\rho}(A,B)+\operatorname{XInv}_{\rho}(B,A))-2\operatorname{XInv}_{\rho}(B,A)$
$\displaystyle=|A|\cdot|B|-2\operatorname{XInv}_{\rho}(B,A).$ (20)

As $\operatorname{XInv}_{\rho}(B,A)$ in an integer, the claim follows. ∎

Fact 50 implies that whenever at least one of the leaf sets $L_{\mathrm{lo}}$
or $L_{\mathrm{hi}}$ is of even cardinality, then (8) fails to hold, and
$\Pi_{T}$ is sensitive to the underlying $\tau$ at $\rho$. Thus, we can
guarantee that $\Pi_{T}$ satisfies the partition property provided that for
any two siblings $u_{1}$ and $u_{2}$ in $T$ that are not both leaves, at least
one of $\lvert\operatorname{L}(T_{u_{1}})\rvert$ or
$\lvert\operatorname{L}(T_{u_{2}})\rvert$ is even. We refer to the latter
condition as the _product condition_. In trees without nodes of degree 1, the
product condition can be expressed alternately in terms of the leaf child
sets. We state and prove the result for arbitrary trees as it will help us in
the next subsection to generalize the analysis.

###### Proposition 51.

Let $T$ be a tree without nodes of degree 1. The following two conditions are
equivalent:

  * (a)

For any two siblings $u_{1}$ and $u_{2}$ that are not both leaves, at least
one of $\lvert\operatorname{L}(T_{u_{1}})\rvert$ or
$\lvert\operatorname{L}(T_{u_{2}})\rvert$ is even.

  * (b)

At most one leaf child set is odd, and if there exists a node $v^{*}$ with an
odd leaf child set $\operatorname{LC}(v^{*})$, then all ancestors of $v^{*}$
have an empty leaf child set.

In the case of binary trees, (b) can be simplified to: At most one leaf has a
non-leaf sibling.

###### Proof.

We establish the two directions of implication separately.

$\Rightarrow$: We argue the contrapositive. Suppose that at least two of the
leaf child sets are odd. Start with the root of $T$ as the node $v$, and
iterate the following: If $v$ has a child $u$ such that $T_{u}$ contains at
least two nodes with an odd leaf child set, replace $v$ by such a child $u$.
When the process ends, one of the following situations applies:

  * $\circ$

There are two distinct children $u_{1}$ and $u_{2}$ of $v$ that are not leaves
and each contain a single node with an odd leaf child set. In this case both
$T_{u_{1}}$ and $T_{u_{2}}$ contain an odd number of leaves, violating (a).

  * $\circ$

There exists a unique child $u_{1}$ of $v$ that is not a leaf and contains a
single node with an odd leaf child set, and $v$ itself has an odd number of
leaf children. In this case, setting $u_{2}$ to any one leaf child of $v$
(which exists as their number is odd), leads to a violation of (a).

Next, suppose that there exists a unique node $v^{*}$ that has an odd leaf
child set, and that an ancestor $v$ of $v^{*}$ has a leaf child $u_{1}$.
Setting $u_{2}$ to the child of $v$ that contains $v^{*}$ in its subtree,
yields a violation of (a) as $T_{u_{2}}$ contains an odd number of leaves.

$\Leftarrow$: If neither $u_{1}$ nor $u_{2}$ are leaves, the first condition
of (b) guarantees that at most one of $T_{u_{1}}$ or $T_{u_{2}}$ contains an
odd number of leaves. If $u_{1}$ is a leaf and $u_{2}$ is not, then the second
condition of (b) implies that $T_{u_{2}}$ cannot contain a node with an odd
leaf child set, and therefore has an even number of leaves.

In the case of binary trees, the first condition of (b) implies the second
one, which can therefore be dropped from the equivalence statement. Moreover,
for binary trees the first condition of (b) can be expressed as: At most one
leaf has a non-leaf sibling. ∎

$1$$3$$6$$2$$4$$5$ Figure 11: Tree insensitive to non-sibling transposition

By Proposition 51, in a binary tree the condition that at most one leaf has no
sibling is equivalent to the product condition, which implies the partition
property of $\Pi_{T}$, so the lower bound of Lemma 49 applies. This
establishes Theorem 8 in the case of binary trees.

As a side note, Fig. 11 shows the simplest example of a full binary tree $T$
and a ranking $\rho$ for which there exists an adjacent-rank transposition
$\tau$ to which $\Pi_{T}$ is insensitive at $\rho$ while the affected leaves
are not siblings. The tree has two leaves without siblings, namely 1 and 2.
The adjacent-rank transposition $(3,4)$ acts on nodes that are not siblings,
but leaves the minimum number of inversions at 4.

###  8.2 General trees

For general trees $T$ the sensitivity analysis of $\Pi_{T}$ becomes more
complicated than for binary trees, and we do not know of a simple sensitivity
criterion like Proposition 30, but we can nevertheless extend the result for
binary trees to arbitrary trees with similar constraints. For a given ranking
$\rho$ of $\operatorname{L}(T)$ and a given adjacent-rank transposition
$\tau$, we would like to figure out the effect of $\tau$ on the objective
$\operatorname{MinInv}(T,\cdot)$, in particular when
$\operatorname{MinInv}(T,\tau\rho)=\operatorname{MinInv}(T,\rho)$. Recall the
decomposition (5) of $\operatorname{MinInv}(T,\cdot)$ from Section 4.2. By
Proposition 26 the only term on the right-hand side of (5) that can be
affected by the transposition $\tau$ is

$\operatorname{MinRInv}(T_{v},\rho)\doteq\min_{\sigma}\operatorname{RInv}(T,\rho,\sigma)$

corresponding to the node $v$ that is the least common ancestor
$\operatorname{LCA}(\ell_{\mathrm{lo}},\ell_{\mathrm{hi}})$ of the two leaves
$\ell_{\mathrm{lo}}$ and $\ell_{\mathrm{hi}}$ that are affected by $\tau$
under $\rho$. In Section 5 we considered the two possible relative orderings
$\sigma_{1}$ and $\sigma_{2}$ of the children of $v$, and derived a criterion
for when the lowest cost does not change under $\tau$. More precisely, when

$\min(\operatorname{RInv}(T,\rho,\sigma_{1}),\operatorname{RInv}(T,\rho,\sigma_{2}))=\min(\operatorname{RInv}(T,\tau\rho,\sigma_{1}),\operatorname{RInv}(T,\tau\rho,\sigma_{2})).$
(21)

There are two complications in generalizing this approach from binary to
general trees.

  * $\circ$

The expression (4) for $\operatorname{RInv}(T,\rho,\sigma)$ involves multiple
terms instead of just one as in (6). This complicates probabilistic analyses
like the one we did in Section 5 because the difference in cost of the two
relative orderings of two children is also affected by parts of the tree
outside of their combined subtrees. The issue did not matter for the analysis
in Section 4. We will be able to manage it here, as well.

  * $\circ$

There now are not just two but multiple possible orderings $\sigma$, and it is
not clear what pairs $(\sigma_{1},\sigma_{2})$ we need to impose (21) on in
order to guarantee that
$\operatorname{MinRInv}(T_{v},\rho)=\operatorname{MinRInv}(T_{v},\tau\rho)$
but no more.

In Section 4 we circumvented the second issue by only considering
sensitivities that decrease the objective function, and establishing a lower
bound on their occurrence independent of the ordering $\sigma$. Here we are
also able to handle the second issue by shooting for a sufficient condition
for sensitivity rather than a criterion. We do so by requiring that for no
pair of distinct orderings $\sigma_{1}$ and $\sigma_{2}$, condition (21) holds
(unless the two affected leaves are siblings). Similar to the case of binary
trees, we guarantee that (21) fails based on parity considerations given the
product condition.

For the analysis we again assume without loss of generality that $T$ has no
nodes of degree 1. We use the same notation as in Section 5: Let
$\ell_{\mathrm{lo}}$ denote the affected leaf that is smaller with respect to
$\rho$, and $\ell_{\mathrm{hi}}$ the other affected leaf. Let $L_{i}$ denote
the leaf set $L_{i}\doteq\operatorname{L}(T_{u_{i}})$, where
$u_{1},\dots,u_{k}$ are the children of
$v=\operatorname{LCA}(\ell_{\mathrm{lo}},\ell_{\mathrm{hi}})$. We also write
$u_{\mathrm{lo}}$ for the child of $v$ that contains $\ell_{\mathrm{lo}}$ in
its subtree, and $L_{\mathrm{lo}}$ for the leaf set of the subtree rooted at
$u_{\mathrm{lo}}$, and define $\ell_{\mathrm{hi}}$, $u_{\mathrm{hi}}$, and
$L_{\mathrm{hi}}$ similarly. See Figure 12 for a sketch of the setting.

$v$$u_{1}$$\cdots$$u_{\mathrm{lo}}$$\cdots$$\cdots$$u_{\mathrm{hi}}$$\cdots$$u_{k}$$\ell_{\mathrm{lo}}$$\ell_{\mathrm{hi}}$$k$
Figure 12: Sensitivity for general trees

We slightly abuse notation and let $\sigma$ denote both the ordering of the
entire tree $T$ as well as the ranking of the children of $v$. By the analysis
of Section 5, we have that for two orderings $\sigma_{1}$ and $\sigma_{2}$ the
situation (21) can only occur if
$\sigma_{1}(u_{\mathrm{lo}})<\sigma_{1}(u_{\mathrm{hi}})$,
$\sigma_{2}(u_{\mathrm{lo}})>\sigma_{2}(u_{\mathrm{hi}})$, and

$\operatorname{RInv}_{\rho}(T_{v},\rho,\sigma_{1})-\operatorname{RInv}_{\rho}(T_{v},\rho,\sigma_{2})=-1=\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},\\{\ell_{\mathrm{hi}}\\}).$
(22)

For any two disjoint sets of leaves, (20) lets us write

$\operatorname{XInv}_{\rho}(A,B)=\frac{1}{2}\operatorname{DInv}_{\rho}(A,B)+\frac{1}{2}|A|\cdot|B|.$
(23)

Applying (23) to all the terms involved in (4), we have

$\displaystyle\operatorname{RInv}_{\rho}(T_{v},\rho,\sigma)$
$\displaystyle=\sum_{1\leq i<j\leq
k}\operatorname{XInv}_{\rho}(L_{i},L_{j})\cdot\mathbb{I}[\sigma(i)<\sigma(j)]$
$\displaystyle\;\;\;\;\;+\sum_{1\leq i<j\leq
k}\operatorname{XInv}_{\rho}(L_{j},L_{i})\cdot\mathbb{I}[\sigma(i)>\sigma(j)]$
$\displaystyle=\frac{1}{2}\sum_{1\leq i<j\leq
k}\left(\operatorname{DInv}_{\rho}(L_{i},L_{j})\cdot(-1)^{\mathbb{I}[\sigma(i>\sigma(j)]}+|L_{1}|\cdot|L_{2}|\right)$
$\displaystyle\operatorname{RInv}_{\rho}(T_{v},\rho,\sigma_{1})-\operatorname{RInv}_{\rho}(T_{v},\rho,\sigma_{2})$
$\displaystyle=\sum\limits_{\begin{subarray}{c}1\leq i<j\leq k\\\
\sigma_{1}(i)<\sigma_{2}(j)\\\
\sigma_{2}(i)>\sigma_{2}(j)\end{subarray}}\operatorname{DInv}_{\rho}(L_{i},L_{j})+\sum\limits_{\begin{subarray}{c}1\leq
i<j\leq k\\\ \sigma_{1}(i)>\sigma_{2}(j)\\\
\sigma_{2}(i)<\sigma_{2}(j)\end{subarray}}\operatorname{DInv}_{\rho}(L_{i},L_{j})$

By combining the last equation with (22) and separating out the term for
$(i,j)=(\mathrm{lo},\mathrm{hi})$, we obtain the following necessary condition
for (21) to hold:

$\operatorname{DInv}_{\rho}(L_{\mathrm{lo}},L_{\mathrm{hi}})-\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},\\{\ell_{\mathrm{hi}}\\})=-\sum\limits_{\begin{subarray}{c}1\leq
i<j\leq k\\\ \sigma_{1}(i)<\sigma_{2}(j)\\\ \sigma_{2}(i)>\sigma_{2}(j)\\\
(i,j)\neq(\mathrm{lo},\mathrm{hi})\end{subarray}}\operatorname{DInv}_{\rho}(L_{i},L_{j})+\sum\limits_{\begin{subarray}{c}1\leq
i<j\leq k\\\ \sigma_{1}(i)>\sigma_{2}(j)\\\
\sigma_{2}(i)<\sigma_{2}(j)\end{subarray}}\operatorname{DInv}_{\rho}(L_{i},L_{j}).$
(24)

In order for $\Pi_{T}$ to have the partition property, it suffices to ensure
that (24) fails whenever $u_{\mathrm{lo}}$ and $u_{\mathrm{hi}}$ are not both
leaves. By (20) each of the terms $\operatorname{DInv}_{\rho}(L_{i},L_{j})$ in
(24) has the same parity as $|L_{i}|\cdot|L_{j}|$. Since
$\operatorname{DInv}_{\rho}(\\{\ell_{\mathrm{lo}}\\},\\{\ell_{\mathrm{hi}}\\})$
is odd, it follows that (24) fails whenever at most one of the leaf sets
$L_{i}$ involved is odd, which is condition (a) in Proposition 51. Switching
to the equivalent condition (b) from Proposition 51 allows us to conclude via
Lemma 49:

###### Theorem 52.

Let $T$ be a tree without nodes of degree 1 such that the leaf child sets have
size at most $k$, at most one of them is odd, and if there exists an odd one,
say $\operatorname{LC}(v^{*})$, then all ancestors of $v^{*}$ have empty leaf
child sets. Then $\operatorname{D}(\Pi_{T})\geq n!/(2(k!)^{2})$.

Theorem 8 follows by taking the base-2 logarithm of the bound.

###  8.3 Counting cross inversions and evaluating the Mann–Whitney statistic

We now apply the connectivity approach that we captured in Proposition 48 to
the problem $\Pi_{\operatorname{XInv}}$ of computing the number of cross
inversions between two disjoint sets $A$ and $B$ with respect to a ranking
$\rho$ of $X=A\sqcup B$. Note that this problem is a refinement of evaluating
the Mann–Whitney statistic, or equivalently, of inversion minimization on the
tree $T$ of Figure 2: Any algorithm that solves $\Pi_{\operatorname{XInv}}$
with $q$ queries, can be transformed into an algorithm for $\Pi_{T}$ with $q$
queries, namely by transforming the output $y$ of the algorithm for
$\Pi_{\operatorname{XInv}}$ to $\min(y,|A|\cdot|B|-y)$. Viewed in the
contrapositive, a lower bound for $\Pi_{\operatorname{XInv}}$ is easier to
obtain than one for $\Pi_{T}$ on the tree $T$ of Figure 2. We first establish
a lower bound for $\Pi_{\operatorname{XInv}}$ and then see how it extends to
$\Pi_{T}$.

One can think of $\Pi_{\operatorname{XInv}}$ as inversion minimization on the
Mann–Whitney tree without allowing swapping the two children of the root. As a
result, the problem $\Pi_{\operatorname{XInv}}$ is sensitive to _every_
adjacent-rank transposition between non-siblings, and therefore automatically
satisfies the partition property (with $A$ and $B$ being the partition
classes), so Proposition 48 applies. In contrast, the problem $\Pi_{T}$ of
minimizing inversions on the Mann–Whitney tree may not have the partition
property. This is why analyzing $\Pi_{\operatorname{XInv}}$ is a bit simpler,
and why we handle it first.

Let $a\doteq|A|$ and $b\doteq|B|$. By the partition property, the average
sensitivity of $\Pi_{\operatorname{XInv}}$ equals $\frac{2ab}{a+b}$, which via
the Sensitivity Lemma yields a query lower bound of $\Omega(a\log(a))$ for
$a\leq b$. To obtain the stronger lower bound of $\Omega((a+b)\log(a))$ we
need a more detailed analysis of the connectivity of the permutahedron graph
$G(\Pi_{\operatorname{XInv}})$.

For a given ranking $\rho$, let $x_{1},\dots,x_{a}$ be the elements of $A$
listed in increasing order, and similarly for $y_{1},\dots,y_{b}$ for the
elements of $B$. We define $m_{1},\dots,m_{b+1}$ such that for each $i$,
$m_{i}$ is the number of elements of $A$ between $y_{i-1}$ and $y_{i}$. (Here,
$y_{0}$ and $y_{b+1}$ serve as sentinels with an infinitely low and infinitely
high rank.) Similarly, we define $n_{1},\dots,n_{a+1}$ as the number of
elements in $B$ between successive elements of $A$. The numbers $m_{i}$ and
$n_{i}$ are the sizes of the connected components of the successor graph
$S(\Pi_{\operatorname{XInv}},\rho)$ (possibly with some additional zeroes). By
Proposition 48, the connected component of $\rho$ in
$G(\Pi_{\operatorname{XInv}})$ has size

$(m_{1})!\cdots(m_{b+1})!(n_{1})!\cdots(n_{a+1})!.$ (25)

Depending on the values of $m_{1},\dots,m_{b+1},n_{1},\dots,n_{a+1}$, some
connected components may be much larger than others. We apply the Connectivity
Lemma in a similar way as in Lemma 49 and only count the rankings $\rho$ that
are in small connected components, which are the rankings for which
$m_{1},\dots,m_{b+1},n_{1},\dots,n_{a+1}$ are bounded. Let $m^{*}$ and $n^{*}$
be the minimum integers for which

$\mathbb{P}[m_{1},\dots,m_{b+1}\leq
m^{*}]\geq\frac{3}{4}\quad\text{and}\quad\mathbb{P}[n_{1},\dots,n_{a+1}\leq
n^{*}]\geq\frac{3}{4}.$

By a union bound, the probability that both of these events hold is at least
$1/2$. In other words, there are least $(a+b)!/2$ rankings $\rho$ for which
$m_{1},\dots,m_{b+1}\leq m^{*}$ and $n_{1},\dots,n_{a+1}\leq n^{*}$.

###### Proposition 53.

$\operatorname{D}(\Pi_{T})\geq\frac{(a+b)!}{2(m^{*})!^{a/m^{*}}(n^{*})!^{b/n^{*}}}.$
(26)

###### Proof.

We consider the rankings for which $m_{1},\dots,m_{b+1}\leq m^{*}$ and
$n_{1},\dots,n_{a+1}\leq n^{*}$. We first argue the following upper bound on
the size (25) of the connected component in $G(\Pi_{\operatorname{XInv}})$ of
any such ranking $\rho$:

$(m_{1})!\cdots(m_{b+1})!(n_{1})!\cdots(n_{a+1})!\leq(m^{*})^{a/m^{*}}(n^{*})^{b/n^{*}}.$
(27)

For nonnegative integers $n$, $n!^{1/n}$ is increasing. This can be seen by
noticing that $\log(n!^{1/n})$ is the average of $\log(1),\dots,\log(n)$. As a
result, for $i\in[b+1]$, $(m_{i})!^{1/m_{i}}\leq(m^{*})!^{1/m^{*}}$, or
equivalently, $(m_{i})!\leq(m^{*})^{m_{i}/m^{*}}$. Using the fact that
$m_{1}+\dots+m_{b+1}=a$,

$(m_{1})!\cdots(m_{b+1})!\leq(m^{*})!^{(m_{1}+\dots+m_{b+1})/m^{*}}=(m^{*})!^{a/m^{*}}.$

We can apply similar reasoning to get
$(n_{1})!\cdots(n_{a+1})!\leq(n^{*})!^{b/n^{*}}$. From this, we conclude that
the size of the connected components among the rankings under consideration is
at most the right-hand side of (27).

Since there are at least $(a+b)!/2$ of the rankings under consideration, we
derive the stated bound on $\operatorname{D}(\Pi_{T})$ by applying the
Connectivity Lemma. ∎

Now, we find concrete bounds on $m^{*}$ and $n^{*}$.

###### Proposition 54.

$\max\left(1,\frac{a}{b+1}\right)\leq m^{*}\leq\frac{a+b}{b}\ln(4(b+1)).$

Symmetrically,

$\max\left(1,\frac{b}{a+1}\right)\leq n^{*}\leq\frac{a+b}{a}\ln(4(a+1)).$

###### Proof.

We first prove the upper bound on $m^{*}$. Let $k$ be a positive integer. We
compute the probability, over an average ranking $\rho$, that $m_{i}>k$ for a
specific $i$. Notice that there is a one-to-one correspondence between ranking
$\rho$ and the corresponding sequence of nonnegative integers
$m_{1},\dots,m_{b+1}$ such that $m_{1}+\dots+m_{b+1}=a$, because the ranks of