Uma extensão linear de um poset é uma ordem linear nos elementos de , de modo que em implica em para todos os .P P x ≤ y P x ≤ y L x , y ∈ P
Um gráfico de extensão linear é um gráfico no conjunto de extensões lineares de um poset, onde duas extensões lineares são adjacentes exatamente se elas diferem em uma troca adjacente de elementos.
Na figura a seguir, há o poset conhecido como poset e seu gráfico de extensão linear, onde .um = 1,234 , b = 2,134 , c = 1,243 , d = 2,143 , E = 2413
(Esta figura é retirada do trabalho .)
Ao estudar gráficos de extensão linear (LEG), você pode ter uma idéia (conjectura) de que se - grau máximo de uma LEG, - respectivamente, grau mínimo, o conjunto de graus de qualquer LEG consiste em e cada número natural entre eles. Por exemplo, vamos pegar um poset, conhecido como chevron, e em seu LEG com e e também, de acordo com de acordo com nossa conjectura, os vértices com os graus 4 e 3 estão contidos no gráfico. Então, a questão é: podemos provar ou refutar essa conjectura?δ Δ , δ G Δ ( G ) = 5 δ ( G ) = 2
Sobre pernas e como é que eles se parecem se pode ler na dissertação de Mareike Massow aqui . A Chevron e sua LEG podem ser vistas na página 23 da dissertação.
Nos conjuntos de graus existe o artigo clássico " Conjuntos de graus para gráficos " de Kapoor SF et al.
fonte
Respostas:
Acho que provei ontem. Assim, aqui vai o esboço da prova. A princípio, o seguinte lema é comprovado.
Lema . Seja - uma ordem parcial, G ( P ) - seu gráfico de extensão linear e v 1 , v 2 - dois vértices adjacentes de G ( P ) . Então | d e g ( v 1 ) - d e g ( v 2 ) | ≤ 2 .P G(P) v1,v2 G(P) |deg(v1)−deg(v2) | ≤ 2
O esboço da prova.
Ao mesmo tempo, são extensões lineares de P, de modo que um deles, digamos v 1 , pode ser transformado em v 2 por uma transposição de elementos adjacentes (transposição adjacente). É fácil ver (considere, por exemplo, d e e da figura acima) que qualquer elemento x i de qualquer extensão linear L = x 1 x 2 … x n pode alterar o número de elementos adjacentes incomparáveis em no máximo dois:v1 1,v2 P v1 1 v2 d e xEu L=x1x2…xn
Se , então d e g ( L ) não muda. Se x i + 1 ⊥ ( ∥ ) x i + 2 ∧ x i ∥ ( ⊥ ) x i + 2 , então d e gxi+1∥(⊥)xi+2∧xi∥(⊥)xi+2 deg(L) xi+1⊥(∥)xi+2∧xi∥(⊥)xi+2 aumenta (diminui) em um. O esboço da prova está completo.deg(L)
Teorema . Seja - um gráfico de extensão linear. Se G ( P ) contém os vértices v 1 , v 2 com d e g ( v 1 ) = k , d e g ( v 2 ) = k + 2 , então existe v 3 ∈ G ( P ) tal que d e g ( v 3 )G(P) G(P) v1 1,v2 de g( v1 1) = k , de g( v2)=k+2 v3∈G(P) .deg(v3)=k+1
O esboço da prova.
Suponha que sejam adjacentes em G ( P ) , caso contrário, qualquer vértice com grau k em G ( P ) é adjacente a algum vértice, se existir, com o grau k + 1 .v1,v2,deg(v1)=k,deg(v2)=k+2 G(P) k G(P) k+1
Vamos considerar o caso em que temos do lema anterior, de modo queL1,L2
e x i - 1 ⊥ x i ∧ x i - 1 ∥ x i + 1 ,
Assim, .deg(L2)=deg(L1)+2
Vamos agora começar a transpor na direção de x 1 . É fácil ver que, eventualmente, poderíamos parar na posição em quexi+1 x1
para alguns j < i - 1 . O esboço da prova está completo.
fonte