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

<p><strong>Lemma</strong>. 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$.</p>

<p>The sketch of the proof.</p>

<p>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:</p>

<ol>
<li>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$.</li>
<li>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.</li>
</ol>

<p>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.</p>

<p><strong>Theorem</strong>. 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$.</p>

<p>The sketch of the proof.</p>

<p>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$.</p>

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

<p>$$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},$$</p>

<p>Thus $deg(L_2)=deg(L_1)+2$.</p>

<p>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</p>

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

CC BY-SA 2.5
2010-11-16T10:25:50.010Z
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
CC BY-SA 2.5
2010-11-16T18:31:23.537Z
@András Salamon I added some clarification (degrees of $v_1,v_2$) to the first sentence of the theorem proof.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-16T20:18:56.360Z
@András Salamon $x\perp y$ is used in the same manner, e.g., here: http://smartech.gatech.edu/bitstream/1853/33810/1/Keller_Mitchel_T_201005_phd.pdf
Oleksandr Bondarenko
CC BY-SA 3.0
2010-11-16T07:23:34.887Z
2012-01-27T18:43:47.013Z
2012-01-27T18:43:47.013Z
Oleksandr Bondarenko
<p>A <strong><em>linear extension</em></strong> $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}$.</p>

<p>A <strong><em>linear extension graph</em></strong> 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.</p>

<p>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$. </p>

<p><img src="https://i.sstatic.net/SRKyt.png" alt="alt text">(This figure is taken from the <a href="http://arxiv.org/abs/0809.1828" rel="nofollow noreferrer">work</a>.)</p>

<p>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?</p>

<p>About LEGs and how do they look like one can read in the dissertation of Mareike Massow <a href="http://www.math.tu-berlin.de/~massow/diss_genehmigt.pdf" rel="nofollow noreferrer">here</a>. Chevron and its LEG can be seen on the page 23 of the dissertation.</p>

<p>On the degree sets there is the classical paper "<a href="http://matwbn.icm.edu.pl/ksiazki/fm/fm95/fm95117.pdf" rel="nofollow noreferrer">Degree sets for graphs</a>" by Kapoor S.F. et al.</p>

CC BY-SA 2.5
2010-11-15T09:40:43.787Z
This conjecture is cute. Is there any motivation or known applications for the conjecture? (Say reductions to another conjectures.)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-04T14:21:51.510Z
@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
CC BY-SA 2.5
2010-11-12T01:30:15.793Z
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
<graph-theory><co.combinatorics>
Degree sets for linear extension graphs
Oleksandr Bondarenko
# Degree sets for linear extension graphs

(Asked by: username_0 on 2010-11-12)

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

![alt text](https://i.sstatic.net/SRKyt.png)(This figure is taken from the [work](http://arxiv.org/abs/0809.1828).)

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](http://www.math.tu-berlin.de/~massow/diss_genehmigt.pdf). 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](http://matwbn.icm.edu.pl/ksiazki/fm/fm95/fm95117.pdf)" by Kapoor S.F. et al.

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_2**: 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 ?  
> **username_1**: This conjecture is cute. Is there any motivation or known applications for the conjecture? (Say reductions to another conjectures.)  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_0 on 2010-11-16. Score: 11 | Accepted answer

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

> **Comments:**
> **username_3**: 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.  
> **username_0**: @András Salamon I added some clarification (degrees of $v_1,v_2$) to the first sentence of the theorem proof.  
> **username_0**: @András Salamon $x\perp y$ is used in the same manner, e.g., here: http://smartech.gatech.edu/bitstream/1853/33810/1/Keller_Mitchel_T_201005_phd.pdf  

---

