比利时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****************************