¿Cuáles son las relaciones entre la combinatoria y el azar?

Question

Acabo de leer el impresionante documento de Tim Gowers Las dos culturas de las matemáticas cuando me di cuenta de las diversas conexiones entre la combinatoria y la aleatoriedad. Como no soy matemático, no me resulta intuitivamente obvio cuál es el alcance de la relación entre ambas, aparte de la idea de que la combinatoria implica el recuento y el recuento es necesario para la probabilidad preliminar (trabajo en aprendizaje automático).

¿Cuáles son los principales resultados que relacionan la combinatoria y la aleatoriedad, y cómo se conectan?

Answer 1

La probabilidad en combinatoria se utiliza a menudo en el marco del método probabilístico

http://en.wikipedia.org/wiki/Probabilistic_method

Un buen resultado que se obtuvo por primera vez con el método probabilístico es el siguiente

Por cada $k$ y $g$ existe un gráfico $G$ de la circunferencia $g$ (longitud del ciclo mínimo) tal que el número cromático de $G$ es al menos $k$ .

Así, un aspecto en el que se puede utilizar la probabilidad en combinatoria es mostrando que la probabilidad de que exista un objeto combinatorio dado es distinta de cero, lo que a su vez permite mostrar la existencia de dicho objeto, sin construirlo explícitamente.