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.