Topological cliques in sparse expanders

Abstract

In the paper, we focus on embedding clique immersions and subdivisions within sparse expanders, and we derive the following main results: (1) For any $0<\hat{I}\cdot <1/2$, there exists $K>0$ such that for sufficiently large $n$, every $(n,d,\hat{I}»)$-graph $G$ contains a $K_{(1-5\hat{I}\cdot )d}$-immersion when $d\ge K\hat{I}»$. (2) For any $\epsilon >0$ and $0<\hat{I}\cdot <1/2$, the following holds for sufficiently large $n$. Every $(n,d,\hat{I}»)$-graph $G$ with $2048\hat{I}»/\hat{I}{\cdot }^2<d\le \hat{I}\cdot n^{1/2-\epsilon }$ contains a $K_{(1-\hat{I}\cdot )d}^{(\ell )}$-subdivision, where $\ell =2\lceil \log (\hat{I}{\cdot }^{2}n/4096)\rceil +5$. (3) There exists $c>0$ such that the following holds for sufficiently large $d$. If $G$ is an $n$-vertex graph with average degree $d(G)\ge d$, then $G$ contains a $K_{cd}^{(\ell )}$-immersion for some $\ell \in \mathbb{N}$. In 2018, Dvo{ř}{á}k and Yepremyan asked whether every graph $G$ with $\hat{I}´(G)\ge t$ contains a $K_t$-immersion. Our first result shows that it is asymptotically true for $(n,d,\hat{I}»)$-graphs when $\hat{I}»=o(d)$. In addition, our second result extends a result of Dragani{ć}, Krivelevich and Nenadov on balanced subdivisions. The last result generalises a result of DeVos, Dvo{ř}{á}k, Fox, McDonald, Mohar, Scheide on $1$-immersions of large cliques in dense graphs.