Una extensión lineal de un poset P es un orden lineal en los elementos de P , de tal manera que x ≤ y en P implica x ≤ y en L para todo x , y ∈ P .
Un gráfico de extensión lineal es un gráfico en el conjunto de extensiones lineales de un poset, donde dos extensiones lineales son adyacentes exactamente si difieren en un intercambio adyacente de elementos.
En la siguiente imagen está el poset conocido como poset, y su gráfico de extensión lineal, donde a = 1234 , b = 2134 , c = 1243 , d = 2143 , e = 2413 .
(Esta cifra está tomada del trabajo ).
Cuando estudias gráficas de extensión lineal (LEG) puedes tener una idea (conjetura) de que si - grado máximo de un LEG, δ - respectivamente, grado mínimo, entonces el conjunto de grados de cualquier LEG consiste en Δ , δ y cada uno Número natural entre ellos. Por ejemplo, tomemos un poset, conocido como chevron, luego en su LEG G con Δ ( G ) = 5 y δ ( G ) = 2 , y también, de acuerdo con nuestra conjetura, los vértices con los grados 4 y 3 están contenidos en la gráfica. Entonces, la pregunta es ¿podemos probar o refutar esta conjetura?
Acerca de LEG y cómo se ven uno puede leer en la disertación de Mareike Massow aquí . Chevron y su LEG se pueden ver en la página 23 de la disertación.
En los conjuntos de grados está el artículo clásico " Conjuntos de grados para gráficos " de Kapoor SF et al.
fuente
Respuestas:
Creo que lo probé ayer. Así, aquí va el bosquejo de la prueba. Al principio, se prueba el siguiente lema.
Lema . Sea - un orden parcial, G ( P ) - su gráfico de extensión lineal y v 1 , v 2 - dos vértices adyacentes de G ( P ) . Entonces | d e g ( v 1 ) - d e g ( v 2 ) | ≤ 2 .P G(P) v1,v2 G(P) |deg(v1)−deg(v2)|≤2
El boceto de la prueba.
Al mismo tiempo, son extensiones lineales de P de modo que uno de ellos, digamos v 1 , puede transformarse en v 2 mediante una transposición de elementos adyacentes (transposición adyacente). Es fácil ver (considere, por ejemplo, d y e de la figura anterior) que cualquier elemento x i de cualquier extensión lineal L = x 1 x 2 ... x n puede cambiar el número de elementos adyacentes incomparables en un máximo de dos:v1,v2 P v1 v2 d e xi L=x1x2…xn
Si , entonces d e g ( L ) no cambia. Si x i + 1 ⊥ ( ∥ ) x i + 2 ∧ x i ∥ ( ⊥ ) x i + 2 , entonces d e gxi+1∥(⊥)xi+2∧xi∥(⊥)xi+2 deg(L) xi+1⊥(∥)xi+2∧xi∥(⊥)xi+2 aumenta (disminuye) en uno. Se completa el boceto de la prueba.deg(L)
Teorema . Deje - un gráfico de extensión lineal. Si G ( P ) contiene vértices v 1 , v 2 con d e g ( v 1 ) = k , d e g ( v 2 ) = k + 2 , entonces hay v 3 ∈ G ( P ) tal que d e g ( v 3 )G(P) G(P) v1,v2 deg(v1)=k,deg(v2)=k+2 v3∈G(P) .deg(v3)=k+1
El boceto de la prueba.
Supongamos que son adyacentes en G ( P ) , de lo contrario, cualquier vértice con grado k en G ( P ) es adyacente con algún vértice si tal existe con grado k + 1 .v1,v2,deg(v1)=k,deg(v2)=k+2 G(P) k G(P) k+1
Consideremos el caso en el que tenemos del lema anterior de modo queL1,L2
y x i - 1 ⊥ x i ∧ x i - 1 ∥ x i + 1 ,
Así .deg(L2)=deg(L1)+2
Comencemos ahora transponer en la dirección de x 1 . Es fácil ver que eventualmente podríamos parar en la posición dondexi+1 x1
para algunos j < i - 1 . Se completa el boceto de la prueba.
fuente