La extraña lógica de los grafos aleatorios

La lógica extraña de los grafos aleatorios es un libro sobre leyes binarias para grafos aleatorios . Fue escrito por Joel Spencer y publicado en 2001 por Springer-Verlag como el volumen 22 de su serie de libros Algoritmos y combinatoria .

Las gráficas aleatorias del libro se generan a partir del modelo Erdős-Rényi-Gilbert.${\displaystyle G(n,p)}$en el cual${\displaystyle n}$Se dan los vértices y se elige aleatoriamente si conectar cada par de vértices mediante una arista, de forma independiente para cada par, con probabilidad${\displaystyle p}$de establecer una conexión. Una ley cero-uno es un teorema que establece que, para ciertas propiedades de los gráficos y para ciertas elecciones de${\displaystyle p}$, la probabilidad de generar un gráfico con la propiedad tiende a cero o a uno en el límite cuando${\displaystyle n}$va hasta el infinito. ^{[ 1 ]}

Un resultado fundamental en esta área, demostrado independientemente por Glebskiĭ et al. y por Ronald Fagin , es que existe una ley cero-uno para${\displaystyle G(n,1/2)}$para cada propiedad que se puede describir en la lógica de primer orden de los grafos . ^{[ 2 ]} Además, la probabilidad límite es uno si y solo si el grafo de Rado infinito tiene la propiedad. Por ejemplo, un grafo aleatorio en este modelo contiene un triángulo con probabilidad que tiende a uno; contiene un vértice universal con probabilidad que tiende a cero. Para otras elecciones de${\displaystyle p}$, pueden ocurrir otros resultados. Por ejemplo, la probabilidad límite de contener un triángulo está entre 0 y 1 cuando${\displaystyle p=c/n}$por una constante${\displaystyle c}$; tiende a 0 para selecciones más pequeñas de${\displaystyle p}$y a 1 para opciones más grandes. La función${\displaystyle 1/n}$Se dice que es un umbral para la propiedad de contener un triángulo, lo que significa que separa los valores de${\displaystyle p}$con probabilidad límite 0 de los valores con probabilidad límite 1. ^{[ 1 ]}

El principal resultado del libro (demostrado por Spencer con Saharon Shelah ) es que los poderes irracionales de${\displaystyle n}$nunca son funciones umbral. Es decir, siempre que${\displaystyle a>0}$es un número irracional , existe una ley cero-uno para las propiedades de primer orden de los grafos aleatorios${\displaystyle G(n,n^{-a})}$. ^{[ 1 ]} Una herramienta clave en la demostración es el juego Ehrenfeucht–Fraïssé . ^{[ 3 ]}

Aunque se trata esencialmente de la demostración de un único teorema, dirigido a especialistas en la materia, el libro está escrito en un estilo accesible que introduce al lector a muchos temas importantes de la teoría de modelos finitos y la teoría de grafos aleatorios. El crítico Valentin Kolchin, autor de otro libro sobre grafos aleatorios, escribe que el libro es «autónomo, de fácil lectura y se distingue por una escritura elegante», recomendándolo a teóricos de la probabilidad y lógicos . ^{[ 2 ]} El crítico Alessandro Berarducci califica el libro de «bellamente escrito» y su tema de «fascinante». ^{[ 1 ]}