En matemáticas, un poset de incidencia u orden de incidencia es un tipo de conjunto parcialmente ordenado que representa la relación de incidencia entre vértices y aristas de un grafo no dirigido . El poset de incidencia de un grafo G tiene un elemento por cada vértice o arista en G ; en esta pose, hay una relación de orden x ≤ y si y solo si x = y o x es un vértice, y es una arista y x es un punto final de y .
A modo de ejemplo, un poset en zigzag o valla con un número impar de elementos, con relaciones de orden alterno a < b > c < d ... es un poset de incidencia de un gráfico de ruta .
Cada poset de incidencia de un gráfico no vacío tiene una altura de dos. Su ancho es igual al número de aristas más el número de componentes conectados acíclicos.
Los conjuntos de incidencias se han estudiado particularmente con respecto a su dimensión de orden y su relación con las propiedades del gráfico subyacente. El conjunto de incidencias de un grafo conexo G tiene una dimensión de orden como máximo dos si y solo si G es un grafo de trayectoria, y tiene una dimensión de orden como máximo tres si y solo si G es como máximo plano ( teorema de Schnyder ). [1] Sin embargo, los gráficos cuyas posets de incidencia tienen una dimensión de orden 4 pueden ser densos [2] y pueden tener un número cromático ilimitado . [3] Todo grafo completo sobre n vértices, y por extensión todo grafo sobre nvértices, tiene un poset de incidencia con dimensión de orden O (log log n ). [4] Si una pose de incidencia tiene una dimensión alta, debe contener copias de las poses de incidencia de todos los árboles pequeños, ya sea como subórdenes o como duales de subórdenes. [5]