×

More Turán-type theorems for triangles in convex point sets. (English) Zbl 1409.90212

Summary: 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.

MSC:

90C35 Programming involving graphs or networks
05D99 Extremal combinatorics

Software:

OEIS
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] F. Behrend. On sets of integers which contain no three terms in arithmetic progression. Proceedings of the National Academy of Sciences USA, 32:331-332, 1946. · Zbl 0060.10302
[2] Peter Braß. Tur´an-type extremal problems for convex geometric hypergraphs. Contemporary Mathematics, 342:25-34, 2004. · Zbl 1060.05074
[3] Peter Braß, G¨unter Rote, and Konrad J. Swanepoel. Triangles of extremal area or perimeter in a finite planar point set. Discrete & Computational Geometry, 26(1):51– 58, 2001.doi:10.1007/s00454-001-0010-6. · Zbl 0982.52014
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, second edition, 2001. · Zbl 1047.68161
[5] J. Fox. A new proof of the graph removal lemma. Annals of Mathematics, 174:561-579, 2011. · Zbl 1231.05133
[6] W. T. Gowers and J. Long. The length of an s-increasing sequence of r-tuples. arXiv:1609.08688, 2016. · Zbl 1510.05285
[7] Po-Shen Loh.Directed paths:from Ramsey to Ruzsa and Szemer´edi. arXiv:1505.07312v2, 2016.
[8] I. Z. Ruzsa and E. Szemer´edi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), 18:939-945, 1978.
[9] N. J. A. Sloane. The online encyclopedia of integer sequences. Sequence number A070214. URL:http://oeis.org/A070214. · Zbl 1044.11108
[10] Sherman Stein. Combinatorial packing of Rnby certain error spheres. IEEE Transactions on Information Theory, 30(2):364-368, 1984. · Zbl 0552.05025
[11] Sherman K. Stein. Packing tripods. Mathematical Intelligencer, 17(2):37-39, 1995. · Zbl 0864.00004
[12] Sherman K. Stein and S´andor Szab´o Algebra and Tiling: Homomorphisms in the Service of Geometry, volume 25 of The Carus Mathematical Monographs.The Mathematical Association of America, 1994.
[13] Alexandre Tiskin. Packing tripods: Narrowing the density gap. Discrete Mathematics, 307(16):1973-1981, 2007. · Zbl 1118.05013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.