Gráfico pseudoaleatorio

En teoría de grafos , se dice que un grafo es pseudoaleatorio si cumple con ciertas propiedades que los grafos aleatorios cumplen con alta probabilidad . No existe una definición concreta de pseudoaleatoriedad de grafos , pero hay muchas caracterizaciones razonables de pseudoaleatoriedad que se pueden considerar.

Las propiedades pseudoaleatorias fueron consideradas formalmente por primera vez por Andrew Thomason en 1987. ^{[1] [2]} Definió una condición llamada "desorden": se dice que un gráfico está desordenado de verdad y con si${\displaystyle G=(V,E)}$${\displaystyle (p,\alpha )}$${\estilo de visualización p}$${\estilo de visualización \alpha}$${\displaystyle 0<p<1\leq \alpha}$

${\displaystyle \left|e(U)-p{\binom {|U|}{2}}\right|\leq \alpha |U|}$

para cada subconjunto del conjunto de vértices , donde es el número de aristas entre (equivalentemente, el número de aristas en el subgrafo inducido por el conjunto de vértices ). Se puede demostrar que el grafo aleatorio de Erdős–Rényi es casi seguramente -desordenado. ^{[2] : 6} Sin embargo, los grafos con aristas distribuidas de manera menos uniforme, por ejemplo un grafo sobre vértices que consiste en un grafo completo de -vértices y vértices completamente independientes, no son -desordenados para ningún , lo que hace que el desorden sea un cuantificador razonable para las propiedades "similares a las aleatorias" de la distribución de aristas de un grafo.${\estilo de visualización U}$${\estilo de visualización V}$${\displaystyle e(U)}$${\estilo de visualización U}$${\estilo de visualización U}$${\displaystyle G(n,p)}$ ${\displaystyle (p,O({\sqrt {np}}))}$${\estilo de visualización 2n}$${\estilo de visualización n}$${\estilo de visualización n}$${\displaystyle (p,\alpha )}$${\estilo de visualización \alpha}$

Thomason demostró que la condición de "desordenado" está implícita en una condición más sencilla de comprobar, que depende únicamente del grado de código de dos vértices y no de cada subconjunto del conjunto de vértices del grafo. Si se deja que sea el número de vecinos comunes de dos vértices y , Thomason demostró que, dado un grafo de vértices con un grado mínimo , si para cada y , entonces es -desordenado. ^{[2] : 7} Este resultado muestra cómo comprobar la condición de desordenado algorítmicamente en tiempo polinomial en el número de vértices, y se puede utilizar para mostrar la pseudoaleatoriedad de grafos específicos. ^{[2] : 7}${\displaystyle \operatorname {código} (u,v)}$${\estilo de visualización u}$${\estilo de visualización v}$${\estilo de visualización G}$${\estilo de visualización n}$${\estilo de visualización np}$${\displaystyle \operatorname {codeg} (u,v)\leq np^{2}+\ell }$${\displaystyle u}$${\displaystyle v}$${\displaystyle G}$${\displaystyle \left(p,{\sqrt {(p+\ell )n}}\,\right)}$

En el espíritu de las condiciones consideradas por Thomason y su naturaleza alternativamente global y local, Chung, Graham y Wilson consideraron varias condiciones más débiles en 1989: ^[3] un gráfico en vértices con densidad de aristas y algunos pueden satisfacer cada una de estas condiciones si${\displaystyle G}$${\displaystyle n}$${\displaystyle p}$${\displaystyle \varepsilon >0}$

• Discrepancia : para cualquier subconjunto del conjunto de vértices , el número de aristas entre y está dentro de .${\displaystyle X,Y}$${\displaystyle V=V(G)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \varepsilon n^{2}}$${\displaystyle p|X||Y|}$
• Discrepancia en conjuntos individuales : para cualquier subconjunto de , el número de aristas entre está dentro de .${\displaystyle X}$${\displaystyle V}$${\displaystyle X}$${\displaystyle \varepsilon n^{2}}$${\displaystyle p{\binom {|X|}{2}}}$
• Recuento de subgrafos : para cada gráfico , el número de copias etiquetadas de entre los subgrafos de está dentro de .${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$${\displaystyle \varepsilon n^{v(H)}}$${\displaystyle p^{e(H)}n^{v(H)}}$
• Conteo de 4 ciclos : el número de ciclos etiquetados entre los subgrafos de está dentro de .${\displaystyle 4}$${\displaystyle G}$${\displaystyle \varepsilon n^{4}}$${\displaystyle p^{4}n^{4}}$
• Código de grado : siendo el número de vecinos comunes de dos vértices y ,${\displaystyle \operatorname {codeg} (u,v)}$${\displaystyle u}$${\displaystyle v}$

${\displaystyle \sum _{u,v\in V}{\big |}\operatorname {codeg} (u,v)-p^{2}n{\big |}\leq \varepsilon n^{3}.}$

• Delimitación de valores propios : Si son los valores propios de la matriz de adyacencia de , entonces está dentro de y .${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$${\displaystyle G}$${\displaystyle \lambda _{1}}$${\displaystyle \varepsilon n}$${\displaystyle pn}$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon n}$

Todas estas condiciones se pueden expresar en términos de una secuencia de grafos donde está en vértices con aristas. Por ejemplo, la condición de conteo de 4 ciclos se convierte en que la cantidad de copias de cualquier grafo en es como , y la condición de discrepancia se convierte en que , utilizando la notación minúscula .${\displaystyle \{G_{n}\}}$${\displaystyle G_{n}}$${\displaystyle n}$${\displaystyle (p+o(1)){\binom {n}{2}}}$${\displaystyle H}$${\displaystyle G_{n}}$${\displaystyle \left(p^{e(H)}+o(1)\right)e^{v(H)}}$${\displaystyle n\to \infty }$${\displaystyle \left|e(X,Y)-p|X||Y|\right|=o(n^{2})}$

Un resultado fundamental sobre la pseudoaleatoriedad de los grafos es el teorema de Chung-Graham-Wilson, que establece que muchas de las condiciones anteriores son equivalentes, hasta cambios polinomiales en ^[3] . Una secuencia de grafos que satisface esas condiciones se denomina cuasialeatoria . Se considera particularmente sorprendente ^{[2] : 9} que la condición débil de tener la densidad de 4 ciclos "correcta" implique las otras condiciones de pseudoaleatoriedad aparentemente mucho más fuertes. Los grafos como el de 4 ciclos, cuya densidad en una secuencia de grafos es suficiente para probar la cuasialeatoriedad de la secuencia, se conocen como grafos forzados .${\displaystyle \varepsilon }$

Algunas implicaciones del teorema de Chung–Graham–Wilson son claras a partir de las definiciones de las condiciones: la condición de discrepancia en conjuntos individuales es simplemente el caso especial de la condición de discrepancia para , y el conteo de 4 ciclos es un caso especial de conteo de subgrafos. Además, el lema de conteo de grafos, una generalización directa del lema de conteo de triángulos , implica que la condición de discrepancia implica conteo de subgrafos.${\displaystyle Y=X}$

El hecho de que el conteo de 4 ciclos implique la condición de grado de código se puede demostrar mediante una técnica similar al método del segundo momento. En primer lugar, la suma de grados de código se puede acotar por arriba:

${\displaystyle \sum _{u,v\in G}\operatorname {codeg} (u,v)=\sum _{x\in G}\deg(x)^{2}\geq n\left({\frac {2e(G)}{n}}\right)^{2}=\left(p^{2}+o(1)\right)n^{3}.}$

Dados 4 ciclos, la suma de los cuadrados de los grados de código está acotada:

${\displaystyle \sum _{u,v}\operatorname {codeg} (u,v)^{2}={\text{Number of labeled copies of }}C_{4}+o(n^{4})\leq \left(p^{4}+o(1)\right)n^{4}.}$

Por lo tanto, la desigualdad de Cauchy-Schwarz da

${\displaystyle \sum _{u,v\in G}|\operatorname {codeg} (u,v)-p^{2}n|\leq n\left(\sum _{u,v\in G}\left(\operatorname {codeg} (u,v)-p^{2}n\right)^{2}\right)^{1/2},}$

que se puede expandir utilizando nuestros límites en el primer y segundo momento de para dar el límite deseado. Se puede hacer una prueba de que la condición de grado de código implica la condición de discrepancia mediante un cálculo similar, aunque más complicado, que involucra la desigualdad de Cauchy-Schwarz.${\displaystyle \operatorname {codeg} }$

La condición de valor propio y la condición de 4 ciclos se pueden relacionar observando que el número de 4 ciclos etiquetados en es, hasta que se deriva de 4 ciclos degenerados, , donde es la matriz de adyacencia de . Se puede demostrar entonces que las dos condiciones son equivalentes invocando el teorema de Courant-Fischer . ^[3]${\displaystyle G}$${\displaystyle o(1)}$${\displaystyle \operatorname {tr} \left(A_{G}^{4}\right)}$${\displaystyle A_{G}}$${\displaystyle G}$

El concepto de grafos que actúan como grafos aleatorios se conecta fuertemente con el concepto de regularidad de grafos utilizado en el lema de regularidad de Szemerédi . Para , un par de conjuntos de vértices se llama -regular , si para todos los subconjuntos que satisfacen , se cumple que${\displaystyle \varepsilon >0}$${\displaystyle X,Y}$${\displaystyle \varepsilon }$${\displaystyle A\subset X,B\subset Y}$${\displaystyle |A|\geq \varepsilon |X|,|B|\geq \varepsilon |Y|}$

${\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon ,}$

donde denota la densidad de aristas entre y : el número de aristas entre y dividido por . Esta condición implica un análogo bipartito de la condición de discrepancia, y esencialmente establece que las aristas entre y se comportan de una manera "similar al azar". Además, Miklós Simonovits y Vera T. Sós demostraron en 1991 que un grafo satisface las condiciones de pseudoaleatoriedad débil anteriores utilizadas en el teorema de Chung-Graham-Wilson si y solo si posee una partición de Szemerédi donde casi todas las densidades están cerca de la densidad de aristas de todo el grafo. ^[4]${\displaystyle d(X,Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle |X||Y|}$${\displaystyle A}$${\displaystyle B}$

El teorema de Chung-Graham-Wilson, específicamente la implicación del conteo de subgrafos a partir de la discrepancia, no se sigue para secuencias de grafos con densidad de aristas que se aproxima a , o, por ejemplo, el caso común de - grafos regulares en vértices como . Los siguientes análogos dispersos de las condiciones de discrepancia y límite de valor propio se consideran comúnmente:${\displaystyle 0}$${\displaystyle d}$${\displaystyle n}$${\displaystyle n\to \infty }$

• Discrepancia dispersa : para cualquier subconjunto del conjunto de vértices , el número de aristas entre y está dentro de .${\displaystyle X,Y}$${\displaystyle V=V(G)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \varepsilon dn}$${\displaystyle {\frac {d}{n}}|X||Y|}$
• Delimitación de valores propios dispersos : Si son los valores propios de la matriz de adyacencia de , entonces .${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$${\displaystyle G}$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon d}$

En general, es cierto que esta condición de valor propio implica la condición de discrepancia correspondiente, pero lo inverso no es cierto: la unión disjunta de un grafo -regular grande aleatorio y un grafo completo -vértice tiene dos valores propios de exactamente pero es probable que satisfaga la propiedad de discrepancia. Sin embargo, como lo demostraron David Conlon y Yufei Zhao en 2017, ligeras variantes de las condiciones de discrepancia y valor propio para grafos de Cayley -regulares son equivalentes hasta el escalamiento lineal en . ^[5] Una dirección de esto se desprende del lema de mezcla de expansores , mientras que la otra requiere la suposición de que el grafo es un grafo de Cayley y utiliza la desigualdad de Grothendieck .${\displaystyle d}$${\displaystyle d+1}$${\displaystyle d}$${\displaystyle d}$${\displaystyle \varepsilon }$

Un grafo -regular sobre vértices se llama -grafo si, dejando los valores propios de la matriz de adyacencia de ser , . El límite de Alon-Boppana da que (donde el término es como ), y Joel Friedman demostró que un grafo -regular aleatorio sobre vértices es para . ^[6] En este sentido, cuánto excede es una medida general de la no aleatoriedad de un grafo. Hay grafos con , que se denominan grafos de Ramanujan . Se han estudiado ampliamente y hay una serie de problemas abiertos relacionados con su existencia y su popularidad.${\displaystyle d}$${\displaystyle G}$${\displaystyle n}$${\displaystyle (n,d,\lambda )}$${\displaystyle G}$${\displaystyle d=\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \lambda }$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\geq 2{\sqrt {d-1}}-o(1)}$${\displaystyle o(1)}$${\displaystyle n\to \infty }$${\displaystyle d}$${\displaystyle n}$${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda =2{\sqrt {d-1}}+o(1)}$${\displaystyle \lambda }$${\displaystyle 2{\sqrt {d-1}}}$${\displaystyle \lambda \leq 2{\sqrt {d-1}}}$

Dado un gráfico para , muchas cantidades estándar de teoría de grafos pueden limitarse a cerca de lo que se esperaría de un gráfico aleatorio. En particular, el tamaño de tiene un efecto directo en las discrepancias de densidad de aristas de subconjuntos a través del lema de mezcla de expansores. Otros ejemplos son los siguientes, siendo :${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda }$${\displaystyle \lambda }$${\displaystyle G}$${\displaystyle (n,d,\lambda )}$

• Si , la conectividad de vértices de satisface ^[7]${\displaystyle d\leq {\frac {n}{2}}}$ ${\displaystyle \kappa (G)}$${\displaystyle G}$${\displaystyle \kappa (G)\geq d-{\frac {36\lambda ^{2}}{d}}.}$
• Si , está conexo por aristas . Si es par, contiene una correspondencia perfecta. ^{[2] : 32}${\displaystyle \lambda \leq d-2}$${\displaystyle G}$${\displaystyle d}$ ${\displaystyle n}$${\displaystyle G}$
• El corte máximo de es como máximo . ^{[2] : 33}${\displaystyle G}$${\displaystyle {\frac {n(d+\lambda )}{4}}}$
• El subconjunto independiente más grande de un subconjunto en tiene un tamaño de al menos ^[8]${\displaystyle U\subset V(G)}$${\displaystyle G}$${\displaystyle {\frac {n}{2(d-\lambda )}}\ln \left({\frac {|U|(d-\lambda )}{n(\lambda +1)}}+1\right).}$
• El número cromático de es como máximo ^[8]${\displaystyle G}$${\displaystyle {\frac {6(d-\lambda )}{\ln \left({\frac {d+1}{\lambda +1}}\right)}}.}$

Los grafos pseudoaleatorios son un factor destacado en la prueba del teorema de Green-Tao . El teorema se demuestra transfiriendo el teorema de Szemerédi , la afirmación de que un conjunto de números enteros positivos con densidad natural positiva contiene progresiones aritméticas arbitrariamente largas, al entorno disperso (ya que los primos tienen densidad natural en los números enteros). La transferencia a conjuntos dispersos requiere que los conjuntos se comporten de forma pseudoaleatoria, en el sentido de que los grafos e hipergrafos correspondientes tengan las densidades de subgrafos correctas para algún conjunto fijo de (hiper)subgrafos pequeños. ^[9] Luego se muestra que un superconjunto adecuado de los números primos, llamado pseudoprimos, en el que los primos son densos obedece estas condiciones de pseudoaleatoriedad, completando la prueba.${\displaystyle 0}$