Gráfico de Rado
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, mediante la simetrización de 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 subgrafo 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 .
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ó un gráfico dirigido , y el gráfico de Rado es el gráfico no dirigido correspondiente dado al olvidar las direcciones en los bordes). Erdős y Rényi (1963) construyeron el gráfico de Rado como el gráfico aleatorio 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 gráfico de Rado como un gráfico universal, y dio una construcción explícita de la misma con vértice establecer los números naturales. La construcción de Rado es esencialmente equivalente a una de las construcciones de Ackermann.
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, ... Un borde conecta los vértices y en el gráfico (donde ) siempre que el th bit de la representación binaria dees 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. [1]
El gráfico de Rado surge casi con seguridad en el modelo Erdős-Rényi de un gráfico aleatorio en innumerables vértices numerables. 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. [2]
