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.)


dimacs-www@dimacs.rutgers.edu
Document last modified on November 8, 1995