Probabilístico método utilizado para demostrar los teoremas de existencia

Question

Busco un "grande" lista de teoremas con probabilidad de técnicas para demostrar la existencia de algunos objetos. Y en cada caso, no es una cuestión interesante, podemos encontrar un ejemplo claro? Fue el método de probabilidades de la primera a venir o fue a raíz de la construcción explícita? Hay ejemplos donde se demuestra que el ejemplo que existe, pero su construcción explícita es imposible?

En wikipedia, en el método de probabilidades, que hacen a proponer dos ejemplos debido a Erdős:

PRIMERA. Para un grafo completo de n vértices es posible el color de los bordes de la gráfica en dos colores, por lo que no hay ningún subgrafo completo en r vértices que es monocromática (una en cada extremo de colores del mismo color).

Pregunta: ¿hay alguna explícita algoritmo para un colorante?

SEGUNDO. El segundo problema también viene de la teoría de grafos y ofertas con una cromática número de un gráfico: el número mínimo de colores en los que podemos color de la gráfica, de forma que dos vértices adyacentes son de color diferente. Dados dos números enteros positivos $g$ e $k$, ¿existe un gráfico que contiene sólo los ciclos de longitud de, al menos, $g$ de manera tal que su cromática número de al menos $k$? Se puede demostrar, por medio del método de probabilidades de que una gráfica existe para todos los valores de $g$ e $k$.

Pregunta: ¿hay algún algoritmo para proporcionar este tipo de coloración?

Yo no estoy en todo un especialista en teoría de grafos, así que me gustaría escuchar las respuestas a estas preguntas, así como ver otros ejemplos que provienen de otras ramas de las matemáticas.

Answer 1

Estoy un poco sorprendido de que nadie ha mencionado expansores, para que la existencia resultado fue establecido por primera vez por el "método de probabilidades" de una manera muy simple, mientras que ejemplos concretos de expansores son siempre una bonita problema de difícil solución, véase, por ejemplo, Que primero se llamó "los gráficos de expansión"? o Cómo probar un aleatoria d-regular gráfico es un expansor con prob >= 0.5?

Answer 2

Shannon es la prueba de que la capacidad de logro código de las familias existen para ruidosos canales es probabilística en la naturaleza. Sólo relativamente simple canales (por ejemplo, el binario de borrado de canales, o, más recientemente, el binario simétrico canal, y quizás más genérico discretos memoryless canales si puedo tomar algunos resúmenes de la literatura reciente en el valor de cara) tiene código explícito de las familias ha dado, a saber. LDPC y polar códigos, respectivamente.

Answer 3

Problema: teniendo en cuenta los puntos de $x_1, \ldots, x_n$ en $\mathbb{R}^d$ con $n << d$ e $0 < \epsilon < 1$, encontramos un lineal mapa $T \colon \mathbb{R}^d \to \mathbb{R}^k$, $k << d$, tal que $$(1 - \epsilon) ||x_i - x_j|| \leq T(x_i) - T(x_j) \leq (1 + \epsilon) ||x_i - x_j||$$

Solución: para $k > C \frac{\log n}{\epsilon^2}$, un random $d \times k$ matriz tiene la propiedad deseada con alta probabilidad (donde "aleatorio" y "alta probabilidad" puede hacerse precisos).

Este es el Johnson-Lindenstrauss lema - de manera informal, se dice que una pequeña cantidad de grandes dimensiones de datos puede ser proyectada hacia un espacio de pocas dimensiones a través de una adecuada matriz aleatoria sin molestar a la distancia Euclídea demasiado mal. Esto es a menudo utilizado en la práctica para aplicar los algoritmos cuyo tiempo de ejecución es exponencial en la dimensión de la entrada de datos de alta dimensión conjuntos de datos. Curiosamente, es muy difícil comprobar que una determinada matriz tiene el Johnson-Lindenstrauss la propiedad, incluso a pesar de una matriz aleatoria tiene la propiedad con muy alta probabilidad. Recuerdo leer en algún lugar de la descripción de la "búsqueda de heno en un pajar" para este problema.

Answer 4

Respecto a su segunda pregunta, en efecto, hay una constructivo prueba que demuestra que no son escasos los gráficos con arbitrariamente alta cromática número debido a Lovász (por desgracia detrás de un paywall). Sin embargo, usted puede leer este muy animado encuesta por Nesetril en la historia del problema. En efecto, la pregunta explícita de construcciones estaba ya planteada por Erdos en el principio. La encuesta comienza con las muchas construcciones para el triángulo-gratuita de su caso y procede a la corriente de estado-of-the-art, pasando a través de muchos temas interesantes (incluyendo Kneser gráficos y expansores) a lo largo del camino.

Answer 5

Pensando en mi propia pregunta, yo tenía otra pregunta que vino a mi mente. Tomar cualquier número real y escribir su representación binaria. Con una probabilidad de $1$ la proporción de ceros y unos es la misma y es igual a $1/2$. Podemos decir que por su 3-representación y la representación en cualquier sistema de la proporción de los números es igual a la probabilidad de $1$. Así que casi cualquier número tiene esta propiedad.

Pero, ¿podemos encontrar algún número concreto y demostrar esta propiedad para que?...