Gráfico de Rado

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

El grafo de Rado surge casi con seguridad en el modelo de Erdős-Rényi de un grafo aleatorio con un número numerable de vértices. Específicamente, se puede formar un grafo infinito eligiendo, de forma independiente y con probabilidad 1/2 para cada par de vértices, si conectar o no los dos vértices mediante una arista. Con probabilidad 1, el grafo resultante es isomorfo al grafo de Rado. Esta construcción también funciona si cualquier probabilidad fija${\displaystyle p}$No es igual a 0 o 1 se usa en lugar de 1/2. ^{[ 2 ]}

Este resultado, demostrado por Paul Erdős y Alfréd Rényi ( 1963 ) , justifica el artículo definido en el nombre alternativo común " grafo aleatorio" para el grafo de Rado. Dibujar repetidamente un grafo finito a partir del modelo de Erdős-Rényi generalmente dará lugar a grafos diferentes; sin embargo, cuando se aplica a un grafo infinito numerable, el modelo casi siempre produce el mismo grafo infinito. ^{[ 3 ]} 

Para cualquier grafo generado aleatoriamente de esta manera, el grafo complemento se puede obtener simultáneamente invirtiendo todas las elecciones: incluyendo una arista cuando el primer grafo no la incluía, y viceversa. Esta construcción del grafo complemento es una instancia del mismo proceso de elegir aleatoria e independientemente si se incluye o no cada arista, por lo que también genera (con probabilidad 1) el grafo de Rado. Por lo tanto, el grafo de Rado es un grafo autocomplementario . ^{[ 4 ]}

En una de las construcciones originales de Ackermann de 1937, los vértices del grafo de Rado se indexan mediante conjuntos hereditariamente finitos , que se definen recursivamente como conjuntos finitos cuyos elementos son conjuntos hereditariamente finitos, permitiendo solo un número finito de niveles de recursión. Existe una arista entre dos vértices precisamente cuando uno de los conjuntos finitos correspondientes pertenece al otro. Esta construcción es equivalente a la construcción de predicados BIT, bajo la codificación de Ackermann de conjuntos hereditariamente finitos como números binarios. Una construcción similar puede basarse en la paradoja de Skolem , el hecho de que existe un modelo numerable para la teoría de conjuntos de primer orden. Se puede construir el grafo de Rado a partir de dicho modelo creando un vértice para cada conjunto, con una arista que conecta cada par de conjuntos donde un conjunto del par pertenece al otro. ^{[ 5 ]}

El grafo de Rado también puede formarse mediante una construcción similar a la de los grafos de Paley , tomando como vértices de un grafo todos los números primos congruentes con 1 módulo 4, y conectando dos vértices mediante una arista siempre que uno de los dos números sea un residuo cuadrático (es decir, congruente con un cuadrado) módulo el otro. Debido a la reciprocidad cuadrática y a la restricción de los vértices a primos congruentes con 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. ^{[ 6 ]}

Otra construcción del grafo de Rado muestra que es un grafo circulante infinito , con los enteros como vértices y con una arista entre cada par de enteros cuya distancia (el valor absoluto de su diferencia) pertenece a un conjunto particular.${\displaystyle S}$Para construir el gráfico de Rado de esta manera,${\displaystyle S}$puede elegirse aleatoriamente o eligiendo la función indicadora de${\displaystyle S}$ser la concatenación de todas las secuencias binarias finitas . ^{[ 7 ]}

El grafo de Rado también puede construirse como el grafo de intersección de bloques de un diseño de bloques infinito en el que el número de puntos y el tamaño de cada bloque son infinitos numerables . ^{[ 8 ]} También puede construirse como el límite de Fraïssé de la clase de grafos finitos. ^{[ 9 ]}

El grafo de Rado satisface la siguiente propiedad de extensión: para cada dos conjuntos finitos disjuntos de vértices${\displaystyle U}$y${\displaystyle V}$, existe un vértice${\displaystyle x}$fuera de ambos conjuntos que está conectado a todos los vértices en${\displaystyle U}$, pero no tiene vecinos en${\displaystyle V}$. ^{[ 2 ]} Por ejemplo, con la definición de números binarios del grafo de Rado, sea $${\displaystyle x=2^{1+\max(U\cup V)}+\sum _{u\in U}2^{u}.}$$ Entonces los bits distintos de cero en la representación binaria de${\displaystyle x}$hacer que esté adyacente a todo en${\displaystyle U}$. Sin embargo,${\displaystyle x}$no tiene bits distintos de cero en su representación binaria correspondientes a los vértices en${\displaystyle V}$, y${\displaystyle x}$es tan grande que el${\displaystyle x}$el bit de cada elemento de${\displaystyle V}$es cero. Por lo tanto,${\displaystyle x}$no es adyacente a ningún vértice en${\displaystyle V}$. ^{[ 10 ]}

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

La propiedad de extensión se puede utilizar para construir copias isomorfas de cualquier grafo finito o infinito numerable.${\displaystyle G}$dentro del grafo de Rado, como subgrafos inducidos . Para ello, ordene los vértices de${\displaystyle G}$y agregar vértices en el mismo orden a una copia parcial de${\displaystyle G}$dentro del grafo de Rado. En cada paso, el siguiente vértice en${\displaystyle G}$estará adyacente a algún conjunto${\displaystyle U}$de vértices en${\displaystyle G}$que se encuentran antes en el ordenamiento de los vértices y no son adyacentes al conjunto restante${\displaystyle V}$de vértices anteriores en${\displaystyle G}$. Por la propiedad de extensión, el grafo de Rado también tendrá un vértice${\displaystyle x}$que es adyacente a todos los vértices en la copia parcial que corresponden a miembros de${\displaystyle U}$y no adyacente a todos los vértices en la copia parcial que corresponden a miembros de${\displaystyle V}$. Añadiendo${\displaystyle x}$a la copia parcial de${\displaystyle G}$produce una copia parcial más grande, con un vértice más. ^{[ 11 ]}

Este método constituye la base para una demostración por inducción , con el subgrafo de 0 vértices como caso base, de que todo grafo finito o infinitamente numerable es un subgrafo inducido del grafo de Rado. ^{[ 11 ]}

El grafo de Rado es, salvo isomorfismo de grafos , el único grafo numerable con la propiedad de extensión. Por ejemplo, sea${\displaystyle G}$y${\displaystyle H}$Sean dos grafos numerables con la propiedad de extensión, sea${\displaystyle G_{i}}$y${\displaystyle H_{i}}$ser subgrafos inducidos finitos isomorfos de${\displaystyle G}$y${\displaystyle H}$respectivamente, y dejemos${\displaystyle g_{i}}$y${\displaystyle h_{i}}$sean los primeros vértices en una enumeración de los vértices de${\displaystyle G}$y${\displaystyle H}$respectivamente que no pertenecen a${\displaystyle G_{i}}$y${\displaystyle H_{i}}$Luego, aplicando la propiedad de extensión dos veces, se pueden encontrar subgrafos inducidos isomorfos.${\displaystyle G_{i+1}}$y${\displaystyle H_{i+1}}$que incluyen${\displaystyle g_{i}}$y${\displaystyle h_{i}}$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 incluya cada vértice en${\displaystyle G}$y${\displaystyle H}$. Así, mediante el método de ida y vuelta ,${\displaystyle G}$y${\displaystyle H}$debe ser isomorfo. ^{[ 12 ]} Debido a que los grafos construidos por la construcción de grafos aleatorios, la construcción de números binarios y la construcción de grafos de Paley son todos grafos contables con la propiedad de extensión, este argumento muestra que todos son isomorfos entre sí. ^{[ 13 ]}

La aplicación de la construcción de ida y vuelta a dos subgrafos finitos isomorfos cualesquiera del grafo de Rado extiende su isomorfismo a un automorfismo de todo el grafo de Rado. El hecho de que todo 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, existe un automorfismo que transforma cualquier par ordenado de vértices adyacentes en cualquier otro par ordenado similar, por lo que el grafo de Rado es un grafo simétrico . ^{[ 12 ]}

El grupo de automorfismos del grafo de Rado es un grupo simple , cuyo número de elementos es la cardinalidad del continuo . Todo subgrupo de este grupo cuyo índice es menor que la cardinalidad del continuo contiene el estabilizador puntual de un conjunto finito de vértices, y además está contenido dentro del estabilizador de conjunto del mismo conjunto. ^{[ 14 ]} La afirmación sobre los estabilizadores puntuales se denomina propiedad del índice pequeño, ^{[ 14 ]} y su demostración requirió mostrar que para todo grafo finito${\displaystyle X}$, hay un grafo finito${\displaystyle Z}$que contiene${\displaystyle X}$como un subgrafo inducido tal que todo isomorfismo entre subgrafos inducidos de${\displaystyle X}$se extiende a un automorfismo de${\displaystyle Z}$. ^{[ 15 ]} Esto se denomina propiedad de extensión para automorfismos parciales y desde entonces se ha generalizado a otras estructuras para demostrar la propiedad de índice pequeño y otras propiedades. ^{[ 16 ]}

La construcción del grafo de Rado como un grafo 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 enteros entre vértices adyacentes) puede restringirse para incluir la diferencia 1, sin afectar la corrección de esta construcción, de lo cual se deduce que el grafo de Rado contiene un camino hamiltoniano infinito cuyas simetrías son un subgrupo de las simetrías de todo el grafo. ^{[ 17 ]}

Si un gráfico${\displaystyle G}$se forma a partir del grafo 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 grafo. Para cualquier par de conjuntos${\displaystyle U}$y${\displaystyle V}$Todavía es posible encontrar un vértice en el grafo modificado que sea adyacente a todo en${\displaystyle U}$y no adyacente a todo en${\displaystyle V}$, agregando las partes modificadas de${\displaystyle G}$a${\displaystyle V}$y aplicando la propiedad de extensión en el grafo de Rado no modificado. Por lo tanto, cualquier modificación finita de este tipo da como resultado un grafo que es isomorfo al grafo de Rado. ^{[ 18 ]}

Para cualquier partición de los vértices del grafo de Rado en dos conjuntos${\displaystyle A}$y${\displaystyle B}$, 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 partición es isomorfo al grafo de Rado completo. Cameron (2001) da la siguiente breve demostración: si ninguna de las partes induce un subgrafo isomorfo al grafo de Rado, todas fallan en tener la propiedad de extensión, y se pueden encontrar pares de conjuntos${\displaystyle U_{i}}$y${\displaystyle V_{i}}$que no se puede extender dentro de cada subgrafo. Pero entonces, la unión de los conjuntos${\displaystyle U_{i}}$y la unión de los conjuntos${\displaystyle V_{i}}$formaría un conjunto que no podría extenderse en todo el grafo, contradiciendo la propiedad de extensión del grafo de Rado. Esta propiedad de ser isomorfo a uno de los subgrafos inducidos de cualquier partición la poseen solo tres grafos no dirigidos infinitos numerables: el grafo de Rado, el grafo completo y el grafo vacío . ^{[ 19 ]} Bonato, Cameron y Delić (2000) y Diestel et al. (2007) investigan grafos dirigidos infinitos con la misma propiedad de partición; todos se forman eligiendo orientaciones para las aristas del grafo completo o del grafo de Rado.

Un resultado relacionado se refiere a particiones de aristas en lugar de particiones de vértices: para cada partición de las aristas del grafo de Rado en un número finito de conjuntos, existe un subgrafo isomorfo al grafo de Rado completo que utiliza como máximo dos de los colores. Sin embargo, no necesariamente existe un subgrafo isomorfo que utilice solo un color de aristas. ^{[ 20 ]} De manera más general, para cada grafo finito${\displaystyle A}$hay un número${\displaystyle d_{A}}$(llamado el gran grado de Ramsey de${\displaystyle A}$en el grafo de Rado) de tal manera que para cada partición de las copias de${\displaystyle A}$En el grafo de Rado dividido en un número finito de conjuntos, existe un subgrafo inducido isomorfo al grafo de Rado completo que utiliza como máximo${\displaystyle d_{A}}$de los colores. ^{[ 21 ] [ 22 ]}

El lenguaje de primer orden de los grafos es el conjunto de oraciones bien formadas en lógica matemática, compuestas por variables que representan los vértices de los grafos, cuantificadores universales y existenciales , conectores lógicos y predicados de igualdad y adyacencia de vértices. Por ejemplo, la condición de que un grafo no tenga vértices aislados puede expresarse mediante la oración $${\displaystyle \forall u:\exists v:u\sim v}$$ donde el${\displaystyle \sim }$El símbolo indica la relación de adyacencia entre dos vértices. ^{[ 23 ]} Esta oración${\displaystyle S}$es cierto para algunos gráficos y falso para otros; un gráfico${\displaystyle G}$Se dice que modela${\displaystyle S}$, escrito${\displaystyle G\models S}$, si${\displaystyle S}$es cierto para los vértices y la relación de adyacencia de${\displaystyle G}$. ^{[ 24 ]}

La propiedad de extensión del grafo de Rado puede expresarse mediante una colección de oraciones de primer orden.${\displaystyle E_{i,j}}$, afirmando que para cada elección de${\displaystyle i}$vértices en un conjunto${\displaystyle A}$y${\displaystyle j}$vértices en un conjunto${\displaystyle B}$, todos distintos, existe un vértice adyacente a todo en${\displaystyle A}$y no adyacente a todo en${\displaystyle B}$. ^{[ 25 ]} Por ejemplo,${\displaystyle E_{1,1}}$se puede escribir como $${\displaystyle \forall a:\forall b:a\neq b\rightarrow \exists c:c\neq a\wedge c\neq b\wedge c\sim a\wedge \lnot (c\sim b).}$$

Gaifman (1964) demostró que las oraciones ${\displaystyle E_{i,j}}$, junto con oraciones adicionales que establecen que la relación de adyacencia es simétrica y antirreflexiva (es decir, que un grafo 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${\displaystyle S}$, exactamente uno de${\displaystyle S}$y su negación puede probarse a partir de estos axiomas. Dado que el grafo de Rado modela los axiomas de extensión, modela todas las oraciones en esta teoría. ^{[ 26 ]}

En lógica, una teoría que tiene un solo modelo (salvo isomorfismo) con una cardinalidad infinita dada${\displaystyle \lambda }$se llama${\displaystyle \lambda }$-categórico . El hecho de que el grafo de Rado sea el único grafo numerable con la propiedad de extensión implica que también es el único modelo numerable para su teoría. Esta propiedad de unicidad del grafo de Rado se puede expresar diciendo que la teoría del grafo de Rado es ω-categórica . Łoś y Vaught demostraron en 1954 que cuando una teoría es${\displaystyle \lambda }$–categórico (para algún cardinal infinito)${\displaystyle \lambda }$) y, además, no tiene modelos finitos, entonces la teoría debe ser completa. ^{[ 27 ]} Por lo tanto, el teorema de Gaifman de que la teoría del grafo de Rado es completa se deduce de la unicidad del grafo de Rado por la prueba de Łoś–Vaught . ^{[ 28 ]}

Como demostró Fagin (1976) , las sentencias de primer orden demostrables a partir de los axiomas de extensión y modeladas por el grafo de Rado son exactamente las sentencias verdaderas para casi todos los grafos finitos aleatorios. Esto significa que si uno elige un${\displaystyle n}$-grafo de vértices uniformemente al azar entre todos los grafos en${\displaystyle n}$vértices etiquetados, entonces la probabilidad de que tal oración sea verdadera para el grafo elegido se aproxima a uno en el límite cuando${\displaystyle n}$se aproxima al infinito. Simétricamente, las oraciones que no están modeladas por el grafo de Rado son falsas para casi todos los grafos finitos aleatorios. De ello se deduce que toda oración de primer orden es casi siempre verdadera o casi siempre falsa para grafos finitos aleatorios, y estas dos posibilidades pueden distinguirse determinando si el grafo de Rado modela la oración. La demostración de Fagin utiliza el teorema de compacidad . ^{[ 29 ]} Basándose en esta equivalencia, la teoría de oraciones modeladas por el grafo de Rado se ha denominado «teoría del grafo aleatorio» o «teoría casi segura de grafos».

Debido a esta ley 0-1, es posible comprobar si una sentencia de primer orden en particular se modela mediante el grafo de Rado en un tiempo finito, eligiendo un valor suficientemente grande de${\displaystyle n}$y contando el número de${\displaystyle n}$-grafos de vértices que modelan la oración. Sin embargo, aquí, "suficientemente grande" es al menos exponencial en el tamaño de la oración. Por ejemplo, el axioma de extensión${\displaystyle E_{k,0}}$implica la existencia de un${\displaystyle (k+1)}$-clique de vértices , pero un clique de ese tamaño existe con alta probabilidad solo en grafos aleatorios de tamaño exponencial en${\displaystyle k}$Es improbable que determinar si el grafo de Rado modela una oración dada se pueda hacer más rápido que en tiempo exponencial, ya que el problema es PSPACE-completo . ^{[ 30 ]}

El grafo de Rado es ultrahomogéneo y, por lo tanto, es el límite de Fraïssé de su clase de subestructuras finitas, es decir, la clase de grafos finitos. ^{[ 31 ]} Dado que también está en un lenguaje relacional finito, la ultrahomogeneidad es equivalente a que su teoría tenga eliminación de cuantificadores y sea ω-categórica. ^{[ 32 ]} Como el grafo de Rado es, por lo tanto, el modelo contable de una teoría ω-categórica contable, es primo y saturado . ^{[ 33 ] [ 34 ]}

La teoría del grafo de Rado es un ejemplo prototípico de una teoría con la propiedad de independencia y de una teoría simple que no es estable . ^{[ 35 ]}