Gradsätze für lineare Erweiterungsgraphen

Eine lineare Ausdehnung eines poset P ist eine lineare Ordnung auf die Elemente P , derart , daß x ≤ y in P bedeutet , x ≤ y in L für alle x , y ∈ P .$L$$\mathcal{P}$$\mathcal{P}$$x \leq y$$\mathcal{P}$$x \leq y$$L$$x,y\in\mathcal{P}$

Ein linearer Erweiterungsgraph ist ein Graph auf der Menge der linearen Erweiterungen eines Posets, wobei zwei lineare Erweiterungen genau dann benachbart sind, wenn sie sich in einem benachbarten Elementaustausch unterscheiden.

Auf dem folgenden Bild ist das als -Poset bekannte Poset und sein linearer Erweiterungsgraph zu sehen, wobei a = 1234 , b = 2134 , c = 1243 , d = 2143 , e = 2413 .$N$$a=1234, b=2134, c=1243, d=2143, e=2413$

(Diese Abbildung stammt aus der Arbeit .)

Wenn Sie lineare Erweiterungsgraphen (LEG) studieren, können Sie eine Idee (Vermutung) aufstellen, dass, wenn - maximaler Grad eines LEG, δ - bzw. minimaler Grad, der Gradsatz eines LEG aus Δ , δ und jedem besteht natürliche Zahl zwischen ihnen. Nehmen wir zum Beispiel einen als Chevron bekannten Poset, dann in dessen LEG G mit Δ ( G ) = 5 und δ ( G ) = 2 , und nach unserer Vermutung sind in auch Scheitelpunkte mit den Graden 4 und 3 enthalten der Graph. Die Frage ist also, ob wir diese Vermutung beweisen oder widerlegen können.$\Delta$$\delta$$\Delta,\delta$$\mathcal{G}$$\Delta(\mathcal{G})=5$$\delta(\mathcal{G})=2$

Über LEGs und wie sehen sie aus wie ein in der Dissertation von Mareike Massow lesen hier . Chevron und sein Bein sind auf Seite 23 der Dissertation zu sehen.

Zu den Gradsätzen gibt es die klassische Arbeit " Gradsätze für Graphen " von Kapoor SF et al.

Ich glaube, ich habe es gestern bewiesen. Also hier ist die Skizze des Beweises. Zunächst wird das folgende Lemma bewiesen.

Lemma . Sei - eine Teilordnung, G ( P ) - sein linearer Erweiterungsgraph und v 1 , v 2 - zwei benachbarte Eckpunkte von G ( P ) . Dann | 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$

Die Skizze des Beweises.

Gleichzeitig sind lineare Erweiterungen von P, so dass eine von ihnen, beispielsweise v 1 , durch eine Transposition benachbarter Elemente in v 2 transformiert werden kann (benachbarte Transposition). Es ist leicht zu erkennen (man betrachte zum Beispiel d und e aus der obigen Abbildung), dass jedes Element x i mit jeder linearen Ausdehnung L = x 1 x 2 … x n die Anzahl von nicht vergleichbaren benachbarten Elementen an höchstens zwei ändern kann:$v_1,v_2$$\mathcal{P}$$v_1$$v_2$$d$$e$$x_i$$L=x_1x_2\dots x_n$

1. $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. $G(\mathcal{P})$$L$$x_ix_{i+2}$$x_{i-1}x_{i+1}$

$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}$ erhöht (verringert) sich um eins. Die Proofskizze ist fertig.$deg(L)$

$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$

Die Skizze des Beweises.

$v_1,v_2,deg(v_1)=k,deg(v_2)=k+2$$G(\mathcal{P})$$k$$G(\mathcal{P})$$k+1$

$L_1,L_2$

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

$x_{i+1}$$x_1$