UConn Math Club
The Probabilistic Method
Sean Li (University of Connecticut)
Wednesday, April 25, 2018
The probabilistic method is a way to prove the existence of deterministic objects and structures via probabilistic means. Rather than giving an explicit construction, one gives a random construction and tries to prove that the random construction has a positive probability of achieving the desired property. This method was pioneered by Erdos and his collaborators in their study of graphs with special properties. We will see examples of the probabilistic method in action in combinatorics and theoretical computer science.
Comments: Free pizza and drinks!