I have been reading the paper 'Time Space Tradeoff for Sorting on Non-Oblivious Machines' by Borodin et al. (Link). Lemma 1 in that paper gives a relation between the number of permutations consistent with a Hasse diagram $H$ and the number of permutations that are $i$-consistent with $H$.

Let me explain for self containment. Let $H$ be a Hasse diagram on $n$ vertices. A permutation $\pi$ on $(1,2,\cdots, n)$ is said to be consistent with $H$ if $\pi(i)>\pi(j)$ whenever there is a path of positive length from $i$ to $j$ in $H$. Two elements $j$ and $k$ are said to be comparable if there exists some path from $j$ to $k$ or $k$ to $j$ in $H$. Now, define the following.

  1. $P(H)$ is the set of all permutations that are consistent with $H$.
  2. $C(H,i)$ is the set of all elements that are comparable to $i$ in $H$.
  3. $H-i$ is the Hasse diagram on $n-1$ vertices after removing $i$ from $H$ and adding an edge from each parent of $i$ in $H$ to all children of $i$ in $H$.

Lemma 1 states that $n\cdot |P(H-i)| \le |C(H,i)|\cdot |P(H)|$ for any Hasse diagram $H$ on $n$ vertices and has a vertex labelled $i$. In order to understand the proof, I tried to take some examples.

Consider the Hasse diagram on $3$ vertices that has only two edges. The edges are $1\rightarrow 2$ and $1\rightarrow 3$. Say $i=1$. Now, we can get the following

  1. $P(H) = \{ \{312\}, \{321\} \}$ where $\{abc\}$ denotes the permutation $\pi$ such that $\pi(1)=a, \pi(2)=b, \pi(3)=c$.
  2. $C(H,i) = \{2,3\}$.
  3. $P(H-i) = \{\{123\},\{132\},\{213\},\{231\},\{312\},\{321\}\}$.

Clearly, $n\cdot |P(H-i)| = 3\cdot 6 > 2\cdot 2 = |C(H,i)|\cdot |P(H)|$. I tried the same for a few other examples, and I ended up in a similar situation.

So, is the lemma incorrect or am I interpreting the lemma incorrectly?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.