Grafo pseudoaleatorio

En teoría de grafos , se dice que un grafo es pseudoaleatorio si cumple 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 la 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 "mezcla": un grafo $G=(V,E)$ Se dice que $(p,\alpha )$ - revuelto de verdad $p$ y $\alpha$ con $0<p<1\leq \alpha$ si

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

para cada subconjunto $U$ del conjunto de vértices $V$ , dónde $e(U)$ es el número de aristas entre $U$ (equivalentemente, el número de aristas en el subgrafo inducido por el conjunto de vértices) $U$ ). Se puede demostrar que el gráfico aleatorio de Erdős-Rényi $G(n,p)$ es casi seguro $(p,O({\sqrt {np}}))$ -mezclado. ^{[ 2 ]}^{: 6} Sin embargo, los grafos con aristas menos uniformemente distribuidas, por ejemplo un grafo en $2n$ vértices que consisten en un $n$ -grafo completo de vértices y $n$ vértices completamente independientes, no lo son. $(p,\alpha )$ -mezclado para cualquier pequeño $\alpha$ , lo que convierte el desorden en un cuantificador razonable para las propiedades "aleatorias" de la distribución de aristas de un grafo.

Conexión con las condiciones locales

Thomason demostró que la condición "desordenada" está implícita en una condición más sencilla de comprobar, que solo depende del codegrado de dos vértices y no de cada subconjunto del conjunto de vértices del grafo. $\operatorname {código} (u,v)$ sea el número de vecinos comunes de dos vértices $u$ y $v$ Thomason demostró que, dado un gráfico $G$ en $n$ vértices con grado mínimo $np$ , si $\operatorname {codeg} (u,v)\leq np^{2}+\ell$ por cada $u$ y $v$ , entonces $G$ es $\left(p,{\sqrt {(p+\ell )n}}\,\right)$ -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 puede utilizarse para demostrar la pseudoaleatoriedad de grafos específicos. ^{[ 2 ]}^{: 7}

Teorema de Chung-Graham-Wilson

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 $G$ en $n$ vértices con densidad de aristas $p$ y algunos $\varepsilon >0$ puede satisfacer cada una de estas condiciones si

Discrepancia : para cualquier subconjunto $X,Y$ del conjunto de vértices $V=V(G)$ , el número de aristas entre $X$ y $Y$ está dentro $\varepsilon n^{2}$ de $p|X||Y|$ .
Discrepancia en conjuntos individuales : para cualquier subconjunto $X$ de $V$ , el número de aristas entre $X$ está dentro $\varepsilon n^{2}$ de $p{\binom {|X|}{2}}$ .
Conteo de subgrafos : para cada grafo $H$ , el número de copias etiquetadas de $H$ entre los subgrafos de $G$ está dentro $\varepsilon n^{v(H)}$ de $p^{e(H)}n^{v(H)}$ .
Conteo de 4 ciclos : el número de elementos etiquetados $4$ -ciclos entre los subgrafos de $G$ está dentro $\varepsilon n^{4}$ de $p^{4}n^{4}$ .
Codegree : permitir $\operatorname {código} (u,v)$ sea el número de vecinos comunes de dos vértices $u$ y $v$ ,

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

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

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

Un resultado fundamental sobre la pseudoaleatoriedad de grafos es el teorema de Chung-Graham-Wilson, que establece que muchas de las condiciones anteriores son equivalentes, salvo cambios polinomiales en $\varepsilon$ ^{[ 3 ]} . Una secuencia de grafos que satisface esas condiciones se llamacuasialeatoria. 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 4-ciclo, cuya densidad en una secuencia de grafos es suficiente para probar la cuasialeatoriaidad de la secuencia, se conocen comografos de forzamiento.

Algunas implicaciones del teorema de Chung-Graham-Wilson quedan 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=X$ y el conteo de ciclos de 4 elementos es un caso especial del 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 el conteo de subgrafos.

El hecho de que el conteo de 4 ciclos implique la condición de codegrado puede probarse mediante una técnica similar al método del segundo momento. En primer lugar, la suma de los codegrados puede acotarse superiormente:

\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 codegrados está acotada:

\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

\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 ampliar utilizando nuestros límites en el primer y segundo momento de $\operatorname {codeg}$ para dar el límite deseado. Una demostración de que la condición de codegrado implica la condición de discrepancia puede hacerse mediante un cálculo similar, aunque más complejo, que involucra la desigualdad de Cauchy-Schwarz.

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

Conexiones con la regularidad de los grafos

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 $\varepsilon >0$ , un par de conjuntos de vértices $X,Y$ se llama $\varepsilon$ -regular , si para todos los subconjuntos $A\subset X,B\subset Y$ satisfactorio $|A|\geq \varepsilon |X|,|B|\geq \varepsilon |Y|$ , sostiene que

\left|d(X,Y)-d(A,B)\right|\leq \varepsilon ,

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

pseudoaleatoriedad dispersa

Análogos del teorema de Chung-Graham-Wilson

El teorema de Chung-Graham-Wilson, específicamente la implicación del conteo de subgrafos a partir de la discrepancia, no se cumple para secuencias de grafos con densidad de aristas que se aproximan a $0$ , o, por ejemplo, el caso común de $d$ - gráficos regulares en $n$ vértices como $n\to \infty$ . Los siguientes análogos dispersos de las condiciones de cota de discrepancia y de valores propios se consideran comúnmente:

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

En general, es cierto que esta condición de autovalor implica la condición de discrepancia correspondiente, pero lo contrario no es cierto: la unión disjunta de un valor aleatorio grande $d$ -gráfico regular y un $d+1$ El grafo completo de vértices tiene dos autovalores exactamente iguales. $d$ pero es probable que satisfaga la propiedad de discrepancia. Sin embargo, David Conlon y Yufei Zhao demostraron en 2017 que, para grafos transitivos en vértices , las condiciones de discrepancia y de autovalor anteriores son equivalentes salvo un cambio de factor constante en $\varepsilon$ . ^{[ 5 ]} Una dirección de esto se deriva del lema de mezcla de expansores , mientras que la otra requiere la suposición de que el grafo es transitivo en vértices y utiliza la desigualdad de Grothendieck .

Consecuencias de la acotación de los valores propios

A $d$ -gráfico regular $G$ en $n$ vértices se llama un $(n,d,\lambda )$ -graficar si, dejando los valores propios de la matriz de adyacencia de $G$ ser $d=\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ , $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \lambda$ . El vínculo Alon-Boppana da eso $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\geq 2{\sqrt {d-1}}-o(1)$ (donde el $o(1)$ El término es como $n\to \infty$ ), y Joel Friedman demostró que un aleatorio $d$ -gráfico regular en $n$ vértices es $(n,d,\lambda )$ para $\lambda =2{\sqrt {d-1}}+o(1)$ . ^{[ 6 ]} En este sentido, cuánto $\lambda$ supera $2{\sqrt {d-1}}$ es una medida general de la no aleatoriedad de un gráfico. Hay gráficos con $\lambda \leq 2{\sqrt {d-1}}$ , que se denominan grafos de Ramanujan . Han sido estudiados exhaustivamente y existen varios problemas abiertos relacionados con su existencia y frecuencia.

Dado un $(n,d,\lambda )$ gráfico para pequeño $\lambda$ , muchas cantidades estándar de la teoría de grafos pueden acotarse a valores cercanos a los que se esperarían de un grafo aleatorio. En particular, el tamaño de $\lambda$ tiene un efecto directo sobre las discrepancias de densidad de aristas de subconjuntos a través del lema de mezcla del expansor. Otros ejemplos son los siguientes, dejando $G$ frijol $(n,d,\lambda )$ gráfico:

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

Conexiones con el teorema de Green-Tao

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

Referencias

↑ Thomason, Andrew (1987). «Grafos pseudoaleatorios» . Annals of Discrete Math . North-Holland Mathematics Studies. 33 : 307–331 . doi : 10.1016/S0304-0208(08)73063-9 . ISBN 978-0-444-70265-4.
1 2 3 4 5 6 7 Krivelevich, Michael; Sudakov, Benny (2006). "Grafos pseudoaleatorios" (PDF) . Más conjuntos, grafos y números . Estudios matemáticos de la Sociedad Bolyai. Vol. 15. págs. 199–262 . doi : 10.1007/978-3-540-32439-3_10 . ISBN 978-3-540-32377-8. S2CID 1952661 .
1 2 3 Chung, FRK; Graham, RL ; Wilson, RM (1989). "Grafos cuasi-aleatorios" (PDF) . Combinatorica . 9 (4): 345– 362. doi : 10.1007/BF02125347 . S2CID 17166765 .
↑ Simonovits, Miklós; Sós, Vera (1991). "La partición y la cuasi aleatoriedad de Szemerédi". Estructuras aleatorias y algoritmos . 2 : 1– 10. doi : 10.1002/rsa.3240020102 .
↑ Conlon, David; Zhao, Yufei (2017). "Grafos de Cayley cuasialeatorios". Análisis discreto . 6. arXiv : 1603.03025 . doi : 10.19086/da.1294 . S2CID 56362932 .
↑ Friedman, Joel (2003). "Expansores relativos o grafos de Ramanujan débilmente relativos". Duke Math. J. 118 ( 1): 19– 35. doi : 10.1215/S0012-7094-03-11812-8 . MR 1978881 .
↑ Krivelevich, Michael; Sudakov, Benny; Vu, Van H.; Wormald, Nicholas C. (2001). "Grafos regulares aleatorios de alto grado". Random Structures and Algorithms . 18 (4): 346– 363. doi : 10.1002/rsa.1013 . S2CID 16641598 .
1 2 Alon, Noga ; Krivelevich, Michael ; Sudakov, Benny (1999). "Coloración de listas de grafos aleatorios y pseudoaleatorios". Combinatorica . 19 (4): 453– 472. doi : 10.1007/s004939970001 . S2CID 5724231 .
↑ Conlon, David ; Fox, Jacob ; Zhao, Yufei (2014). "El teorema de Green-Tao: una exposición". EMS Surveys in Mathematical Sciences . 1 (2): 249– 282. arXiv : 1403.2957 . doi : 10.4171/EMSS/6 . MR 3285854. S2CID 119301206 .

[th-1] Thomason, Andrew (1987). «Grafos pseudoaleatorios» . Annals of Discrete Math . North-Holland Mathematics Studies. 33 : 307–331 . doi : 10.1016/S0304-0208(08)73063-9 . ISBN 978-0-444-70265-4.

[ks-2] 1 2 3 4 5 6 7 Krivelevich, Michael; Sudakov, Benny (2006). "Grafos pseudoaleatorios" (PDF) . Más conjuntos, grafos y números . Estudios matemáticos de la Sociedad Bolyai. Vol. 15. págs. 199–262 . doi : 10.1007/978-3-540-32439-3_10 . ISBN 978-3-540-32377-8. S2CID 1952661 .

[cgw-3] 1 2 3 Chung, FRK; Graham, RL ; Wilson, RM (1989). "Grafos cuasi-aleatorios" (PDF) . Combinatorica . 9 (4): 345– 362. doi : 10.1007/BF02125347 . S2CID 17166765 .

[4] Simonovits, Miklós; Sós, Vera (1991). "La partición y la cuasi aleatoriedad de Szemerédi". Estructuras aleatorias y algoritmos . 2 : 1– 10. doi : 10.1002/rsa.3240020102 .

[5] Conlon, David; Zhao, Yufei (2017). "Grafos de Cayley cuasialeatorios". Análisis discreto . 6. arXiv : 1603.03025 . doi : 10.19086/da.1294 . S2CID 56362932 .

[6] Friedman, Joel (2003). "Expansores relativos o grafos de Ramanujan débilmente relativos". Duke Math. J. 118 ( 1): 19– 35. doi : 10.1215/S0012-7094-03-11812-8 . MR 1978881 .

[7] Krivelevich, Michael; Sudakov, Benny; Vu, Van H.; Wormald, Nicholas C. (2001). "Grafos regulares aleatorios de alto grado". Random Structures and Algorithms . 18 (4): 346– 363. doi : 10.1002/rsa.1013 . S2CID 16641598 .

[aks-8] 1 2 Alon, Noga ; Krivelevich, Michael ; Sudakov, Benny (1999). "Coloración de listas de grafos aleatorios y pseudoaleatorios". Combinatorica . 19 (4): 453– 472. doi : 10.1007/s004939970001 . S2CID 5724231 .

[9] Conlon, David ; Fox, Jacob ; Zhao, Yufei (2014). "El teorema de Green-Tao: una exposición". EMS Surveys in Mathematical Sciences . 1 (2): 249– 282. arXiv : 1403.2957 . doi : 10.4171/EMSS/6 . MR 3285854. S2CID 119301206 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]