Computer Science/Discrete Mathematics Seminar I | |

Topic: | Large deviations in random graphs |

Speaker: | Eyal Lubetzky |

Affiliation: | New York University |

Date: | Monday, April 9 |

Time/Room: | 11:00am - 12:15pm/West Building Lecture Hall |

What is the probability that the number of triangles in the Erd\H{o}s-R\'enyi random graph with edge density $p$, is at least twice its mean? What is the typical structure of the graph conditioned on this rare event? For instance, when $p=o(1)$, already obtaining the order of log of this probability was a longstanding open problem finally settled by Chatterjee and by DeMarco and Kahn, whereas the latter problem remains largely open. I will review some recent progress on these questions and related ones, in both the dense and sparse regimes of the random graph.