The number of extreme triples of a planar point set (Q1921337)

Let \(S\) be a set of \(n\) points in \(\mathbb{R}^2\). For a half-plane \(h\), \(S'=S\cap h\) is called a \(k\)-set of \(S\) where \(k=|S'|\). Let \(e_k(S)\) denote the number of \(k\)-sets realized by \(S\), and define \(e_k(n)=\max\{e_k(S):S\subseteq\mathbb{R}^2,|S|=n\}\) for \(1\leq k\leq n-1\). 2-sets and 3-sets are called extreme pairs and extreme triples respectively. It is known that \(e_2(n)=\lfloor 3n/2\rfloor\) for \(n\geq 4\), and that \(e_3(n)\geq\lfloor 11n/6\rfloor\) for \(n\geq 15\), \(n\neq 19\). This note establishes the upper bound \(e_3(n)\leq\lfloor 11n/6\rfloor+1\) for \(n\geq 10\). This bound is established in a more general setting where the straight lines which determine the half-planes used in the definition are replaced by pseudolines, topological lines for which every pair intersect exactly once at a crossing point. The proof, by induction, is a somewhat tedious case analysis which establishes that maximal configurations (with respect to the number of extreme triples) can be made smaller by utilizing a suite of reduction techniques. The techniques of this approach are also used to provide a new proof of the \(e_2(n)\) result.