Spanning clique subdivisions in pseudorandom graphs

Source abstract

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 results. (i) There are constants upper C greater than 0 C > 0 $C\gt 0$ and c element of left parenthesis 0 comma 1 right bracket c ∈ ( 0 , 1 ] $c\in (0,1]$ such that, whenever d divided by lamda greater than or equals upper C d / λ ≥ C $d/\lambda \ge C$ , every left parenthesis n comma d comma lamda right parenthesis ( n , d , λ ) $(n,d,\lambda )$ -graph contains a spanning subdivision of upper K Subscript t K t $K_t$ for all 2 less than or equals t less than or equals min left brace c d comma c StartRoot StartFraction n Over log n EndFraction EndRoot right brace 2 ≤ t ≤ min { c d , c n log ⁡ n } $2\le t \le \min \{cd,c\sqrt {\frac {n}{\log n}}\}$ . (ii) There are constants upper C greater than 0 C > 0 $C\gt 0$ and c element of left parenthesis 0 comma 1 right bracket c ∈ ( 0 , 1 ] $c\in (0,1]$ such that, whenever d divided by lamda greater than or equals upper C log cubed n d / λ ≥ C log 3 ⁡ n $d/\lambda \ge C\log ^3n$ , every left parenthesis n comma d comma lamda right parenthesis ( n , d , λ ) $(n,d,\lambda )$ -graph contains a spanning nearly balanced subdivision of upper K Subscript t K t $K_t$ for all 2 less than or equals t less than or equals min left brace c d comma c StartRoot StartFraction n Over log cubed n EndFraction EndRoot right brace 2 ≤ t ≤ min { c d , c n log 3 ⁡ n } $2\le t \le \min \{cd,c\sqrt {\frac {n}{\log ^3n}}\}$ . (iii) For every mu greater than 0 μ > 0 $\mu \gt 0$ , there are constants c comma epsilon element of left parenthesis 0 comma 1 right bracket c , ε ∈ ( 0 , 1 ] $c,\varepsilon \in (0,1]$ and n 0 element of double struck upper N n 0 ∈ N $n_0\in \mathbb N$ such that, whenever n greater than or equals n 0 n ≥ n 0 $n\ge n_0$ , every n n $n$ -vertex graph with minimum degree at least mu n μ n $\mu n$ and no bipartite holes of size epsilon n ε n $\varepsilon n$ contains a spanning nearly balanced subdivision of upper K Subscript t K t $K_t$ for all 2 less than or equals t less than or equals c StartRoot n EndRoot 2 ≤ t ≤ c n $2\le t \le c\sqrt {n}$ .