En la teoría de grafos , una rama de las matemáticas , un medio gráfico es un tipo especial de gráfico bipartito . Estas gráficas se denominan medias gráficas porque tienen aproximadamente la mitad de los bordes de una gráfica bipartita completa en los mismos vértices. El nombre de estos gráficos fue dado por Paul Erd givens y András Hajnal . [1]
Definición
Para definir la mitad del gráfico en vértices y , conectar a por un borde siempre que . [1]
El mismo concepto también se puede definir de la misma manera para gráficos infinitos sobre dos copias de cualquier conjunto ordenado de vértices. [1] La mitad del gráfico sobre los números naturales (con su orden habitual) tiene la propiedad de que cada vérticetiene un grado finito , como máximo. Los vértices del otro lado de la bipartición tienen un grado infinito. [2]
Propiedades
Pareo
La mitad del gráfico tiene una combinación perfecta única . Esto es fácil de ver por inducción: debe coincidir con su único vecino, , y los vértices restantes forman otra mitad de gráfico. Más claramente, cada gráfico bipartito con una coincidencia perfecta única es un subgráfico de medio gráfico. [3]
En gráficos de incontable número cromático
Si el número cromático de un gráfico es incontable , entonces el gráfico necesariamente contiene como subgráfico un medio gráfico sobre los números naturales. Este medio gráfico, a su vez, contiene todos los gráficos bipartitos completos en los que un lado de la bipartición es finito y el otro lado es infinito numerable. [4]
Aplicaciones
Regularidad
Una aplicación para la mitad del gráfico ocurre en el lema de regularidad de Szemerédi , que establece que los vértices de cualquier gráfico 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 formas como un gráfico aleatorio de alguna densidad particular). Si la mitad del gráfico se divide de esta manera en subconjuntos, el número de pares irregulares será al menos proporcional a . 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. [5] Por otro lado, para cualquier número entero, los gráficos que no tienen -La mitad del gráfico del vértice como un subgráfico inducido obedece a una versión más fuerte del lema de regularidad sin pares irregulares. [6]
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 pocos tipos ) por la inexistencia de medias gráficas infinitas contables. Shelah define una teoría completa que tiene la propiedad de orden si existe un modelo de la teoría, una fórmula en dos tuplas finitas de variables libres y , y un sistema de muchos valores contables y para estas variables de modo que los pares Formar los bordes de un medio gráfico contable en vértices. y . Intuitivamente, la existencia de estas medias gráficas permite construir infinitos conjuntos 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. [7]
Referencias
- ↑ a b c Erdős, Paul (1984), "Algunos problemas combinatorios, geométricos y teóricos de conjuntos en la teoría de la medida", en Kölzow, D .; Maharam-Stone, D. (eds.), Measure Theory Oberwolfach 1983 , Lecture Notes in Mathematics, 1089 , Springer
- ^ Nešetřil, Jaroslav ; Shelah, Saharon (2003), "En el orden de los gráficos contables", European Journal of Combinatorics , 24 (6): 649–663, arXiv : math / 0404319 , doi : 10.1016 / S0195-6698 (03) 00064-7 , Señor 1995579
- ^ Godsil, CD (1985), "Inverses of trees", Combinatorica , 5 (1): 33–39, doi : 10.1007 / bf02579440. Ver en particular el Lema 2.1.
- ^ Erdős, Paul ; Hajnal, András (1985), "Número cromático de gráficos e hipergráficos finitos e infinitos" (PDF) , Matemáticas discretas , 53 : 281-285, doi : 10.1016 / 0012-365X (85) 90148-7 , MR 0786496. El resultado de que las gráficas de número cromático incontable contienen una mitad infinita se acredita en este artículo a Hajnal y se cita a un artículo de 1973 de los mismos autores con Shelah, pero ese artículo establece el resultado solo en la forma más débil que las gráficas de número cromático incontable contienen gráficos bipartitos completos donde un lado es cualquier número finito y el otro lado es infinito.
- ^ Conlon, David ; Fox, Jacob (2012), "Límites para la regularidad de los gráficos y los lemas de eliminación", Análisis geométrico y funcional , 22 (5): 1191-1256, arXiv : 1107.4829 , doi : 10.1007 / s00039-012-0171-x , MR 2989432
- ^ Malliaris, M .; Shelah, S. (2014), "Lemas de regularidad para gráficos estables", Transactions of the American Mathematical Society , 366 (3): 1551-1585, arXiv : 1102.3904 , doi : 10.1090 / S0002-9947-2013-05820-5 , Señor 3145742
- ^ Shelah, S. (1990), Teoría de la clasificación y el número de modelos no isomórficos , Studies in Logic and the Foundations of Mathematics, 92 (2ª ed.), Amsterdam: North-Holland Publishing Co., págs. 30–31, ISBN 0-444-70260-1, MR 1083551