Alan Frieze (Carnegie Mellon University)
Large combinatorial objects such as random graphs can exhibit sharp transitions in their structure as they grow. As an example, consider the graph process where we start with a graph with many vertices and no edges and add random edges one by one. There is a rapid change in structure at around the time when the average degree reaches 1. This "Phase Transition" has been the subject of intense study. In a similar vein we find that many other graph properties, such as connectivity or 3-colorability, appear relatively suddenly at a precise threshold. In this talk we give a brief survey of various aspects of thresholds and phase transitions in combinatorics.
Light refreshments will be served before the lecture at 3:30 p.m.