Required bits to communicate a partial order?

Question

Suppose that you have a ranking (i.e. a strict complete partial order) over $n$ different objects, so that the objects can be ordered as $a>b>\cdots>n$. You want to communicate the exact order you have to a outside server. The question is how many bites do you need to do it? We are interested in the minimal number of bits that the task requires.

My initial guess is that you need $\frac{n(n-1)}{2}$ bites to transfer the information, because the partial order is equivalent to pairwise comparison among all the elements of ${1,...,n}$. One can verify that there are exactly $\frac{n(n-1)}{2}$ such binary relations.

Yet a recent paper claims that the partial order can be transmited in $\log_2(n!)$ bits. I understand that this follows from Shannon's entropy, but I just can't see the precise way to allocate the binary digits to express the ranking. Any ideas or explanations?

Intuitive answers are very welcome. Thanks,

Answer 1

Assuming that the ranking is strict and linear, transmitting it amounts to transmitting a permutation $\sigma$ of $[n]=\{1,2,\ldots,n\}$. For $k,\ell\in[n]$ write $k\prec\ell$ if and only if $k$ precedes $\ell$ in $\sigma$. For each $k\in[n]$ let

$$p(k)=|\{\ell\in[n]:\ell<k\text{ and }\ell\prec k\}|\;;$$

$0\le p(k)\le k-1$. The number $p(k)$ specifies where $k$ must be inserted amongst the numbers $\{1,\ldots,k-1\}$, so $\sigma$ can be reconstructed from the sequence $\langle p(2),p(3),\ldots,p(n)\rangle$, which can be expressed in

$$\sum_{k=2}^n\lceil\lg k\rceil\approx\lg(n!)$$

bits.

Answer 2

This is at best a partial answer.

For a general finite partially ordered set (i.e. a partial order that is not necessarily a total order), I can think of two things that would reduce the amount of information that would need to be sent.

The first is to collapse "similar" elements into a single element. By similar elements, I mean that they are covered by the same set of elements and they cover the same set of elements (this means that an element is similar to itself). For each element $a$, find the set $A$ of similar elements to $a$, then collapse $A$ into a single element. This produces a new "reduced" poset where each element is similar to itself, and no others.

The next thing to do is to decompose the reduced poset into chains (another name for total order). Dilworth's Theorem may be of some use here.

Then, instead of sending all pairs in the partial order, send the chains in order (as a list of lists, for example), and for each element $a$ of the reduced poset that was produced by collapsing at least 2 elements from the original poset, send the list of similar elements $a_1,\ldots,a_k$.

I don't know how close this gets you to $\log_2 n!$, though.

Actually, I almost see it for a total order. There are $n$ elements in total. $\log_2n$ bits are needed to encode each element. Therefore, a list containing $n$ elements will require $n\log_2n$ bits. I don't know how to get $\log_2n!$ exactly, but I believe that $\log n!=O(n\log n)$ (see, for example, Why is $\log(n!)$ $O(n\log n)$?)