Conjuntos de grados para gráficos de extensión lineal

17

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 .LPPxyPxyLx,yP

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 .Na=1234,b=2134,c=1243,d=2143,e=2413

texto alternativo(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?ΔδΔ,δGΔ(G)=5δ(G)=2

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.

Oleksandr Bondarenko
fuente
3
¿Qué es un gráfico de extensión lineal? es decir, ¿puedes incluir la definición en la pregunta para que sea un poco más autónoma?
Suresh Venkat
1
Esta conjetura es linda. ¿Hay alguna motivación o aplicaciones conocidas para la conjetura? (Diga reducciones a otras conjeturas.)
Hsien-Chih Chang 張顯 之
@ Hsien-Chih Chang La motivación para esta conjetura es cuando la demostremos, conoceremos el contenido del conjunto de grados simplemente conociendo los grados máximos y mínimos de un gráfico de extensión lineal dado.
Oleksandr Bondarenko

Respuestas:

11

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 .PG(P)v1,v2G(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,v2Pv1v2dexiL=x1x2xn

  1. Si se puede transponer entonces al menos uno de sus vecinos, digamos x i + 1 , es incomparable ( x ix i + 1 , si es comparable, entonces x ix i + 1 ). Nota: antes de transponer tenemos L 1 = ... x i - 1 x i x i + 1 x i + 2 ... e inmediatamente después - L 2 = ...xixi+1xixi+1xixi+1L1=xi1xixi+1xi+2 .L2=xi1xi+1xixi+2
  2. Consideremos cómo podría cambiar el número de incompatibilidades (grado de la extensión lineal como vértice en ) en L. Consideramos al principio el par x i x i + 2 . Para x i - 1 x i + 1, la misma conclusión se sigue por simetría.G(P)Lxixi+2xi1xi+1

Si , entonces d e g ( L ) no cambia. Si x i + 1( ) x i + 2x i( ) x i + 2 , entonces d e gxi+1()xi+2xi()xi+2deg(L)xi+1()xi+2xi()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 3G ( P ) tal que d e g ( v 3 )G(P)G(P)v1,v2deg(v1)=k,deg(v2)=k+2v3G(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+2G(P)kG(P)k+1

Consideremos el caso en el que tenemos del lema anterior de modo queL1,L2

y x i - 1x ix i - 1x i + 1 ,

xi+1xi+2xixi+2,
xi1xixi1xi+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+1x1

para algunos j < i - 1 . Se completa el boceto de la prueba.

xjxi+1xi+1xj+1,
j<i1
Oleksandr Bondarenko
fuente
2
En la prueba del teorema, no sigo la primera oración. Con respecto a la notación, generalmente he visto que usa para denotar que x e y son comparables. xyxy
András Salamon
1
@ András Salamon Agregué algunas aclaraciones (grados de ) a la primera oración de la demostración del teorema. v1,v2
Oleksandr Bondarenko
1
xy