Spanning clique subdivisions in pseudorandom graphs

Abstract

In this paper, we study the appearance of a spanning subdivision of a clique in graphs satisfying certain pseudorandom conditions. Specifically, we show the following three results. Firstly, that there are constants $C>0$ and $c\in (0,1]$ such that, whenever $d/\hat{I}»\ge C$, every $(n,d,\hat{I}»)$-graph contains a spanning subdivision of $K_t$ for all $2\le t\le \min \{cd,c\sqrt{\frac{n}{\log n}}\}$. Secondly, that there are constants $C>0$ and $c\in (0,1]$ such that, whenever $d/\hat{I}»\ge C{\log }^{3}n$, every $(n,d,\hat{I}»)$-graph contains a spanning nearly-balanced subdivision of $K_t$ for all $2\le t\le \min \{cd,c\sqrt{\frac{n}{{\log }^{3}n}}\}$. Finally, we show that for every $\hat{I}¼>0$, there are constants $c,\epsilon \in (0,1]$ and $n_0\in \mathbb{N}$ such that, whenever $n\ge n_0$, every $n$-vertex graph with minimum degree at least $\hat{I}¼n$ and no bipartite holes of size $\epsilon n$ contains a spanning nearly-balanced subdivision of $K_t$ for all $2\le t\le c\sqrt{n}$.

To appear in Combinatorics, Probability and Computing. 17 pages, 1 figure