Probabilistic Methods

The Probabilistic Method was primarily used in Combinatorics and pioneered by Erdös Pai, better known to Westerners as Paul Erdos in the 1950s. The probabilistic method is a powerful tool for solving many problems in discrete mathematics, combinatorics and also in graph .theory. It is also very useful to solve problems in number theory, combinatorial geometry, linear algebra and real analysis. More recently, it has been applied in the development of efficient algorithms and in the study of various computational problems.Broadly, the probabilistic method is somewhat opposite of the extremal graph theory. Instead of considering how a graph can behave in the extreme, we consider how a collection of graphs behave on \u27average\u27 where by we can formulate a probability space. The method allows one to prove the existence of a structure with particular properties by defining an appropriate probability space of structures and show that the desired properties hold in the space with positive probability.(please see PDF for complete abstract