More turán-type theorems for triangles in convex point sets

Boris Aronov; Vida Dujmović; Pat Morin; Aurélien Ooms; Luís Fernando; Schultz Xavier da Silveira

doi:10.37236/7224

More turán-type theorems for triangles in convex point sets

Boris Aronov, Vida Dujmović, Pat Morin, Aurélien Ooms, Luís Fernando, Schultz Xavier da Silveira

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Article number	#P1.8
Journal	Electronic Journal of Combinatorics
Volume	26
Issue number	1
DOIs	https://doi.org/10.37236/7224
State	Published - 2019

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/7224

Cite this

@article{91be1cda1f514ae0b47e59d8dbd154a6,

title = "More tur{\'a}n-type theorems for triangles in convex point sets",

abstract = "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{\'a}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{\textquoteright}s longstanding tripod packing problem.",

author = "Boris Aronov and Vida Dujmovi{\'c} and Pat Morin and Aur{\'e}lien Ooms and Lu{\'i}s Fernando and Silveira, {Schultz Xavier da}",

note = "Funding Information: Partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. Funding Information: ∗Partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. †Partially supported by NSERC and the Ontario Ministry of Research and Innovation. ‡Partially supported by NSERC. School of Computer Science, Carleton University, Canada. §Supported by the Fund for Research Training in Industry and Agriculture (FRIA). Publisher Copyright: {\textcopyright} The author.",

year = "2019",

doi = "10.37236/7224",

language = "English (US)",

volume = "26",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - More turán-type theorems for triangles in convex point sets

AU - Aronov, Boris

AU - Dujmović, Vida

AU - Morin, Pat

AU - Ooms, Aurélien

AU - Fernando, Luís

AU - Silveira, Schultz Xavier da

N1 - Funding Information: Partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. Funding Information: ∗Partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. †Partially supported by NSERC and the Ontario Ministry of Research and Innovation. ‡Partially supported by NSERC. School of Computer Science, Carleton University, Canada. §Supported by the Fund for Research Training in Industry and Agriculture (FRIA). Publisher Copyright: © The author.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85061541542&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85061541542&partnerID=8YFLogxK

U2 - 10.37236/7224

DO - 10.37236/7224

M3 - Article

AN - SCOPUS:85061541542

SN - 1077-8926

VL - 26

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - #P1.8

ER -

More turán-type theorems for triangles in convex point sets

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this