Gráfico de Rado - Rado graph

En la matemática campo de la teoría de grafos , el gráfico Rado , gráfico Erdős-Rényi , o grafo aleatorio es un infinito numerable gráfica que puede ser construido (con una probabilidad ) seleccionando de forma independiente al azar para cada par de sus vértices si para conectar los vértices por un borde. Los nombres de este gráfico honran a Richard Rado , Paul Erdős y Alfréd Rényi , matemáticos que lo estudiaron a principios de la década de 1960; aparece incluso antes en la obra de Wilhelm Ackermann  ( 1937 ). El gráfico de Rado también se puede construir de forma no aleatoria, simétricamente la relación de pertenencia de los conjuntos finitos hereditariamente , aplicando el predicado BIT a las representaciones binarias de los números naturales , o como un gráfico de Paley infinito que tiene aristas que conectan pares de números primos. congruentes con 1 mod 4 que son residuos cuadráticos módulo entre sí.

Cada grafo finito o infinito numerable es un subgrafo inducido del grafo de Rado, y se puede encontrar como un subgrafo inducido por un algoritmo codicioso que construye el subgrafo un vértice a la vez. El gráfico de Rado está definido de forma única, entre los gráficos contables, por una propiedad de extensión que garantiza la exactitud de este algoritmo: no importa qué vértices ya se han elegido para formar parte del subgráfico inducido, y no importa qué patrón de adyacencias se necesita extender el subgrafo por un vértice más, siempre existirá otro vértice con ese patrón de adyacencias que el algoritmo codicioso puede elegir.

El gráfico de Rado es muy simétrico: cualquier isomorfismo de sus subgráficos inducidos puede extenderse a una simetría de todo el gráfico. Las oraciones lógicas de primer orden que son verdaderas del gráfico de Rado también lo son para casi todos los gráficos finitos aleatorios, y las oraciones que son falsas para el gráfico de Rado también lo son para casi todos los gráficos finitos. En la teoría de modelos , el gráfico de Rado forma un ejemplo de un modelo saturado de una teoría ω categórica y completa .

Historia

El gráfico de Rado fue construido por primera vez por Ackermann (1937) de dos formas, con vértices, ya sea los conjuntos finitos hereditarios o los números naturales. (Estrictamente hablando, Ackermann describió una gráfica dirigida , y la gráfica de Rado es la gráfica no dirigida correspondiente dada al olvidar las direcciones en los bordes). Erdős y Rényi (1963) construyeron la gráfica de Rado como la gráfica aleatoria en un número contable de puntos. Demostraron que tiene infinitos automorfismos, y su argumento también muestra que es único, aunque no lo mencionaron explícitamente. Richard Rado  ( 1964 ) redescubrió el grafo de Rado como grafo universal y le dio una construcción explícita con el conjunto de vértices de los números naturales. La construcción de Rado es esencialmente equivalente a una de las construcciones de Ackermann.

Construcciones

Numeros binarios

Ackermann (1937) y Rado (1964) construyeron el gráfico de Rado utilizando el predicado BIT de la siguiente manera. Identificaron los vértices del gráfico con los números naturales 0, 1, 2, ... Una arista conecta los vértices y en el gráfico (donde ) siempre que el th bit de la representación binaria de es distinto de cero. Así, por ejemplo, los vecinos del vértice 0 constan de todos los vértices impares, porque los números cuyo bit 0 es distinto de cero son exactamente los números impares. El vértice 1 tiene un vecino más pequeño, el vértice 0, ya que 1 es impar y el vértice 0 está conectado a todos los vértices impares. Los vecinos más grandes del vértice 1 son todos vértices con números congruentes con 2 o 3 módulo 4, porque esos son exactamente los números con un bit distinto de cero en el índice 1. ${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle x <y}$${\ Displaystyle x}$${\ Displaystyle y}$

Gráfico aleatorio

El gráfico de Rado surge casi con seguridad en el modelo de Erdős-Rényi de un gráfico aleatorio en innumerables vértices. Específicamente, uno puede formar un gráfico infinito eligiendo, independientemente y con probabilidad 1/2 para cada par de vértices, si conectar los dos vértices por una arista. Con probabilidad 1, el gráfico resultante es isomorfo al gráfico de Rado. Esta construcción también funciona si se usa una probabilidad fija que no sea igual a 0 o 1 en lugar de 1/2. ${\ Displaystyle p}$

Este resultado, mostrado por Paul Erdős y Alfréd Rényi  ( 1963 ), justifica el artículo definido en el nombre alternativo común " el gráfico aleatorio" para el gráfico de Rado. Dibujar repetidamente un gráfico finito a partir del modelo de Erdős-Rényi conducirá en general a gráficos diferentes; sin embargo, cuando se aplica a un gráfico infinito numerable, el modelo casi siempre produce el mismo gráfico infinito.

Para cualquier gráfico generado aleatoriamente de esta manera, el gráfico de complemento se puede obtener al mismo tiempo invirtiendo todas las opciones: incluyendo un borde cuando el primer gráfico no incluye el mismo borde, y viceversa. Esta construcción del gráfico de complemento es una instancia del mismo proceso de elegir aleatoria e independientemente si se incluye cada borde, por lo que también (con probabilidad 1) genera el gráfico de Rado. Por lo tanto, el gráfico de Rado es un gráfico autocomplementario .

Otras construcciones

En una de las construcciones originales de Ackermann de 1937, los vértices del grafo de Rado están indexados por los conjuntos finitos hereditariamente, y hay una arista entre dos vértices exactamente cuando uno de los conjuntos finitos correspondientes es miembro del otro. Una construcción similar puede basarse en la paradoja de Skolem , el hecho de que existe un modelo contable para la teoría de conjuntos de primer orden. Se puede construir el gráfico de Rado a partir de dicho modelo creando un vértice para cada conjunto, con un borde que conecta cada par de conjuntos donde un conjunto del par es miembro del otro.

El gráfico de Rado también puede estar formado por una construcción similar a la de los gráficos de Paley , tomando como vértices de un gráfico todos los números primos que son congruentes con 1 módulo 4, y conectando dos vértices por una arista siempre que uno de los dos números sea un residuo cuadrático módulo el otro. Por reciprocidad cuadrática y la restricción de los vértices a primos congruentes a 1 mod 4, esta es una relación simétrica , por lo que define un grafo no dirigido, que resulta ser isomorfo al grafo de Rado.

Otra construcción del grafo de Rado muestra que es un grafo circulante infinito , con los enteros como sus vértices y con una arista entre cada dos enteros cuya distancia (el valor absoluto de su diferencia) pertenece a un conjunto particular . Para construir el gráfico de Rado de esta manera, se puede elegir al azar, o eligiendo la función indicadora de para que sea la concatenación de todas las secuencias binarias finitas . ${\ Displaystyle S}$${\ Displaystyle S}$${\ Displaystyle S}$

El gráfico de Rado también se puede construir como el gráfico de intersección de bloques de un diseño de bloques infinitos en el que el número de puntos y el tamaño de cada bloque son infinitos contables . También se puede construir como el límite de Fraïssé de la clase de grafos finitos.

Propiedades

Extensión

El gráfico de Rado satisface la siguiente propiedad de extensión: por cada dos conjuntos finitos disjuntos de vértices y , existe un vértice fuera de ambos conjuntos que está conectado a todos los vértices en , pero no tiene vecinos en . Por ejemplo, con la definición de número binario del gráfico de Rado, dejemos ${\ Displaystyle U}$${\ Displaystyle V}$${\ Displaystyle x}$${\ Displaystyle U}$${\ Displaystyle V}$

Luego, los bits distintos de cero en la representación binaria de hacen que sea adyacente a todo en . Sin embargo, no tiene bits distintos de cero en su representación binaria correspondiente a los vértices en , y es tan grande que el ésimo bit de cada elemento de es cero. Por lo tanto, no es adyacente a ningún vértice en . ${\ Displaystyle x}$${\ Displaystyle U}$${\ Displaystyle x}$${\ Displaystyle V}$${\ Displaystyle x}$${\ Displaystyle x}$${\ Displaystyle V}$${\ Displaystyle x}$${\ Displaystyle V}$

Con la definición de grafo aleatorio del grafo de Rado, cada vértice fuera de la unión de y tiene probabilidad de cumplir con la propiedad de extensión, independientemente de los otros vértices. Debido a que hay infinitos vértices para elegir, cada uno con la misma probabilidad finita de éxito, la probabilidad es una de que exista un vértice que cumpla con la propiedad de extensión. Con la definición del gráfico de Paley, para cualquier conjunto y , según el teorema del resto chino , los números que son residuos cuadráticos módulo cada primo y no residuos módulo cada primo en forma de una secuencia periódica, por lo que según el teorema de Dirichlet sobre los primos en progresiones aritméticas este número- grafo teórico tiene la propiedad de extensión. ${\ Displaystyle U}$${\ Displaystyle V}$${\ Displaystyle 1/2 ^ {| U | + | V |}}$${\ Displaystyle U}$${\ Displaystyle V}$${\ Displaystyle U}$${\ Displaystyle V}$

Subgrafos inducidos

La propiedad de extensión se puede utilizar para construir copias isomórficas de cualquier gráfico finito o infinito numerable dentro del gráfico de Rado, como subgrafos inducidos . Para hacerlo, ordene los vértices de y agregue vértices en el mismo orden a una copia parcial de dentro del gráfico de Rado. En cada paso, el siguiente vértice en será adyacente a algún conjunto de vértices en que están antes en el orden de los vértices, y no adyacente al conjunto restante de vértices anteriores en . Por la propiedad de extensión, el gráfico de Rado también tendrá un vértice adyacente a todos los vértices de la copia parcial que corresponden a miembros de y no adyacente a todos los vértices de la copia parcial que corresponden a miembros de . Agregar a la copia parcial de produce una copia parcial más grande, con un vértice más. ${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle U}$${\ Displaystyle G}$${\ Displaystyle V}$${\ Displaystyle G}$${\ Displaystyle x}$${\ Displaystyle U}$${\ Displaystyle V}$${\ Displaystyle x}$${\ Displaystyle G}$

Este método forma la base para una prueba por inducción , con el subgrafo de vértice 0 como su caso base, de que cada grafo finito o infinito numerable es un subgrafo inducido del grafo de Rado.

Unicidad

El gráfico de Rado es, hasta el isomorfismo del gráfico , el único gráfico contable con la propiedad de extensión. Por ejemplo, sean y sean dos grafos contables con la propiedad de extensión, sean y sean subgrafos inducidos finitos isomórficos de y respectivamente, y sean y sean los primeros vértices en una enumeración de los vértices de y respectivamente que no pertenecen a y . Luego, aplicando la propiedad de extensión dos veces, se pueden encontrar subgrafos inducidos isomorfos y que incluyen y junto con todos los vértices de los subgrafos anteriores. Al repetir este proceso, se puede construir una secuencia de isomorfismos entre subgrafos inducidos que eventualmente incluye todos los vértices en y . Por lo tanto, por el método de ida y vuelta , y debe ser isomórfico. Debido a que las gráficas construidas por la construcción de gráficas aleatorias, la construcción de números binarios y la construcción de gráficas de Paley son todas gráficas contables con la propiedad de extensión, este argumento muestra que todas son isomorfas entre sí. ${\ Displaystyle G}$${\ Displaystyle H}$${\ Displaystyle G_ {i}}$${\ Displaystyle H_ {i}}$${\ Displaystyle G}$${\ Displaystyle H}$${\ Displaystyle g_ {i}}$${\ Displaystyle h_ {i}}$${\ Displaystyle G}$${\ Displaystyle H}$${\ Displaystyle G_ {i}}$${\ Displaystyle H_ {i}}$${\ Displaystyle G_ {i + 1}}$${\ Displaystyle H_ {i + 1}}$${\ Displaystyle g_ {i}}$${\ Displaystyle h_ {i}}$${\ Displaystyle G}$${\ Displaystyle H}$${\ Displaystyle G}$${\ Displaystyle H}$

Simetría

La aplicación de la construcción de ida y vuelta a dos subgráficos finitos isomórficos cualesquiera del gráfico de Rado extiende su isomorfismo a un automorfismo de todo el gráfico de Rado. El hecho de que cada isomorfismo de subgrafos finitos se extienda a un automorfismo de todo el grafo se expresa diciendo que el grafo de Rado es ultrahomogéneo . En particular, hay un automorfismo que lleva cualquier par ordenado de vértices adyacentes a cualquier otro par ordenado, por lo que el gráfico de Rado es un gráfico simétrico .

El grupo de automorfismo del gráfico de Rado es un grupo simple , cuyo número de elementos es la cardinalidad del continuo . Cada subgrupo de este grupo cuyo índice es menor que la cardinalidad del continuo puede intercalarse entre el estabilizador puntual y el estabilizador de un conjunto finito de vértices.

La construcción del gráfico de Rado como un gráfico circulante infinito muestra que su grupo de simetría incluye automorfismos que generan un grupo cíclico infinito transitivo . El conjunto de diferencias de esta construcción (el conjunto de distancias en los enteros entre vértices adyacentes) se puede restringir para incluir la diferencia 1, sin afectar la exactitud de esta construcción, de lo cual se sigue que el gráfico de Rado contiene una trayectoria infinita hamiltoniana cuyas simetrías son un subgrupo de las simetrías de todo el gráfico.

Robustez frente a cambios finitos

Si se forma un gráfico a partir del gráfico de Rado eliminando cualquier número finito de aristas o vértices, o agregando un número finito de aristas, el cambio no afecta la propiedad de extensión del gráfico. Para cualquier par de conjuntos y todavía es posible encontrar un vértice en el gráfico modificado que es adyacente a todo en y no adyacente a todo en , mediante la adición de las partes modificadas de a y la aplicación de la propiedad de extensión en el gráfico Rado sin modificar. Por lo tanto, cualquier modificación finita de este tipo da como resultado un gráfico que es isomórfico al gráfico de Rado. ${\ Displaystyle G}$${\ Displaystyle U}$${\ Displaystyle V}$${\ Displaystyle U}$${\ Displaystyle V}$${\ Displaystyle G}$${\ Displaystyle V}$

Dividir

Para cualquier partición de los vértices del grafo de Rado en dos conjuntos y , o más generalmente para cualquier partición en un número finito de subconjuntos, al menos uno de los subgrafos inducidos por uno de los conjuntos de particiones es isomorfo a todo el grafo de Rado. Cameron (2001) da la siguiente prueba corta: si ninguna de las partes induce un subgrafo isomorfo a la gráfica Rado, todos ellos dejar de tener la propiedad de extensión, y uno puede encontrar pares de conjuntos y que no puede extenderse dentro de cada subgrafo. Pero entonces, la unión de los conjuntos y la unión de los conjuntos formarían un conjunto que no podría extenderse en todo el gráfico, contradiciendo la propiedad de extensión del gráfico de Rado. Esta propiedad de ser isomórfico a uno de los subgráficos inducidos de cualquier partición se mantiene en solo tres gráficos no dirigidos infinitos contables: el gráfico de Rado, el gráfico completo y el gráfico vacío . Bonato, Cameron y Delić (2000) y Diestel et al. (2007) investigan gráficas dirigidas infinitas con la misma propiedad de partición; todos se forman eligiendo orientaciones para los bordes del gráfico completo o el gráfico de Rado. ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle U_ {i}}$${\ Displaystyle V_ {i}}$${\ Displaystyle U_ {i}}$${\ Displaystyle V_ {i}}$

Un resultado relacionado se refiere a las particiones de borde en lugar de las particiones de vértice: para cada partición de los bordes del gráfico de Rado en un número finito de conjuntos, hay un subgráfico isomórfico para todo el gráfico de Rado que usa como máximo dos de los colores. Sin embargo, es posible que no exista necesariamente un subgrafo isomorfo que use solo un color de bordes.

Teoría de modelos y leyes 0-1

Fagin (1976) utilizó el gráfico de Rado para probar una ley de cero a uno para enunciados de primer orden en la lógica de los gráficos . Cuando una declaración lógica de este tipo es verdadera o falsa para el gráfico de Rado, también es verdadera o falsa (respectivamente) para casi todos los gráficos finitos.

Propiedades de primer orden

El lenguaje de gráficos de primer orden es la colección de oraciones bien formadas en lógica matemática formadas a partir de variables que representan los vértices de gráficos, cuantificadores universales y existenciales , conectivos lógicos y predicados para la igualdad y adyacencia de vértices. Por ejemplo, la condición de que un gráfico no tenga vértices aislados puede expresarse mediante la oración

donde el símbolo indica la relación de adyacencia entre dos vértices. Esta oración es verdadera para algunos gráficos y falsa para otros; se dice que un grafo modela , escrito , si es cierto de los vértices y la relación de adyacencia de . ${\ Displaystyle \ sim}$${\ Displaystyle S}$${\ Displaystyle G}$ ${\ Displaystyle S}$${\ Displaystyle G \ modelos S}$${\ Displaystyle S}$${\ Displaystyle G}$

La propiedad de extensión del grafo de Rado puede expresarse mediante una colección de oraciones de primer orden , indicando que para cada elección de vértices en un conjunto y vértices en un conjunto , todos distintos, existe un vértice adyacente a todo en y no adyacente a todo. en . Por ejemplo, se puede escribir como ${\ Displaystyle E_ {i, j}}$${\ Displaystyle i}$${\ Displaystyle A}$${\ Displaystyle j}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle E_ {1,1}}$

$${\ Displaystyle \ forall a: \ forall b: a \ neq b \ rightarrow \ existe c: c \ neq a \ wedge c \ neq b \ wedge c \ sim a \ wedge \ lnot (c \ sim b).}$$

Lo completo

Gaifman (1964) demostró que las oraciones , junto con las oraciones adicionales que afirman que la relación de adyacencia es

simétrica y antirreflexiva (es decir, que un gráfico que modela estas oraciones no está dirigido y no tiene bucles propios), son los axiomas de una teoría completa . Esto significa que, para cada oración de primer orden , se puede probar exactamente uno de y su negación a partir de estos axiomas. Debido a que el gráfico de Rado modela los axiomas de extensión, modela todas las oraciones en esta teoría. ${\ Displaystyle E_ {i, j}}$${\ Displaystyle S}$${\ Displaystyle S}$

En lógica, una teoría que tiene un solo modelo (hasta el isomorfismo) con una cardinalidad infinita dada se llama

-categórica . El hecho de que el gráfico de Rado sea el único gráfico contable con la propiedad de extensión implica que también es el único modelo contable para su teoría. Esta propiedad de unicidad del gráfico de Rado se puede expresar diciendo que la teoría del gráfico de Rado es ω-categórica . Łoś y Vaught demostraron en 1954 que cuando una teoría es –categórica (para algún cardinal infinito ) y, además, no tiene modelos finitos, entonces la teoría debe ser completa. Por lo tanto, el teorema de Gaifman de que la teoría del gráfico de Rado es completa se deriva de la unicidad del gráfico de Rado mediante la prueba de Łoś – Vaught . ${\ Displaystyle \ lambda}$${\ Displaystyle \ lambda}$${\ Displaystyle \ lambda}$${\ Displaystyle \ lambda}$

Gráficos finitos y complejidad computacional

Como demostró Fagin (1976) , los enunciados de primer orden demostrables a partir de los axiomas de extensión y modelados por el gráfico de Rado son exactamente los enunciados verdaderos para casi todos los gráficos finitos aleatorios. Esto significa que si uno elige un gráfico -vertex uniformemente al azar entre todos los gráficos en vértices etiquetados, entonces la probabilidad de que tal oración sea verdadera para el gráfico elegido se acerca a uno en el límite cuando se acerca al infinito. Simétricamente, las oraciones que no están modeladas por el gráfico de Rado son falsas para casi todos los gráficos finitos aleatorios. De ello se deduce que cada oración de primer orden es

casi siempre verdadera o casi siempre falsa para gráficos finitos aleatorios, y estas dos posibilidades se pueden distinguir determinando si el gráfico de Rado modela la oración. La demostración de Fagin utiliza el teorema de la compacidad . Con base en esta equivalencia, la teoría de oraciones modelada por el gráfico de Rado ha sido llamada "la teoría del gráfico aleatorio" o "la teoría casi segura de los gráficos". ${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle n}$

Debido a esta ley 0-1, es posible probar si una oración particular de primer orden es modelada por el gráfico de Rado en una cantidad finita de tiempo, eligiendo un valor lo suficientemente grande de y contando el número de gráficos -vertex que modelan la frase. Sin embargo, aquí, "suficientemente grande" es al menos exponencial en el tamaño de la oración. Por ejemplo, el axioma de extensión implica la existencia de una

camarilla -vertex , pero una camarilla de ese tamaño existe con alta probabilidad solo en gráficos aleatorios de tamaño exponencial en . Es poco probable que la determinación de si el gráfico de Rado modela una oración determinada se pueda hacer más rápidamente que el tiempo exponencial, ya que el problema es PSPACE completo . ${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle E_ {k, 0}}$${\ Displaystyle (k + 1)}$${\ Displaystyle k}$

Modelo saturado

Desde el punto de vista de la teoría del

modelo , el gráfico de Rado es un ejemplo de un modelo saturado . Esta es solo una formulación lógica de la propiedad de que el gráfico de Rado contiene todos los gráficos finitos como subgrafos inducidos.

En este contexto, un tipo es un conjunto de variables junto con una colección de restricciones sobre los valores de algunos o todos los predicados determinados por esas variables; un tipo completo es un tipo que restringe todos los predicados determinados por sus variables. En la teoría de grafos, las variables representan vértices y los predicados son las adyacencias entre vértices, por lo que un tipo completo especifica si una arista está presente o ausente entre cada par de vértices representados por las variables dadas. Es decir, un tipo completo especifica el subgrafo que induce un conjunto particular de variables de vértice.

Un modelo saturado es un modelo que realiza todos los tipos que tienen un número de variables como máximo igual a la cardinalidad del modelo. El gráfico de Rado ha inducido subgrafos de todos los tipos finitos o infinitos contables, por lo que está saturado.

Conceptos relacionados

Aunque el gráfico de Rado es universal para subgráficos inducidos, no es universal para incrustaciones isométricas de gráficos, donde una incrustación isométrica es un isomorfismo de gráfico que conserva la distancia . El gráfico de Rado tiene un diámetro dos, por lo que cualquier gráfico con un diámetro mayor no se incrusta isométricamente en él. Moss ( 1989 , 1991 ) ha descrito una familia de gráficos universales para la incrustación isométrica, uno para cada posible diámetro de gráfico finito; la gráfica de su familia con diámetro dos es la gráfica de Rado.

Las gráficas de Henson son

gráficas contables (una para cada entero positivo ) que no contienen una camarilla -vertex y son universales para gráficas sin -clique. Se pueden construir como subgrafos inducidos del gráfico de Rado. El gráfico de Rado, los gráficos de Henson y sus complementos, las uniones disjuntas de camarillas infinitas numerables y sus complementos, y las uniones dislocadas infinitas de camarillas finitas isomórficas y sus complementos son los únicos grafos homogéneos numerables infinitos posibles . ${\ Displaystyle i}$${\ Displaystyle i}$${\ Displaystyle i}$

La propiedad de universalidad del gráfico de Rado se puede extender a los gráficos de color de borde; es decir, gráficos en los que los bordes se han asignado a diferentes clases de color, pero sin el requisito habitual de coloración de los bordes de que cada clase de color forme una coincidencia . Para cualquier número de colores finito o numerablemente infinito , existe un gráfico único de color de borde infinito numerable de modo que cada isomorfismo parcial de un gráfico finito de color de borde puede extenderse a un isomorfismo completo. Con esta notación, el gráfico de Rado es justo .

Truss (1985) investiga los grupos de automorfismos de esta familia más general de gráficos. ${\ Displaystyle \ chi}$${\ Displaystyle \ chi}$${\ Displaystyle G _ {\ chi}}$${\ Displaystyle \ chi}$${\ Displaystyle G_ {1}}$

De las consideraciones de la teoría clásica del modelo de la construcción de un modelo saturado se deduce que bajo la hipótesis del

continuo CH, hay un grafo universal con un continuo de muchos vértices. Por supuesto, bajo CH, el continuo es igual a , la primera cardinal incontable . Shelah ( 1984 , 1990 ) utiliza el forzamiento para investigar grafos universales con muchos vértices y muestra que incluso en ausencia de CH, puede existir un grafo universal de tamaño . También investiga cuestiones análogas para cardinalidades superiores. ${\ Displaystyle \ aleph _ {1}}$${\ Displaystyle \ aleph _ {1}}$${\ Displaystyle \ aleph _ {1}}$

Notas

Referencias

• Ackermann, Wilhelm (1937), "Die Widerspruchsfreiheit der allgemeinen Mengenlehre", Mathematische Annalen , 114 (1): 305–315, doi : 10.1007 / BF01594179
• Bonato, Anthony; Cameron, Peter ; Delić, Dejan (2000), "Torneos y órdenes con la propiedad del casillero", Canadian Mathematical Bulletin , 43 (4): 397–405, doi : 10.4153 / CMB-2000-047-6 , MR  1793941.
• Cameron, Peter J. (1990), Grupos de permutación oligomórfica , Serie de notas de conferencia de la Sociedad Matemática de Londres, 152 , Cambridge: Cambridge University Press, ISBN 0-521-38836-8, MR  1066691.
• Cameron, Peter J. (1997), "El gráfico aleatorio", Las matemáticas de Paul Erdős, II , Algorithms Combin., 14 , Berlín: Springer, págs. 333–351, arXiv : 1301.7544 , Bibcode : 2013arXiv1301.7544C , MR  1425227.
• Cameron, Peter J. (2001), "El gráfico aleatorio revisitado" (PDF) , Congreso Europeo de Matemáticas , vol. I (Barcelona, ​​2000) , Progr. Math., 201 , Basilea: Birkhäuser, págs. 267–274, doi : 10.1007 / 978-3-0348-8268-2_15 , MR  1905324.
• Diestel, Reinhard; Líder, Imre; Scott, Alex; Thomassé, Stéphan (2007), "Partitions and orientations of the Rado graph", Transactions of the American Mathematical Society , 359 (5): 2395–2405, doi : 10.1090 / S0002-9947-06-04086-4 , MR  2276626.
• Enderton, Herbert B. (1972), Una introducción matemática a la lógica , Academic Press, Nueva York-Londres, MR  0337470.
• Erdős, P .; Rényi, A. (1963), "Gráficos asimétricos", Acta Mathematica Academiae Scientiarum Hungaricae , 14 : 295–315, doi : 10.1007 / BF01895716 , MR  0156334.
• Fagin, Ronald (1976), "Probabilidades en modelos finitos" (PDF) , The Journal of Symbolic Logic , 41 (1): 50–58, doi : 10.1017 / s0022481200051756 , MR  0476480.
• Gaifman, Haim (1964), "Sobre las medidas en los cálculos de primer orden", Israel Journal of Mathematics , 2 : 1–18, doi : 10.1007 / BF02759729 , MR  0175755.
• Grandjean, Étienne (1983), "Complejidad de la teoría de primer orden de casi todas las estructuras finitas", Información y control , 57 (2-3): 180-204, doi : 10.1016 / S0019-9958 (83) 80043-6 , MR  0742707.
• Henson, C. Ward (1971), "Una familia de gráficos homogéneos contables", Pacific Journal of Mathematics , 38 : 69–83, doi : 10.2140 / pjm.1971.38.69 , MR  0304242.
• Hodges, Wilfrid (1997), A Shorter Model Theory , Cambridge University Press, ISBN 0-521-58713-1, OCLC  468298248
• Horsley, Daniel; Pike, David A .; Sanaei, Asiyeh (2011), "Cierre existencial de gráficos de intersección de bloques de diseños infinitos que tienen un tamaño de bloque infinito", Journal of Combinatorial Designs , 19 (4): 317–327, doi : 10.1002 / jcd.20283 , MR  2838911.
• Lachlan, AH; Woodrow, Robert E. (1980), "Gráficos no dirigidos ultrahomogéneos contables", Transactions of the American Mathematical Society , 262 (1): 51–94, doi : 10.2307 / 1999974 , MR  0583847.
• Lascar, D. (2002), "Grupos de automorfismos de estructuras saturadas; una revisión", Actas del Congreso Internacional de Matemáticos, vol. II (Beijing, 2002) (PDF) , Ed. Superior. Press, Beijing, págs. 25–33, arXiv : math / 0304205 , Bibcode : 2003math ...... 4205L , MR  1957017.
• Łoś, J. (1954), "Sobre la categoricidad en el poder de los sistemas deductivos elementales y algunos problemas relacionados", Coloquio de matemáticas. , 3 : 58–62, MR  0061561.
• Marker, David (2002), Teoría de modelos , Textos de posgrado en matemáticas, 217 , Springer-Verlag, Nueva York, ISBN 0-387-98760-6, Señor  1924282.
• Moss, Lawrence S. (1989), "Existencia y no existencia de gráficos universales", Polska Akademia Nauk. Fundamenta Mathematicae , 133 (1): 25–37, MR  1059159.
• Moss, Lawrence S. (1991), "Los gráficos universales de diámetro finito fijo", Teoría de grafos, combinatoria y aplicaciones. Vol. 2 (Kalamazoo, MI, 1988) , Wiley-Intersci. Publ., Nueva York: Wiley, págs. 923–937, MR  1170834.
• Pouzet, Maurice; Sauer, Norbert (1996), "Edge particitions of the Rado graph", Combinatorica , 16 (4): 505–520, doi : 10.1007 / BF01271269 , MR  1433638.
• Rado, Richard (1964), "Gráficos universales y funciones universales" (PDF) , Acta Arith. , 9 : 331–340.
• Shelah, Saharon (1984), "Sobre gráficos universales sin instancias de CH", Annals of Pure and Applied Logic , 26 (1): 75–87, doi : 10.1016 / 0168-0072 (84) 90042-3 , MR  0739914.
• Shelah, Saharon (1990), "Gráficos universales sin instancias de CH: revisitado", Israel Journal of Mathematics , 70 (1): 69–81, doi : 10.1007 / BF02807219 , MR  1057268.
• Spencer, Joel (2001), La extraña lógica de gráficos aleatorios , algoritmos y combinatorios, 22 , Springer-Verlag, Berlín, doi : 10.1007 / 978-3-662-04538-1 , ISBN 3-540-41654-4, Señor  1847951.
• Truss, JK (1985), "The group of the countable universal graph", Mathematical Proceedings of the Cambridge Philosophical Society , 98 (2): 213–245, Bibcode : 1985MPCPS..98..213T , doi : 10.1017 / S0305004100063428 , Señor  0795890.
• Vaught, Robert L. (1954), "Aplicaciones del teorema de Löwenheim-Skolem-Tarski a problemas de integridad y decidibilidad", Indagationes Mathematicae , 16 : 467–472, MR  0063993.