Rutgers Mathematics Department Colloquium

Title:

Sharp Thresholds for Random Graph Properties

Speaker:

Gil Kalai

IAS and Hebrew University

Place:

Hill Center, Room 705

CoRE Building

Rutgers University

Time:

4:30 PM

Friday, November 17, 1995

Abstract:

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