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

alternatywny tekst (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ę? $\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.

graph-theory co.combinatorics

— Oleksandr Bondarenko
źródło

co to jest wykres rozszerzenia liniowego? to znaczy, czy możesz sprowadzić definicję do pytania, aby było trochę bardziej samodzielne?

— Suresh Venkat,

Ta hipoteza jest urocza. Czy istnieje jakaś motywacja lub znane zastosowania przypuszczenia? (Powiedz redukcje do innych przypuszczeń.)

— Hsien-Chih Chang 之之

@ Hsien-Chih Chang Motywacja do tego przypuszczenia polega na udowodnieniu, że poznamy zawartość ustawionego stopnia po prostu znając maksymalne i minimalne stopnie danego wykresu rozszerzenia liniowego.

— Oleksandr Bondarenko

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

Lemat . Niech - rząd częściowy, - jego liniowy wykres rozszerzenia, a - dwa sąsiednie wierzchołki . To . $\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 tak że jeden z nich, powiedzmy , może zostać przekształcony w przez jedną transpozycję sąsiednich elementów (transpozycja sąsiednia). Z powyższego rysunku łatwo zauważyć (na przykład i ), że dowolny element dowolnego przedłużenia liniowego 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$

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

Jeśli , to się nie zmienia. Jeśli , to $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 zawiera wierzchołki z , to jest takie, że $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 , w przeciwnym razie każdy wierzchołek o stopniu w sąsiaduje z jakiś wierzchołek, jeśli taki istnieje ze stopniem . $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$

x_{ja + 1} ⊥ x_{ja + 2)} \land x_{ja} ∥ x_{ja + 2)},

$x_{i+1}\perp x_{i+2}\land x_{i}\parallel x_{i+2},$

x_{ja - 1} ⊥ x_{ja} \land x_{ja - 1} ∥ x_{ja + 1},

$x_{i-1}\perp x_{i}\land x_{i-1}\parallel x_{i+1},$

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

$x_{i+1}$ $x_1$

x_{jot} ⊥ x_{ja + 1} \land x_{ja + 1} ∥ x_{jot + 1},

$x_{j}\perp x_{i+1}\land x_{i+1}\parallel x_{j+1},$

j < i - 1

$j<i-1$

— Oleksandr Bondarenko
źródło

W dowodzie twierdzenia nie podążam za pierwszym zdaniem. Jeśli chodzi o notację, zwykle widziałem

x \sim y

$x \sim y$ używane do oznaczenia tego

x

$x$ i

y

$y$ są porównywalne.

— András Salamon

@ András Salamon Dodałem trochę wyjaśnienia (stopnie

v_{1}, v_{2}

$v_1,v_2$ ) do pierwszego zdania dowodu twierdzenia.

— Oleksandr Bondarenko

@ András Salamon

x ⊥ y

$x\perp y$ jest używany w ten sam sposób, np. tutaj: smartech.gatech.edu/bitstream/1853/33810/1/...

— Oleksandr Bondarenko