Rutgers Mathematics Department Colloquium


Sharp Thresholds for Random Graph Properties


Gil Kalai
IAS and Hebrew University


Hill Center, Room 705
CoRE Building
Rutgers University


4:30 PM
Friday, November 17, 1995


In their work which initiated random graph theory Erdos and Renyi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity; that is: when every edge of the graph is chosen with probability $p$ then when $p$ is increased the transition from a property being very unlikely to it being very likely is very swift.

We prove a conjecture of Linial that every monotone graph property has a sharp threshold as the number of vertices goes to infinity. This result applies to random subgraphs of arbitrary symmetric graphs.

We will discuss the dependence of the threshold interval on a specific symmetry group, this is related to the number and structure of orbits of "large" sets under permutation groups.

(Joint work with Ehud Friedgut.)

Document last modified on November 8, 1995