# Degree sets for linear extension graphs

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 diﬀer 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$.

(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.

• 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 ? – Suresh Venkat Nov 12 '10 at 1:30
• This conjecture is cute. Is there any motivation or known applications for the conjecture? (Say reductions to another conjectures.) – Hsien-Chih Chang 張顯之 Nov 15 '10 at 9:40
• @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. – Oleksandr Bondarenko Dec 4 '10 at 14:21

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.

• 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. – András Salamon Nov 16 '10 at 10:25
• @András Salamon I added some clarification (degrees of $v_1,v_2$) to the first sentence of the theorem proof. – Oleksandr Bondarenko Nov 16 '10 at 18:31
• @András Salamon $x\perp y$ is used in the same manner, e.g., here: smartech.gatech.edu/bitstream/1853/33810/1/… – Oleksandr Bondarenko Nov 16 '10 at 20:18