Problem 1718

The maximum is $\binom{n}{2} + 1$, achieved for instance by a convex $n$-gon: besides the trivial partition (in which all of the points are in one part), each linear partition occurs by drawing a line crossing a unique pair of edges.

\textbf{First solution:} We will prove that $L_S = \binom{n}{2} + 1$ in any configuration in which no two of the lines joining points of $S$ are parallel. This suffices to imply the maximum in all configurations: given a maximal configuration, we may vary the points slightly to get another maximal configuration in which our hypothesis is satisfied. For convenience, we assume $n \geq 3$, as the cases $n=1,2$ are easy.

Let $P$ be the line at infinity in the real projective plane; i.e., $P$ is the set of possible directions of lines in the plane, viewed as a circle. Remove the directions corresponding to lines through two points of $S$; this leaves behind $\binom{n}{2}$ intervals.

Given a direction in one of the intervals, consider the set of linear partitions achieved by lines parallel to that direction. Note that the resulting collection of partitions depends only on the interval. Then note that the collections associated to adjacent intervals differ in only one element.

The trivial partition that puts all of $S$ on one side is in every such collection. We now observe that for any other linear partition $\{A,B\}$, the set of intervals to which $\{A,B\}$ is: \begin{enumerate} \item[(a)] a consecutive block of intervals, but \item[(b)] not all of them. \end{enumerate} For (a), note that if $\ell_1, \ell_2$ are nonparallel lines achieving the same partition, then we can rotate around their point of intersection to achieve all of the intermediate directions on one side or the other. For (b), the case $n=3$ is evident; to reduce the general case to this case, take points $P,Q,R$ such that $P$ lies on the opposite side of the partition from $Q$ and $R$.

It follows now that that each linear partition, except for the trivial one, occurs in exactly one place as the partition associated to some interval but not to its immediate counterclockwise neighbor. In other words, the number of linear partitions is one more than the number of intervals, or $\binom{n}{2} + 1$ as desired.

\textbf{Second solution:} We prove the upper bound by induction on $n$. Choose a point $P$ in the convex hull of $S$. Put $S' = S \setminus \{P\}$; by the induction hypothesis, there are at most $\binom{n-1}{2} + 1$ linear partitions of $S'$. Note that each linear partition of $S$ restricts to a linear partition of $S'$. Moreover, if two linear partitions of $S$ restrict to the same linear partition of $S'$, then that partition of $S'$ is achieved by a line through $P$.

By rotating a line through $P$, we see that there are at most $n-1$ partitions of $S'$ achieved by lines through $P$: namely, the partition only changes when the rotating line passes through one of the points of $S$. This yields the desired result.

\textbf{Third solution:} (by Noam Elkies) We enlarge the plane to a projective plane by adding a line at infinity, then apply the polar duality map centered at one of the points $O \in S$. This turns the rest of $S$ into a set $S'$ of $n-1$ lines in the dual projective plane. Let $O'$ be the point in the dual plane corresponding to the original line at infinity; it does not lie on any of the lines in $S'$.

Let $\ell$ be a line in the original plane, corresponding to a point $P$ in the dual plane. If we form the linear partition induced by $\ell$, then the points of $S \setminus \{O\}$ lying in the same part as $O$ correspond to the lines of $S'$ which cross the segment $O'P$. If we consider the dual affine plane as being divided into regions by the lines of $S'$, then the lines of $S'$ crossing the segment $O'P$ are determined by which region $P$ lies in.

Thus our original maximum is equal to the maximum number of regions into which $n-1$ lines divide an affine plane. By induction on $n$, this number is easily seen to be $1 + \binom{n}{2}$.

\textbf{Fourth solution:} (by Florian Herzig) Say that an \emph{$S$-line} is a line that intersects $S$ in at least two points. We claim that the nontrivial linear partitions of $S$ are in natural bijection with pairs $(\ell, \{X,Y\})$ consisting of an $S$-line $\ell$ and a nontrivial linear partition $\{X,Y\}$ of $\ell \cap S$. Since an $S$-line $\ell$ admits precisely $|\ell\cap S|-1 \le \binom{|\ell \cap S|}{2}$ nontrivial linear partitions, the claim implies that $L_S \le \binom n2 + 1$ with equality iff no three points of $S$ are collinear.

Let $P$ be the line at infinity in the real projective plane. Given any nontrivial linear partition $\{A,B\}$ of $S$, the set of lines inducing this partition is a proper, open, connected subset $I$ of $P$. (It is proper because it has to omit directions of $S$-lines that pass through both parts of the partition and open because we can vary the separating line. It is connected because if we have two such lines that aren't parallel, we can rotate through their point of intersection to get all intermediate directions.) Among all $S$-lines that intersect both $A$ and $B$ choose a line $\ell$ whose direction is minimal (in the clockwise direction) with respect to the interval $I$; also, pick an arbitrary line $\ell'$ that induces $\{A,B\}$. By rotating $\ell'$ clockwise to $\ell$ about their point of intersection, we see that the direction of $\ell$ is the least upper bound of $I$. (We can't hit any point of $S$ during the rotation because of the minimality property of $\ell$.) The line $\ell$ is in fact unique because if the (parallel) lines $pq$ and $rs$ are two choices for $\ell$, with $p$, $q \in A$; $r$, $s \in B$, then one of the diagonals $ps$, $qr$ would contradict the minimality property of $\ell$. To define the above bijection we send $\{A,B\}$ to $(\ell, \{A \cap \ell, B \cap \ell\})$.

Conversely, suppose that we are given an $S$-line $\ell$ and a nontrivial linear partition $\{X,Y\}$ of $\ell \cap S$. Pick any point $p \in \ell$ that induces the partition $\{X,Y\}$. If we rotate the line $\ell$ about $p$ in the counterclockwise direction by a sufficiently small amount, we get a nontrivial linear partitition of $S$ that is independent of all choices. (It is obtained from the partition of $S-\ell$ induced by $\ell$ by adjoining $X$ to one part and $Y$ to the other.) This defines a map in the other direction.

By construction these two maps are inverse to each other, and this proves the claim.

\textbf{Remark:} Given a finite set $S$ of points in $\mathbb{R}^n$, a \emph{non-Radon partition} of $S$ is a pair $(A,B)$ of complementary subsets that can be separated by a hyperplane. \emph{Radon's theorem} states that if $\#S\geq n+2$, then not every $(A,B)$ is a non-Radon partition. The result of this problem has been greatly extended, especially within the context of matroid theory and oriented matroid theory. Richard Stanley suggests the following references: T. H. Brylawski, A combinatorial perspective on the Radon convexity theorem, \emph{Geom. Ded.} \textbf{5} (1976), 459-466; and T. Zaslavsky, Extremal arrangements of hyperplanes, \emph{Ann. N. Y. Acad. Sci.} \textbf{440} (1985), 69-87.