Zestawy stopni dla liniowych wykresów rozszerzenia

Liniowe rozszerzenie $L$ z poset $\mathcal{P}$ jest liniowy porządek na elementach $\mathcal{P}$ tak, że $x \leq y$ w implikuje w dla wszystkich . x ≤ y L x , y ∈ $\mathcal{P}$$x \leq y$$L$$x,y\in\mathcal{P}$

Liniowy wykres przedłużenie jest wykresem na zestawie liniowe przedłużenie części poset, gdzie dwa rozszerzenia liniowe przylegają dokładnie jeśli są di ff ER w jednej sąsiedniej wymiany elementów.

Na poniższym obrazku jest zestaw znany jako purposet i jego liniowy wykres rozszerzenia, gdzie .a = 1234 , b = 2134 , c = 1243 , d = 2143 , e = $N$$a=1234, b=2134, c=1243, d=2143, e=2413$

(Ta liczba pochodzi z pracy .)

Kiedy studiujesz liniowe wykresy rozszerzenia (LEG), możesz wymyślić pomysł (przypuszczenie), że jeśli - maksymalny stopień LEG, - odpowiednio, minimalny stopień, to zestaw stopni dowolnego LEG składa się z i każda liczba naturalna między nimi. Na przykład weźmy poset, znany jako szewron, a następnie w jego LEG z i , a także, zgodnie z zgodnie z naszą hipotezą na wykresie znajdują się wierzchołki o stopniach 4 i 3. Pytanie brzmi: czy możemy udowodnić lub obalić tę hipotezę?δ Δ , δ G Δ ( G ) = 5 δ ( G ) = $\Delta$$\delta$$\Delta,\delta$$\mathcal{G}$$\Delta(\mathcal{G})=5$$\delta(\mathcal{G})=2$

O LEG i ich wyglądzie można przeczytać w rozprawie Mareike Massow tutaj . Chevron i jego LEG można zobaczyć na stronie 23 rozprawy.

Na zestawach stopni znajduje się klasyczna praca „ Zestawy stopni dla wykresów ” autorstwa Kapoor SF i in.

Myślę, że udowodniłem to wczoraj. Oto szkic dowodu. Najpierw udowodniono następujący lemat.

Lemat . Niech - rząd częściowy, G ( P ) - jego liniowy wykres rozszerzenia, a v 1 , v 2 - dwa sąsiednie wierzchołki G ( P ) . To | d e g ( v 1 ) - d e g ( v 2 ) | ≤ 2 .$\mathcal{P}$$G(\mathcal{P})$$v_1,v_2$$G(\mathcal{P})$$|deg(v_1)-deg(v_2)|\leq 2$

Szkic dowodu.

Jednocześnie są liniowymi przedłużeniami P, tak że jeden z nich, powiedzmy v 1 , może zostać przekształcony w v 2 przez jedną transpozycję sąsiednich elementów (transpozycja sąsiednia). Z powyższego rysunku łatwo zauważyć (na przykład d i e ), że dowolny element x i dowolnego przedłużenia liniowego L = x 1 x 2 … x n może zmienić liczbę nieporównywalnych sąsiednich elementów na maksymalnie dwóch:$v_1,v_2$$\mathcal{P}$$v_1$$v_2$$d$$e$$x_i$$L=x_1x_2\dots x_n$

1. Jeśli można w ogóle transponować, to co najmniej jeden jego sąsiad, powiedzmy x i + 1 , jest z nim nieporównywalny ( x i ∥ x i + 1 , jeśli jest porównywalny, to x i ⊥ x i + 1 ). Uwaga: przed transpozycją mamy L 1 = … x i - 1 x i x i + 1 x i + 2 … i natychmiast po - L 2 = $x_i$$x_{i+1}$$x_i\parallel x_{i+1}$$x_i\perp x_{i+1}$$L_1=\dots x_{i-1}x_ix_{i+1}x_{i+2}\dots$ .$L_2=\dots x_{i-1}x_{i+1}x_{i}x_{i+2}\dots$
2. Zastanówmy się, jak może zmienić się liczba nieporównywalności (stopień rozszerzenia liniowego jako wierzchołek w ) w L. Najpierw rozważamy parę x i x i + 2 . Dla x i - 1 x i + 1 ten sam wniosek wynika z symetrii.$G(\mathcal{P})$$L$$x_ix_{i+2}$$x_{i-1}x_{i+1}$

Jeśli , to d e g ( L ) się nie zmienia. Jeśli x i + 1 ⊥ ( ∥ ) x i + 2 ∧ x i ∥ ( ⊥ ) x i + 2 , to d e $x_{i+1}\parallel(\perp) x_{i+2}\land x_{i}\parallel(\perp) x_{i+2}$$deg(L)$$x_{i+1}\perp(\parallel) x_{i+2}\land x_{i}\parallel(\perp) x_{i+2}$ zwiększa się (zmniejsza) o jeden. Szkic dowodu jest zakończony.$deg(L)$

Twierdzenie . Niech - wykres rozszerzenia liniowego. Jeśli G ( P ) zawiera wierzchołki v 1 , v 2 z d e g ( v 1 ) = k , d e g ( v 2 ) = k + 2 , to jest v 3 ∈ G ( P ) takie, że d e g ( v 3$G(\mathcal{P})$$G(\mathcal{P})$$v_1,v_2$$deg(v_1)=k,deg(v_2)=k+2$$v_3\in G(\mathcal{P})$ .$deg(v_3)=k+1$

Szkic dowodu.

Załóżmy, że sąsiadują w G ( P ) , w przeciwnym razie każdy wierzchołek o stopniu k w G ( P ) sąsiaduje z jakiś wierzchołek, jeśli taki istnieje ze stopniem k + 1 .$v_1,v_2,deg(v_1)=k,deg(v_2)=k+2$$G(\mathcal{P})$$k$$G(\mathcal{P})$$k+1$

Rozważmy przypadek, w którym mamy z poprzedniego lematu takie, że$L_1,L_2$

a x i - 1 ⊥ x i ∧ x i - 1 ∥ x i + 1

Zatem .$deg(L_2)=deg(L_1)+2$

$x_{i+1}$$x_1$