Is the following relation on disjoint subsets of [n] transitive?

80 Views Asked by At

The following is a curiosity which arised during my work.

We deal with subsets of $[n]$, where $n$ is some natural number. For an ordered pair of disjoint subsets $(X,Y)$ we call any pair $(x,y)\in X \times Y$ with $x > y$ a discordant pair of $(X,Y)$. Let $D(X,Y)$ be the number of discordant pairs of $(X,Y)$.

We say that $X \leq Y$ iff $D(X,Y) \leq D(Y,X)$. For example, $\{1,5\} \leq \{2,4,6\}$.

My question is whether this relation is transitive. More precisely, let $A,B,C$ be pairwise disjoint subsets of $[n]$. Assume that $A \leq B$ and $B \leq C$. Does it follow that $A \leq C$?

I've initially suspected that this is wrong, but failed to produce a counterexample. Then, I thought: $X \leq Y$ intuitively means that the elements of $X$ are "usually" smaller than those of $Y$. This interpretation would suggest that the relation is transitive. Now I'm no longer sure what the right answer is. Any help would be appreciated :)

1

There are 1 best solutions below

0
On BEST ANSWER

As suggested in the comments; consider the sets \begin{eqnarray*} A&=&\{2,4,9\},\\ B&=&\{3,5,7\},\\ C&=&\{1,6,8\}. \end{eqnarray*}