On the number of edges in geometric graphs without empty triangles (Q2637713): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q899712 |
Changed an Item |
||
Property / author | |||
Property / author: Marco A. Heredia / rank | |||
Normal rank |
Revision as of 13:33, 21 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the number of edges in geometric graphs without empty triangles |
scientific article |
Statements
On the number of edges in geometric graphs without empty triangles (English)
0 references
14 February 2014
0 references
Given a finite point set \(S\) in the plane in general position, a geometric graph \(G\) on \(S\) has \(S\) as vertex set and its edges are straight line segments joining points of \(S\). A triple \(T\) of points in \(S\) is a triangle of \(G\) if all edges between the points of \(T\) are in \(G\). A triangle is empty if its interior does not contain points from \(S\). Given \(S\), the number \(E(S)\) is the the maximum number of edges over all geometric graphs on \(S\) without empty triangle. The purpose of the paper is to give bounds for the function \(ET(n):=\max\{E(S)\mid \#S=n\}\). A straightforward lower bound of \(\frac{n^2}{4}\) follows from Turán's theorem and \(\binom{n}{2}\) is a strict upper bound, since the complete graph on any point set has an empty triangle. In the paper the following better bounds are presented: \[ \binom{n}{2}-\mathcal{O}(n\log n)\leq ET(n)\leq \binom{n}{2}-(n-2+\lfloor\frac{n}{8}\rfloor). \] The lower bound is a construction of geometric graphs based on Horton sets. While the upper bound of \(\binom{n}{2}-(n-2)\) follows by recursive application of an easy observation, where a little more detailed work is needed to obtain the final bound.
0 references
geometric graphs
0 references
empty triangles
0 references
combinatorial geometry
0 references
extremal problem
0 references
Horton set
0 references