论文标题
完全简单的拓扑图中的不可避免的模式
Unavoidable patterns in complete simple topological graphs
论文作者
论文摘要
我们表明，每个完整的$ n $ vertex简单拓扑图都包含至少$（\ log n）^{1/4- o（1）} $ vertices上的拓扑子图，该the是弱同构的，对于完整的凸线几何图或完整的扭曲图。这是Pach，Solymosi和Tóth2003年获得的BOND $ω（\ log^{1/8} n）$的第一个改进。我们还表明，每个完整的$ n $ vertex简单拓扑图都包含一个长度的平面路径至少$（\ log n）^{1 -o（1）} $。
We show that every complete $n$-vertex simple topological graph contains a topological subgraph on at least $(\log n)^{1/4 - o(1)}$ vertices that is weakly isomorphic to the complete convex geometric graph or the complete twisted graph. This is the first improvement on the bound $Ω(\log^{1/8}n)$ obtained in 2003 by Pach, Solymosi, and Tóth. We also show that every complete $n$-vertex simple topological graph contains a plane path of length at least $(\log n)^{1 -o(1)}$.
