On the number of edges in geometric graphs without empty triangles (Q2637713): Difference between revisions

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.