Método probabilístico

El método probabilístico es un método no constructivo para probar la existencia de un objeto matemático con propiedades dadas. Se utiliza principalmente en combinatoria , pero también en teoría de números , álgebra lineal y cálculo , así como en informática (como el método de redondeo probabilístico ) y teoría de la información .

El método consiste en estimar la probabilidad de que un objeto aleatorio de una clase determinada satisfaga la condición deseada. Si se prueba que esta probabilidad es positiva, entonces existe un objeto con las propiedades deseadas. Aunque la prueba usa probabilidades, la conclusión final es definitiva, sin ambigüedad alguna.

Las herramientas comunes utilizadas en el método probabilístico incluyen la desigualdad de Markov , la desigualdad de Chernov y el lema local de Lovas .

Historia

La aplicación más famosa de este método está asociada con Erdős . Sin embargo, el método probabilístico se aplicó incluso antes del trabajo de Erdős en esta dirección. Por ejemplo, Seles en 1943 utilizó el método para demostrar que existen torneos que contienen una gran cantidad de ciclos hamiltonianos .

Ejemplos

Los siguientes dos ejemplos de la aplicación del método probabilístico se analizan en detalle en el libro Evidence from the Book de Martin Aigner y Günter Ziegler .

Límite inferior para el número de Ramsey

Necesitamos probar la existencia de una coloración en dos colores (digamos, rojo y azul) de las aristas de un grafo completo con vértices (para valores no muy grandes de ) tal que no exista un subgrafo monocromático completo con vértices (que es decir, con cada borde del mismo color). $norte$ $norte$ $r$

Elegiremos los colores al azar. El color de cada borde se elige independientemente con igual probabilidad rojo o azul. Calcule el número esperado de subgrafos monocromáticos completos con vértices de la siguiente manera: $r$

Para cualquier conjunto de vértices en nuestro gráfico, defina un valor de 1 si cada borde termina en el mismo color y 0 en caso contrario. Tenga en cuenta que el número de subgrafos monocromáticos es la suma de todos . $S$ $r$ ${\ estilo de visualización X (S)}$ $S$ $r$ ${\ estilo de visualización X (S)}$ $S$

Para cualquier , la expectativa de es la probabilidad de que todos los bordes tengan el mismo color. Y eso significa $S$ $\mu$ ${\ estilo de visualización X (S)}$ ${r \elegir 2}$ $S$

\mu =2\cdot 2^{-{r \elegir 2)).

El factor 2 aparece porque hay dos colores posibles.

Lo mismo es cierto para cualquiera de los posibles subconjuntos con vértices. Para que la expectativa matemática de la suma sobre todo sea igual ${\displaystyle {n \elegir r))$ $r$ ${\ estilo de visualización X (S)}$ $S$

M={n \elegir r}\cdot \mu ={n \elegir r}\cdot 2\cdot 2^{-{r \elegir 2))

La suma de las expectativas matemáticas es igual a la expectativa de la suma (independientemente de si las variables son independientes ). En otras palabras , existe el número promedio de subgrafos monocromáticos de un gráfico coloreado aleatoriamente. $METRO$ $r$

El número de subgrafos monocromáticos en una coloración aleatoria siempre será un número entero . Por lo tanto, si , entonces en al menos una coloración, no debe haber subgrafos monocromáticos completos. $r$ ${\ estilo de visualización M <1}$ $r$

es decir, si

2\cdot {n \elegir r}<2^{r \elegir 2},

después

{\ Displaystyle R (r, r)> n}

donde denota el número de Ramsey para . En particular, crece al menos exponencialmente en . ${\ estilo de visualización R (r, r)}$ $r$ ${\ estilo de visualización R (r, r)}$ $r$

Notas

La prueba anterior es dada por Erdős. [una]
Este método no da un ejemplo explícito de tal coloración. La cuestión de describir un ejemplo particular ha estado abierta durante más de 50 años.

Construcción de un grafo sin ciclos cortos con gran número cromático

Sean números enteros positivos y dados . Necesitamos construir un gráfico con todos los ciclos de al menos , y al mismo tiempo el número cromático G es al menos . $gramo$ $k$ $GRAMO$ $gramo$ $k$

Arreglamos un entero grande . Considere un gráfico aleatorio con vértices, donde cada borde existe con probabilidad p = n 1/ g −1 . Demostremos que las siguientes dos propiedades se cumplen con probabilidad positiva $norte$ $GRAMO$ $norte$ $GRAMO$

Propiedad 1. contiene como máximo ciclos de duración inferior a . Más precisamente, la probabilidad de que el gráfico no tenga más que ciclos de longitud menor que tiende a 1 cuando . $GRAMO$ $n/2$ $gramo$ $GRAMO$ $n/2$ $gramo$ $n\to\infty$

Prueba. Sea el número de ciclos de longitud menor que . El número de ciclos de longitud en un grafo completo con vértices es $X$ $gramo$ $i$ $norte$

{\frac {n!}{2\cdot i\cdot (ni)!}}\leq {\frac {n^{i}}{2}}

y cada uno de ellos está contenido con probabilidad p i . Por lo tanto, por la desigualdad de Markov, tenemos $GRAMO$

\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}\cdot E[X]\leq {\frac {1}{ n}}\cdot \sum _{i=3}^{g-1}p^{i}\cdot n^{i}={\frac {1}{n}}\cdot \sum _{i= 3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}\cdot n^{\frac {g-1}{g}}=g \cdot n^{-{\frac {1}{g}}}=o(1).

■

La propiedad 2. no contiene un conjunto independiente de tamaño . Más precisamente, la probabilidad de que un gráfico tenga un conjunto de tamaño independiente tiende a 1 cuando . $GRAMO$ $\lceil {\tfrac {n}{2k))\rceil$ $GRAMO$ $\lceil {\tfrac {n}{2k))\rceil$ $n\to\infty$

Prueba. Denotemos el tamaño del conjunto independiente más grande en . obviamente tenemos $Y$ $GRAMO$

\Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2))\leq n^{y}e^{ -{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln np)}=o(1),

cuando

y=\left\lceil {\frac {n}{2k))\right\rceil .

■

Como tiene estas dos propiedades, podemos extraer el máximo de vértices de para obtener un nuevo gráfico con vértices que contengan solo ciclos de longitud como máximo . Vemos que tiene un conjunto de tamaños independiente . solo se puede dividir en al menos conjuntos independientes, y por lo tanto tiene un número cromático de al menos . $GRAMO$ $n/2$ $GRAMO$ $GRAMO'$ $n'\geq n/2$ $gramo$ $GRAMO'$ $\lceil {\frac {n'}{k))\rceil$ $GRAMO'$ $k$ $k$

Notas

Este resultado explica por qué calcular el número cromático de un gráfico es una tarea difícil. Incluso en ausencia de causas locales (como ciclos pequeños), el número cromático puede ser arbitrariamente grande.

Véase también

Recuento aleatorio

Literatura

Aigner M. Ziegler G. Evidencia del Libro. La mejor evidencia desde la época de Euclides hasta nuestros días. - Editorial "Laboratorio del Saber" (anteriormente "BINOM. Laboratorio del Saber"), 2014. - ISBN 978-5-9963-2736-2 .

Alon N., Spencer J. Método probabilístico, Binom, 2007, p. 320, 1100 copias. ISBN 978-5-94774-556-6

A. M. Raigorodsky . Gráficas con gran número cromático y gran perímetro // Matem. iluminación , ser. 3. - 2016. - T. 20 . - S. 228-237 . (Ruso)

En inglés

Erdős, P. Teoría de grafos y probabilidad (indefinida) // Canad. J. Math .. - 1959. - T. 11 , No. 0 . - S. 34-38 . -doi : 10.4153 / CJM-1959-003-9 . Archivado desde el original el 18 de julio de 2011.

J. Matousek, J. Vondrak. El Método Probabilístico . notas de lectura.

Alon, N y Krivelevich, M (2006). Combinatoria extrema y probabilística

Notas al pie

↑ Erdös, P. Algunas observaciones sobre la teoría de grafos. Toro. amer Matemáticas. soc. 53, (1947). 292–294.