printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 269 - seminar in combinatorics

zhifei yan

impa, rio de janeiro (zhifei.yan@impa.br)

the chromatic number of very dense random graphs

abstract:

the chromatic number of a very dense random graph $g(n,p)$, with $p \ge 1 - n^{-c}$ for some constant $c > 0$, was first studied by surya and warnke, who  conjectured that the typical deviation of $\chi(g(n,p))$ from its mean is of order $\sqrt{\mu_r}$, where $\mu_r$ is the expected number of independent sets of size $r$, and $r$ is maximal such that $\mu_r > 1$, except when $\mu_r = o(\log n)$. they moreover proved their conjecture in the case $n^{-2} \ll 1 - p = o(n^{-1})$.

in this talk, we study $\chi(g(n,p))$ in the range $n^{-1}\log n \ll 1 - p \ll n^{-2/3}$, that is, when the largest independent set of $g(n,p)$ is typically of size 3. we prove in this case that $\chi(g(n,p))$ is concentrated on some interval of length $o(\sqrt{\mu_3})$, and for sufficiently `smooth' functions $p = p(n)$, that there are infinitely many values of $n$ such that $\chi(g(n,p))$ is not concentrated on any interval of size $o(\sqrt{\mu_3})$. we also show that $\chi(g(n,p))$ satisfies a central limit theorem in the range $n^{-1} \log n \ll 1 - p \ll n^{-7/9}$.

this talk is based on arxiv:2405.13914

october 15, 2024

2:00 pm

ap&m 7321 (zoom-talk: meeting id: 941 1988 0012, password: 634921)

research areas

combinatorics probability theory

****************************