The probabilistic method

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
PublisherAssociation for Computing Machinery
Pages41-47
Number of pages7
ISBN (Electronic)089791466X
StatePublished - Sep 1 1992
Event3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992 - Orlando, United States
Duration: Jan 27 1992Jan 29 1992

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
VolumePart F129721

Other

Other3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
CountryUnited States
CityOrlando
Period1/27/921/29/92

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The probabilistic method'. Together they form a unique fingerprint.

Cite this