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 -