Sep 24
Math/Stats Colloquium: Corrine Yap, Georgia Institute of Technology & the Algorithms and Randomness Center
Title: Evolution of Random Discrete Structures
Abstract: In grade school, we learn about phase transitions: at what temperature does solid turn to liquid and liquid turn to gas? The phenomenon of phase transitions occurs not only in nature but also in mathematics. Suppose we create a random network by flipping independent coins to determine if nodes are connected. If each coin is biased, what is the typical structure of the network? What amount of bias will result in the network being connected? In this talk, we'll discover several notions of "thresholds," including those defined by structural properties, by the existence of efficient sampling algorithms, and by the evolution rate of a dynamical process. Our examples will come from combinatorics, computer science, and statistical physics, but no background with these topics will be assumed!