On the number of edges in geometric graphs without empty triangles (Q2637713)

From MaRDI portal
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
    0 references
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    geometric graphs
    0 references
    empty triangles
    0 references
    combinatorial geometry
    0 references
    extremal problem
    0 references
    Horton set
    0 references

    Identifiers