The Probabilistic Method

作者：Joel Spencer · 发表于：Medical Entomology and Zoology · 年份：1991 · 被引用次数：4390 · 研究领域：Advanced Graph Theory Research、Computability, Logic, AI Algorithms、Graph Labeling and Dimension Problems

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 Erdoő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.