El método probabilístico en matemáticas discretas

Abstract

The next paper deals with the probabilistic method. The probabilistic method is a non-constructive tool that uses probability theory to demonstrate the existence of mathematical "objects." Since there is no standard way of applying these demonstrations many people prefer to call them probabilistic (plural) methods. These methods have been used for several decades, although the first demonstrations that were made using them were not given much attention. It was not until Paul Erdos began to demonstrate with these techniques that they were given importance. Thanks to these techniques at last, solutions to problems that had long been classified as mere conjectures could be solved. These techniques are mainly applied to discrete math problems. In addition, these offer quite comfort when dealing with graph theory. This is why most of the results shown in the paper are on theory of graphs and discrete mathematics in general. All chapters show at least one graph theory result. Briefly, we can say that these methods consist of the following: Define an appropriate sample space, measure the probability that an object exists and, if it is positive, then the object exists. When the sample space is finite, the problem of calculating a probability becomes a counting problem. Often counting problems become difficult to manage, rather than fully solved using quotas that offer theories of probability theory. This is very useful when dealing with graphics problems where hypotheses are usually scarce and the possibilities for graphics are many and difficult to handle.

El siguiente trabajo trata sobre el método probabilístico. El método probabilístico es una herramienta no constructiva que utiliza teoría de la probabilidad para de- mostrar la existencia de “objetos” matemáticos. Como no existe una forma estándar de aplicar estas demostraciones muchas personas prefieren llamarles métodos probabilísticos (en plural). Estos métodos se han usado durante varias décadas, aunque, a las primeras de- mostraciones que se hicieron utilizándolos no se les prestó mucha atención. No fue sino hasta que Paul Erdós empezó a hacer demostraciones con estas técnicas que se les dio importancia. Gracias a estas técnicas por fin se pudo dar solución a problemas que por mucho tiempo habían sido clasificados como meras conjeturas. Estas técnicas son principalmente aplicadas en problemas de matemáticas discretas. Además, estas ofrecen bastante comodidad al tratar con teoría de gráficas. Es por esto que la mayoría de los resultados que se muestran en el trabajo son sobre teoría de gráficas y matemáticas discretas en general. En todos los capítulos se muestra al menos un resultado de teoría de gráficas. De manera breve, se puede decir que estos métodos consisten en lo siguiente: Definir un espacio muestral apropiado, medir la probabilidad de que cierto objeto existe y, si ésta es positiva, entonces el objeto existe. Cuando el espacio muestral es finito, el problema de calcular una probabilidad se vuelve en un problema de conteo. Muchas veces los problemas de conteo se vuelven difíciles de manejar, en vez de resolverlos completamente se utilizan cotas que ofrecen los teoremas de teoría de la probabilidad. Esto es muy útil cuando se trata con problemas de gráficas donde usualmente las hipótesis son escasas y las posibilidades para las gráficas son muchas y difíciles de manejar.