All Monotone Graph Properties Have Sharp Thresholds

Gil Kalai (Institute for Advanced Study and Hebrew University)

In their seminal work which initiated random graph theory Erd\"os and R\'enyi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. That is, if every edge of the graph is chosen with probability $p$, then when $p$ increases, the transition from a property being very unlikely to its being very likely is very swift. We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This result applies to random subgraphs of arbitrary symmetric graphs. We will discuss the relation between the symmetry group and the length of the transition interval.