A Turán-type Extremal Theory of Convex Geometric Graphs
A Turán-type Extremal Theory of Convex Geometric Graphs
复制标题
凸几何图的图兰型极值理论
DOI：
10.1007/978-3-642-55566-4_12
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
P. Valtr
中科院分区：
文献类型：
--
作者：
Peter Braß;G. Károlyi;P. Valtr
我们研究具有额外的顶点循环排序的图（即凸几何图）的图兰型极值问题。如果排除子图的适当定义的色数大于二，那么凸几何图上的结果非常类似于图兰理论的经典结果。另一方面，在二分案例中，我们表现出一些令人惊讶的差异，特别是对于树木和森林。例如，某些凸几何森林的 Turan 函数的量级为 θ(n log n)，这是图 Turan 理论中不会出现的增长率。我们还获得了 Furedi 在凸 n 边形中单位距离数量上的 O(n log n) 界限的另一个证明，以及显示该模型极限的下界。还确定了几个无限类凸几何图的图兰函数的精确增长。
We study Turan-type extremal questions for graphs with an additional cyclic ordering of the vertices, i.e. for convex geometric graphs. If a suitably defined chromatic number of the excluded subgraph is bigger than two then the results on convex geometric graphs resemble very much the classical results from the Tur´an theory. On the other hand, in the bipartite case we show some surprising differences, in particular for trees and forests. For example, the Turan function of some convex geometric forests is of the order Θ(n log n), a growth rate that does not occur in the graph Turan theory. We also obtain still another proof of Furedi’s O(n log n) bound on the number of unit distances in a convex n-gon, together with a lower bound showing the limits of this model. The exact growth of the Turan function for several infinite classes of convex geometric graphs is also determined.