论文标题
强大的（彩虹）细分和简单周期
Robust (rainbow) subdivisions and simplicial cycles
论文作者
论文摘要
我们在拓扑性质的极端图和超图理论中介绍了几个结果。首先，我们表明，如果$α> 0 $和$ \ ell =ω（\ frac {1}α\ log \ frac \ frac {1}α$是一个奇数的整数，那么每个图形$ g $带有$ n $ vertices和$ n $ vertices和$ n $ n^{1+α} $ edges包含$ \ ell $ -Sphrable $ ell $ -subdiviv，则$ t = n^{θ（α）} $。另外，如果此外，如果$ g $的边缘得到适当的颜色，并且希望找到这样一个细分的彩虹副本，则这是正确的。在稀疏制度中，我们表明，在$ n $顶点上具有适当的边缘彩色图形，其平均度$ $（\ log n）^{2+o（1）} $包含彩虹循环，而平均度$（\ log n）^{6+o（1）$保证$ k_t $ k_t $的$ k_t $ to $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t。此外，我们考虑了纯简单复合物（均匀的超图）中循环的某些拓扑概念。我们表明，如果$ g $是$ 2 $二维的纯简单综合体（$ 3 $ -graph），$ n $ 1 $ 1 $ - 二维，至少$ n^{1+α} $ 2维面，然后$ g $包含圆柱的三角形，则cylinder and theMöbius条$ O（\ frac {1}α\ log \ frac {1}α）$ vertices。我们对更高维的纯简单复合物也提出了概括。为了证明这些结果，我们考虑了具有强大扩展的某些（适当边缘的彩色）图和超图$ g $。我们认为，如果一个随机的$ g $的顶点（和颜色）的可能性不小，那么许多顶点是通过一个短路径连接的，其顶点（和颜色）来自采样集，具有很高的可能性。
We present several results in extremal graph and hypergraph theory of topological nature. First, we show that if $α>0$ and $\ell=Ω(\frac{1}α\log\frac{1}α)$ is an odd integer, then every graph $G$ with $n$ vertices and at least $n^{1+α}$ edges contains an $\ell$-subdivision of the complete graph $K_t$, where $t=n^{Θ(α)}$. Also, this remains true if in addition the edges of $G$ are properly colored, and one wants to find a rainbow copy of such a subdivision. In the sparser regime, we show that properly edge colored graphs on $n$ vertices with average degree $(\log n)^{2+o(1)}$ contain rainbow cycles, while average degree $(\log n)^{6+o(1)}$ guarantees rainbow subdivisions of $K_t$ for any fixed $t$, thus improving recent results of Janzer and Jiang et al., respectively. Furthermore, we consider certain topological notions of cycles in pure simplicial complexes (uniform hypergraphs). We show that if $G$ is a $2$-dimensional pure simplicial complex ($3$-graph) with $n$ $1$-dimensional and at least $n^{1+α}$ 2-dimensional faces, then $G$ contains a triangulation of the cylinder and the Möbius strip with $O(\frac{1}α\log\frac{1}α)$ vertices. We present generalizations of this for higher dimensional pure simplicial complexes as well. In order to prove these results, we consider certain (properly edge colored) graphs and hypergraphs $G$ with strong expansion. We argue that if one randomly samples the vertices (and colors) of $G$ with not too small probability, then many pairs of vertices are connected by a short path whose vertices (and colors) are from the sampled set, with high probability.
