Mathematical Sciences Research Institute

Home » Workshop » Schedules » Using uncertainty to establish certainty

Using uncertainty to establish certainty

Math Institutes Modern Mathematics Workshop October 08, 2008 - October 09, 2008

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
No Video Uploaded
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