Extremal theory for convex matchings in convex geometric graphs (Q1911768)

Let \(G_n\) denote a graph whose nodes are the vertices of a convex \(n\)-gon in the plane and whose edges are straight line segments joining some pairs of these vertices. Let \(E_k\) denote any set of \(k\) edges of \(G_n\) such that for each edge \(e\) of \(E_k\), the remaining edges of \(E_k\) all lie on one side of \(e\) (assuming that \(6 \leq 2k \leq n)\). The graph \(G_n\) is \(k\)-saturated if it contains no such set \(E_k\) of edges but loses this property if any new edge is added to \(G_n\). The authors determine the maximum and minimum number of edges such a \(k\)-saturated graph \(G_n\) can have and they characterize the extremal graph, among other things. These results are related to corresponding results on extremal graphs that contain no complete \(k\)-graphs as subgraphs.