Return to 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 follow 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.

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.

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 than at least one its neighbor, say $x_{i+1}$, is incomparable to it ($x_i\parallel x_{i+1}$, if comparable than $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 follow 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.

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

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 than at least one its neighbor, say $x_{i+1}$, is incomparable to it ($x_i\parallel x_{i+1}$, if comparable than $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 follow 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$ 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.

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 than at least one its neighbor, say $x_{i+1}$, is incomparable to it ($x_i\parallel x_{i+1}$, if comparable than $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 follow 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.