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