Semigrafo

Un grafo medio de 14 vértices

En teoría de grafos, una rama de las matemáticas, un semigrafo es un tipo especial de grafo bipartito . Estos grafos se denominan así porque tienen aproximadamente la mitad de las aristas que un grafo bipartito completo en los mismos vértices. El nombre fue dado a estos gráficos por Paul Erdős y András Hajnal . ​

Definición

Para definir el semigrafo en $2n$ vértices $u_{1},\dots u_{n}$ y $v_{1},\dots v_{n}$, conectamos a $u_{i}$ a $v_{j}$ por una arista siempre que $i\leq j$ . ​

Esta misma construcción también se puede definir para grafos infinitos sobre dos copias de cualquier conjunto ordenado de vértices. ​ El semigrafo sobre los números naturales (con su orden habitual) tiene la propiedad de que cada vértice $v_{j}$ tiene grado finito, como mucho $j$ . Los vértices del otro lado de la bipartición tienen grado infinito. ​

Propiedades

Emparejamiento

El semigrafo tiene un emparejamiento perfecto único. Esto es fácil de ver por inducción: $u_{n}$ debe coincidir con su único vecino, $v_{n}$, y los vértices restantes forman otro semigrafo. Más fuertemente, cada grafo bipartito con una combinación perfecta única es un subgrafo de un semigrafo. ​

En grafos de número cromático incontable

Si el número cromático de un grafo es incontable, entonces el grafo necesariamente contiene como subgrafo un semigrafo sobre los números naturales. Este semigrafo, a su vez, contiene todos los grafos bipartitos completos en los que un lado de la bipartición es finito y el otro lado es contablemente infinito. ​

Aplicaciones

Regularidad

Una aplicación para el semigrafo ocurre en el lema de regularidad de Szemerédi, que establece que los vértices de cualquier grafo se pueden dividir en un número constante de subconjuntos de igual tamaño, de modo que la mayoría de los pares de subconjuntos son regulares (los bordes que conectan el par se comportan en ciertas maneras como un grafo aleatorio de alguna densidad particular). Si el semigrafo se divide de esta manera en $k$ subconjuntos, el número de pares irregulares será al menos proporcional a $k$ . Por lo tanto, no es posible fortalecer el lema de regularidad para mostrar la existencia de una partición para la cual todos los pares son regulares. ​ Por otro lado, para cualquier número entero $k$, los grafos que no contienen al semigrafo de tamaño $2k$. como un subgrafo inducido obedece a una versión más fuerte del lema de regularidad sin pares irregulares. ​

Estabilidad

El teorema de la fórmula inestable de Saharon Shelah en la teoría de modelos caracteriza las teorías estables (teorías completas que tienen una cantidad menor de tipos) por la inexistencia de semigrafos contablemente infinitos. Shelah define que una teoría completa tiene la propiedad de orden si existe un modelo $M$ de la teoría, una fórmula $\phi ({\bar {x}},{\bar {y}})$ en dos tuplas finitas de variables libres ${\bar {x}}$ y ${\bar {y}}$, y un sistema de una cantidad contable de valores ${\bar {x}}_{i}$ y ${\bar {y}}_{i}$ para estas variables tales que las parejas ${\bigl \{}({\bar {x}}_{i},{\bar {y}}_{i})\mid M\models \phi ({\bar {x}}_{i},{\bar {y}}_{j}){\bigr \}}$ forman las aristas de un semigrafo contable en los vértices ${\bar {x}}_{i}$ y ${\bar {y}}_{i}$ . Intuitivamente, la existencia de estos semigrafos permite construir conjuntos infinitos ordenados dentro del modelo. El teorema de la fórmula inestable establece que una teoría completa es estable si y solo si no tiene la propiedad de orden. ​