A linear extension $L$ of a poset $\mathcal{P}$ is a linear order on the elements of $\mathcal{P}$, such that $x \leq y$ in $\mathcal{P}$ implies $x \leq y$ in $L$ for all $x,y\in\mathcal{P}$.

A linear extension graph is a graph on the set of linear extensions of a poset, where two linear extensions are adjacent exactly if they differ in one adjacent swap of elements.

On the following picture there is the poset known as $N$-poset, and its linear extension graph, where $a=1234, b=2134, c=1243, d=2143, e=2413$.

alt text(This figure is taken from the work.)

When you study linear extension graphs (LEG) you can come up with an idea (conjecture) that if $\Delta$ - maximal degree of a LEG, $\delta$ - respecrively, minimal degree, then the degree set of any LEG consists of $\Delta,\delta$ and each natural number between them. For example, let's take a poset, known as chevron, then in its LEG $\mathcal{G}$ with $\Delta(\mathcal{G})=5$ and $\delta(\mathcal{G})=2$, and also, according to our conjecture, vertices with the degrees 4 and 3 are contained in the graph. So, the question is can we prove or disprove this conjecture?

About LEGs and how do they look like one can read in the dissertation of Mareike Massow here. Chevron and its LEG can be seen on the page 23 of the dissertation.

On the degree sets there is the classical paper "Degree sets for graphs" by Kapoor S.F. et al.

  • 3
    $\begingroup$ what's a linear extension graph ? that is to say, can you fold the definition into the question so that it's a little more self-contained ? $\endgroup$ Commented Nov 12, 2010 at 1:30
  • 1
    $\begingroup$ This conjecture is cute. Is there any motivation or known applications for the conjecture? (Say reductions to another conjectures.) $\endgroup$ Commented Nov 15, 2010 at 9:40
  • $\begingroup$ @Hsien-Chih Chang Motivation for this conjecture is when proving it we will know the contents of the degree set just by knowing maximum and minimum degrees of a given linear extension graph. $\endgroup$ Commented Dec 4, 2010 at 14:21

1 Answer 1


I think I proved it yesterday. Thus here goes the sketch of the proof. At first, the following lemma is proved.

Lemma. Let $\mathcal{P}$ - a partial order, $G(\mathcal{P})$ - its linear extension graph and $v_1,v_2$ - two adjacent vertices of $G(\mathcal{P})$. Then $|deg(v_1)-deg(v_2)|\leq 2$.

The sketch of the proof.

At the same time, $v_1,v_2$ are linear extensions of $\mathcal{P}$ such that one of them, say $v_1$, can be transformed into $v_2$ by one transposition of adjacent elements (adjacent transposition). It is easy to see (consider, for instance, $d$ and $e$ from the above figure) that any element $x_i$ of any linear extension $L=x_1x_2\dots x_n$ can change the number of incomparable adjacent elements on at most two:

  1. If $x_i$ can be transposed at all then at least one its neighbor, say $x_{i+1}$, is incomparable to it ($x_i\parallel x_{i+1}$, if comparable then $x_i\perp x_{i+1}$). Note: before transposing we have $L_1=\dots x_{i-1}x_ix_{i+1}x_{i+2}\dots$ and immediately after - $L_2=\dots x_{i-1}x_{i+1}x_{i}x_{i+2}\dots$.
  2. Let us consider how the number of incomparabilities (degree of the linear extension as the vertex in $G(\mathcal{P})$) in $L$ could change. We consider at first the pair $x_ix_{i+2}$. For $x_{i-1}x_{i+1}$ the same conclusion follows by symmetry.

If $x_{i+1}\parallel(\perp) x_{i+2}\land x_{i}\parallel(\perp) x_{i+2}$, then $deg(L)$ doesn't change. If $x_{i+1}\perp(\parallel) x_{i+2}\land x_{i}\parallel(\perp) x_{i+2}$, then $deg(L)$ increases (decreases) by one.The sketch of the proof is completed.

Theorem. Let $G(\mathcal{P})$ - a linear extension graph. If $G(\mathcal{P})$ contains vertices $v_1,v_2$ with $deg(v_1)=k,deg(v_2)=k+2$, then there is $v_3\in G(\mathcal{P})$ such that $deg(v_3)=k+1$.

The sketch of the proof.

Suppose $v_1,v_2,deg(v_1)=k,deg(v_2)=k+2$ are adjacent in $G(\mathcal{P})$, otherwise any vertex with degree $k$ in $G(\mathcal{P})$ is adjacent with some vertex if such exists with degree $k+1$.

Let us consider the case where we have $L_1,L_2$ from the previous lemma such that

$$x_{i+1}\perp x_{i+2}\land x_{i}\parallel x_{i+2},$$ and $$x_{i-1}\perp x_{i}\land x_{i-1}\parallel x_{i+1},$$

Thus $deg(L_2)=deg(L_1)+2$.

Let us now start transpose $x_{i+1}$ in the direction of $x_1$. It is easy to see that eventually we could stop at the position where

$$x_{j}\perp x_{i+1}\land x_{i+1}\parallel x_{j+1},$$ for some $j<i-1$. The sketch of the proof is completed.

  • 2
    $\begingroup$ In the proof of the theorem, I don't follow the first sentence. Regarding notation, I've usually seen $x \sim y$ used to denote that $x$ and $y$ are comparable. $\endgroup$ Commented Nov 16, 2010 at 10:25
  • 1
    $\begingroup$ @András Salamon I added some clarification (degrees of $v_1,v_2$) to the first sentence of the theorem proof. $\endgroup$ Commented Nov 16, 2010 at 18:31
  • 1
    $\begingroup$ @András Salamon $x\perp y$ is used in the same manner, e.g., here: smartech.gatech.edu/bitstream/1853/33810/1/… $\endgroup$ Commented Nov 16, 2010 at 20:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.