TY - GEN

T1 - The probabilistic method

AU - Spencer, Joel

PY - 1992/9/1

Y1 - 1992/9/1

N2 - The use of randomness is now an accepted tool in Theoretical Computer Science but not everyone is aware of the underpinnings of this methodology in Combinatorics - particularly, in what is now called the Probabilistic Method as developed primarily by Paul Erdös over the past half century. Here I will explore a particular set of problems - all dealing with "good" colorings of an underlying set of points relative to a given family of sets. A central point will be the evolution of these problems from the purely existential proofs of Erdös to the algorithmic aspects of much interest to this audience.

AB - The use of randomness is now an accepted tool in Theoretical Computer Science but not everyone is aware of the underpinnings of this methodology in Combinatorics - particularly, in what is now called the Probabilistic Method as developed primarily by Paul Erdös over the past half century. Here I will explore a particular set of problems - all dealing with "good" colorings of an underlying set of points relative to a given family of sets. A central point will be the evolution of these problems from the purely existential proofs of Erdös to the algorithmic aspects of much interest to this audience.

UR - http://www.scopus.com/inward/record.url?scp=0039963923&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039963923&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0039963923

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 41

EP - 47

BT - Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

PB - Association for Computing Machinery

T2 - 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

Y2 - 27 January 1992 through 29 January 1992

ER -