Medio gráfico

En un medio grafo, cada par de vértices se encuentran a una distancia de uno, dos o tres. Cualquier par de vértices${\displaystyle u_{i}}$y${\displaystyle u_{j}}$están a distancia dos a través de un camino que pasa${\displaystyle v_{n}}$y cualesquiera dos vértices${\displaystyle v_{i}}$y${\displaystyle v_{j}}$están a distancia dos a través de un camino que pasa${\displaystyle u_{1}}$. Si dos vértices en lados opuestos de la bipartición no son adyacentes (a distancia uno), entonces están a distancia tres a través de un camino que pasa por ambos${\displaystyle u_{1}}$y${\displaystyle v_{n}}$Los semigrafos son un caso especial de los grafos de cadena bipartitos (grafos bipartitos en los que, a cada lado de la bipartición, los vértices se pueden ordenar por inclusión de vecindad), que a su vez son un caso especial de los grafos bipartitos con herencia de distancia . Por lo tanto, los semigrafos tienen herencia de distancia. Es decir, en cada subgrafo inducido conexo de un semigrafo, las distancias son las mismas que en el semigrafo mismo. ^{[ 3 ]}

La mitad del gráfico tiene una coincidencia perfecta única . Esto se puede ver fácilmente por inducción:${\displaystyle u_{n}}$debe coincidir con su único vecino,${\displaystyle v_{n}}$y los vértices restantes forman otro semigrafo. Más concretamente, todo grafo bipartito con un emparejamiento perfecto único es un subgrafo de un semigrafo. ^{[ 4 ]}

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 todo grafo bipartito completo en el que un lado de la bipartición es finito y el otro es infinito numerable. ^{[ 5 ]}

Una aplicación del medio grafo se encuentra en el lema de regularidad de Szemerédi , que establece que los vértices de cualquier grafo pueden particionarse en un número constante de subconjuntos de igual tamaño, de modo que la mayoría de los pares de subconjuntos son regulares (las aristas que conectan el par se comportan de ciertas maneras como un grafo aleatorio de alguna densidad particular). Si el medio grafo se particiona de esta manera en${\displaystyle k}$subconjuntos, el número de pares irregulares será al menos proporcional a${\displaystyle k}$Por lo tanto, no es posible fortalecer el lema de regularidad para demostrar la existencia de una partición para la cual todos los pares sean regulares. ^{[ 6 ]} Por otro lado, para cualquier entero${\displaystyle k}$, los gráficos que no tienen un${\displaystyle 2k}$-un semigrafo de vértices como subgrafo inducido obedece una versión más fuerte del lema de regularidad sin pares irregulares. ^{[ 7 ]}

El teorema de la fórmula inestable de Saharon Shelah en teoría de modelos caracteriza las teorías estables ( teorías completas que tienen pocos tipos ) por la no existencia de semigrafos infinitos numerables. Shelah define una teoría completa como aquella que tiene la propiedad de orden si existe un modelo${\displaystyle M}$de la teoría, una fórmula${\displaystyle \phi ({\bar {x}},{\bar {y}})}$sobre dos tuplas finitas de variables libres${\displaystyle {\bar {x}}}$y${\displaystyle {\bar {y}}}$y un sistema de una cantidad numerable de valores${\displaystyle {\bar {x}}_{i}}$y${\displaystyle {\bar {y}}_{i}}$para estas variables de tal manera que los pares${\displaystyle {\bigl \{}({\bar {x}}_{i},{\bar {y}}_{i})\mid M\models \phi ({\bar {x}}_{i},{\bar {y}}_{j}){\bigr \}}}$formen las aristas de un semigrafo contable en vértices${\displaystyle {\bar {x}}_{i}}$y${\displaystyle {\bar {y}}_{i}}$Intuitivamente, la existencia de estos semigrafos permite construir conjuntos ordenados infinitos dentro del modelo. El teorema de la fórmula inestable establece que una teoría completa es estable si y solo si no posee la propiedad de orden. ^{[ 8 ]}