Ensembles de degrés pour les graphiques d'extension linéaire

Une extension linéaire $L$ d'un poset est un ordre linéaire sur les éléments de , tel que dans implique dans pour tout . $\mathcal{P}$ $\mathcal{P}$ $x \leq y$ $\mathcal{P}$ $x \leq y$ $L$ $x,y\in\mathcal{P}$

Un graphique d'extension linéaire est un graphique sur l'ensemble des extensions linéaires d'un poset, où deux extensions linéaires sont adjacentes exactement si elles diffèrent dans un échange d'éléments adjacent.

Sur l'image suivante, il y a le poset connu sous le nom de poset, et son graphique d'extension linéaire, où . $N$ $a=1234, b=2134, c=1243, d=2143, e=2413$

texte alternatif (Ce chiffre est tiré de l' ouvrage .)

Lorsque vous étudiez les graphes d'extension linéaire (LEG), vous pouvez avoir une idée (conjecture) que si - degré maximal d'un LEG, - respectivement, degré minimal, alors l'ensemble de degrés de tout LEG se compose de et chaque nombre naturel entre eux. Par exemple, prenons un poset, appelé chevron, puis dans son LEG avec et , et aussi, selon à notre conjecture, les sommets avec les degrés 4 et 3 sont contenus dans le graphique. La question est donc de savoir si nous pouvons prouver ou infirmer cette conjecture? $\Delta$ $\delta$ $\Delta,\delta$ $\mathcal{G}$ $\Delta(\mathcal{G})=5$ $\delta(\mathcal{G})=2$

A propos GLE et comment ils ressemblent on peut lire dans le mémoire de Mareike Massow ici . Chevron et son LEG sont visibles à la page 23 de la thèse.

Sur les ensembles de degrés, il y a l'article classique " Ensembles de degrés pour les graphiques " de Kapoor SF et al.

graph-theory co.combinatorics Oleksandr Bondarenko
la source

qu'est-ce qu'un graphique d'extension linéaire? c'est-à-dire, pouvez-vous replier la définition dans la question pour qu'elle soit un peu plus autonome?

Suresh Venkat

Cette conjecture est mignonne. Y a-t-il une motivation ou des applications connues pour la conjecture? (Dites des réductions à d'autres conjectures.)

Hsien-Chih Chang 張顯之

@ Hsien-Chih Chang La motivation de cette conjecture consiste à prouver que nous connaîtrons le contenu de l'ensemble de degrés simplement en connaissant les degrés maximum et minimum d'un graphique d'extension linéaire donné.

Oleksandr Bondarenko

Je pense que je l'ai prouvé hier. Voilà donc l'esquisse de la preuve. Dans un premier temps, le lemme suivant est prouvé.

Lemme . Soit - un ordre partiel, $\mathcal{P}$ $G(\mathcal{P})$ - son graphe d'extension linéaire et - deux sommets adjacents de . Alors . $v_1,v_2$ $G(\mathcal{P})$ $|deg(v_1)-deg(v_2)|\leq 2$

Le croquis de la preuve.

En même temps, $v_1,v_2$ sont des extensions linéaires de telles que l'une d'entre elles, disons , peut être transformée en par une transposition d'éléments adjacents (transposition adjacente). Il est facile de voir (considérons, par exemple, et de la figure ci-dessus) que tout élément de n'importe quelle extension linéaire peut changer le nombre d'éléments adjacents incomparables sur au plus deux: $\mathcal{P}$ $v_1$ $v_2$ $d$ $e$ $x_i$ $L=x_1x_2\dots x_n$

Si peut être transposé, alors au moins un de ses voisins, disons , lui est incomparable ( , s'il est comparable, alors $x_i$ $x_{i+1}$ $x_i\parallel x_{i+1}$ ). Remarque: avant la transposition, nous avons et immédiatement après - $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$
Examinons comment le nombre d'incomparabilités (degré de l'extension linéaire comme le sommet dans ) dans pourrait changer. On considère d'abord la paire . Pour la même conclusion suit la symétrie. $G(\mathcal{P})$ $L$ $x_ix_{i+2}$ $x_{i-1}x_{i+1}$

Si , alors ne change pas. Si , alors $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}$ augmente (diminue) de un. Le croquis de la preuve est terminé. $deg(L)$

Théorème . Soit - un graphique d'extension linéaire. Si contient des sommets avec $G(\mathcal{P})$ $G(\mathcal{P})$ $v_1,v_2$ , alors il y a tel que $deg(v_1)=k,deg(v_2)=k+2$ $v_3\in G(\mathcal{P})$ . $deg(v_3)=k+1$

Le croquis de la preuve.

Supposons que sont adjacents dans , sinon tout sommet de degré dans est adjacent à un sommet si tel existe avec le degré . $v_1,v_2,deg(v_1)=k,deg(v_2)=k+2$ $G(\mathcal{P})$ $k$ $G(\mathcal{P})$ $k+1$

Considérons le cas où nous avons du lemme précédent tel que $L_1,L_2$

x_{i + 1} ⊥ x_{i + 2} \land x_{i} ∥ x_{i + 2},

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

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

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

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

Commençons maintenant à transposer en direction de . Il est facile de voir que finalement nous pourrions nous arrêter à la position où $x_{i+1}$ $x_1$

pour certains. Le croquis de l'épreuve est terminé.

x_{j} ⊥ x_{i + 1} \land x_{i + 1} ∥ x_{j + 1},

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

j < i - 1

$j<i-1$

Oleksandr Bondarenko
la source

Dans la preuve du théorème, je ne suis pas la première phrase. En ce qui concerne la notation, j'ai généralement vu

utilisé pour indiquer que

sont comparables.

x \sim y

$x \sim y$

x

$x$

y

$y$

András Salamon

@ András Salamon J'ai ajouté quelques éclaircissements (degrés de

) à la première phrase de la preuve du théorème.

v_{1}, v_{2}

$v_1,v_2$

Oleksandr Bondarenko

x ⊥ y

$x\perp y$

Ensembles de degrés pour les graphiques d'extension linéaire

Réponses: