Home / Workshop / Schedules / Using uncertainty to establish certainty
Using uncertainty to establish certainty
October 08, 2008 (02:00 PM PDT - 03:00 PM PDT)
Speaker(s):
Po-Shen Loh
Primary Mathematics Subject Classification
No Primary AMS MSC
Secondary Mathematics Subject Classification
No Secondary AMS MSC
Abstract
"Leave nothing to chance." When accuracy is paramount, this maxim reflects the common belief that elaborate planning is essential for success. One would expect that in the rigorous environment of mathematical logic, such a statement would hold the status of doctrine. However, half a century ago, researchers discovered that to the contrary, artificially-introduced randomness could be used as a powerful tool to prove deterministic statements with absolute certainty. This revolutionized the field of discrete mathematics. Indeed, consider the following application. Suppose one needs to show the existence of a combinatorial arrangement with certain properties. Instead of exhibiting an (often intricate) satisfying construction, consider a random arrangement, sampled from a suitable probablility space. It is then enough to show that the random arrangement is suitable with probability strictly greater than zero. This alternative perspective allows one to apply results from the theory of probability, and in many cases it makes the problem substantially more tractable. In this talk, we will showcase this technique, now known as the Probabilistic Method, through examples and applications.
Supplements
No Notes/Supplements Uploaded
Video/Audio Files
No Video Files Uploaded
