Large deviations in random graphs - Yufei Zhao

From Katie Gentilello May 22nd, 2018

23 plays 0 comments

What is the probability that the number of triangles in an Erd\H{o}s–R\'enyi random graph exceeds its mean by a constant factor?

This problem has been a useful litmus test for concentration bound techniques. Even the order of the log-probability was considered a difficult problem until its resolution a few years ago by Chatterjee and DeMarco--Kahn. I will discuss the problem of determining the exponential rate of the tail probability, and survey some recent developments and open problems.

https://mediaspace.gatech.edu/media/zhao.mpg/1_bnt5jhmr

Tags: workshop on algorithms and randomnessalgorithms and randomness centergeorgia techrecorded by gtlibraryspring 2018

name: Yufei Zhao
Date: May 14th, 2018
Appears In: Open Scholarship

Comments
Related Media

Add a comment

Large deviations in random graphs - Yufei Zhao

Related Media