More Turán-Type Theorems for Triangles in Convex Point Sets

More Turán-Type Theorems for Triangles in Convex Point Sets
复制标题

更多凸点集中三角形的图兰型定理

DOI：
10.37236/7224
复制
发表时间：
2017
期刊：
ArXiv
影响因子：
--
通讯作者：
Luís Fernando Schultz Xavier da Silveira
Luís Fernando Schultz Xavier da Silveira
中科院分区：
--
文献类型：
--
作者：
B. Aronov;V. Dujmović;Pat Morin;Aurélien Ooms;Luís Fernando Schultz Xavier da Silveira

文献摘要

被引文献

相似文献

我们研究了如下问题族：给定一个凸位置上的n个点，在避免某些禁止构形的情况下，以这些点为顶点可以创建的三角形的最大数目是多少？作为禁止构形，我们考虑了这样一个点集中的一对三角形可以相互作用的所有8种方式，这导致了256个极值Turán型问题。我们给近紧（在一个$\log n$因子）的248这些问题的界限，并表明，其余8个问题都是渐近等价于斯坦的长期三脚架包装问题。
We study the following family of problems: Given a set of $n$ points in convex position, what is the maximum number triangles one can create having these points as vertices while avoiding certain sets of forbidden configurations.  As forbidden configurations we consider all 8 ways in which a pair of triangles in such a point set can interact.  This leads to 256 extremal Turán-type questions. We give nearly tight (within a $\log n$ factor) bounds for 248 of these questions and show that the remaining 8 questions are all asymptotically equivalent to Stein's longstanding tripod packing problem.