Upper tail estimates for cycles in the random graph

Combinatorics Seminar
Event time: 
Thursday, January 24, 2019 - 4:00pm
DL 431
Abigail Raz
Speaker affiliation: 
Rutgers University
Event description: 
Let $X_H$ denote the number of copies of a fixed graph $H$ in the random graph $G(n,p)$.  Determining the behavior of $X_H$ has long been a central problem in probabilistic combinatorics.  Although many results have been established for this random variable, the problem of determining the upper tail of $X_H$ is still an area of active research.  In this talk, we examine the case where $H$ is an $l$-cycle, showing that
$\mathbb{P}(X_H > (1+\epsilon)E[X_H])<\exp[-C_{\epsilon,l}\min\{n^2p^2 \log(1/p),n^lp^l\}]$.
Research Area(s):