摘要 Abstract
本文研究了满足特定拟随机条件的图中生成团细分结构的存在性问题。具体而言,我们证明了以下三个结果。首先,存在常数 $C>0$ 和 $c\in (0,1]$,使得当 $d/\lambda \geq C$ 时,每个 $(n,d,\lambda)$-图包含生成 $K_t$ 的细分结构,其中 $2\leq t \leq \min\{cd,c\sqrt{\frac{n}{\log n}}\}$。其次,存在常数 $C>0$ 和 $c\in (0,1]$,使得当 $d/\lambda \geq C\log^3n$ 时,每个 $(n,d,\lambda)$-图包含生成近似平衡的 $K_t$ 的细分结构,其中 $2\leq t \leq \min\{cd,c\sqrt{\frac{n}{\log^3n}}\}$。最后,我们证明了对于任意 $\mu>0$,存在常数 $c,\varepsilon\in (0,1]$ 和 $n_0\in \mathbb{N}$,使得当 $n\geq n_0$ 时,每个最小度至少为 $\mu n$ 且不含 $\varepsilon n$ 大小二分洞的 $n$-顶点图包含生成近似平衡的 $K_t$ 的细分结构,其中 $2\leq t \leq c\sqrt{n}$。
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/\lambda\ge C$, every $(n,d,\lambda)$-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/\lambda\ge C\log^3n$, every $(n,d,\lambda)$-graph contains a spanning nearly-balanced subdivision of $K_t$ for all $2\le t \le \min\{cd,c\sqrt{\frac{n}{\log^3n}}\}$. Finally, we show that for every $\mu>0$, there are constants $c,\varepsilon\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 $\mu n$ and no bipartite holes of size $\varepsilon n$ contains a spanning nearly-balanced subdivision of $K_t$ for all $2\le t \le c\sqrt{n}$.