Semigrafo
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/de/Half_graph_14.svg/220px-Half_graph_14.svg.png)
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 . [1]
Definición
[editar]Para definir el semigrafo en vértices y , conectamos a a por una arista siempre que . [1]
Esta misma construcción también se puede definir para grafos infinitos sobre dos copias de cualquier conjunto ordenado de vértices. [1] El semigrafo sobre los números naturales (con su orden habitual) tiene la propiedad de que cada vértice tiene grado finito, como mucho . Los vértices del otro lado de la bipartición tienen grado infinito. [2]
Propiedades
[editar]Emparejamiento
[editar]El semigrafo tiene un emparejamiento perfecto único. Esto es fácil de ver por inducción: debe coincidir con su único vecino, , 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. [3]
En grafos de número cromático incontable
[editar]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. [4]
Aplicaciones
[editar]Regularidad
[editar]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 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 grafos que no contienen al semigrafo de tamaño . como un subgrafo inducido obedece a una versión más fuerte del lema de regularidad sin pares irregulares. [6]
Estabilidad
[editar]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 de la teoría, una fórmula en dos tuplas finitas de variables libres y , y un sistema de una cantidad contable de valores y para estas variables tales que las parejas forman las aristas de un semigrafo contable en los vértices y . 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. [7]
Referencias
[editar]- ↑ a b c Erdős, Paul (1984), «Some combinatorial, geometric and set theoretic problems in measure theory», 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), «On the order of countable graphs», European Journal of Combinatorics 24 (6): 649-663, MR 1995579, arXiv:math/0404319, doi:10.1016/S0195-6698(03)00064-7.
- ↑ Godsil, C. D. (1985), «Inverses of trees», Combinatorica 5 (1): 33-39, doi:10.1007/bf02579440.. See in particular Lemma 2.1.
- ↑ Erdős, Paul; Hajnal, András (1985), «Chromatic number of finite and infinite graphs and hypergraphs», Discrete Mathematics 53: 281-285, MR 786496, doi:10.1016/0012-365X(85)90148-7.. The result that graphs of uncountable chromatic number contain an infinite half graph is credited in this paper to Hajnal and cited to a 1973 paper of the same authors with Shelah, but that paper states the result only in the weaker form that graphs of uncountable chromatic number contain complete bipartite graphs where one side is any finite number and the other side is infinite.
- ↑ Conlon, David; Fox, Jacob (2012), «Bounds for graph regularity and removal lemmas», Geometric and Functional Analysis 22 (5): 1191-1256, MR 2989432, arXiv:1107.4829, doi:10.1007/s00039-012-0171-x.
- ↑ Malliaris, M.; Shelah, S. (2014), «Regularity lemmas for stable graphs», Transactions of the American Mathematical Society 366 (3): 1551-1585, MR 3145742, arXiv:1102.3904, doi:10.1090/S0002-9947-2013-05820-5.
- ↑ Shelah, S. (1990), Classification theory and the number of nonisomorphic models, Studies in Logic and the Foundations of Mathematics 92 (2nd edición), Amsterdam: North-Holland Publishing Co., pp. 30-31, ISBN 0-444-70260-1, MR 1083551.