# 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