# criterion for a near-linear space being a linear space

Suppose $\mathscr{S}$ is near-linear space with $v$ points and $b$ lines, and $s_{i}$ is the number of points in the $i$th line, for $i=1,\ldots,b$. Then

 $\sum_{i=1}^{b}s_{i}(s_{i}-1)\leq v(v-1),$

and equality holds if and only if $\mathscr{S}$ is a linear space.

## Proof

Let $N$ be the number of ordered pairs of points that are joined by a line. Clearly $N$ can be no more than $v(v-1)$, and $N=v(v-1)$ if and only if every pair of points are joined by a line. Since two points in a near-linear space are on at most one line, we can label each pair by the line to which the two points belong to. We thus have a partition of the $N$ pairs into $b$ groups, and each group is associated with a distinct line. The group corresponding to the line consisting of $s_{i}$ points contributes $s_{i}(s_{i}-1)$ to the total sum. Therefore

 $\sum_{i=1}^{b}s_{i}(s_{i}-1)=N\leq v(v-1).$
Title criterion for a near-linear space being a linear space CriterionForANearlinearSpaceBeingALinearSpace 2013-03-22 14:32:47 2013-03-22 14:32:47 kshum (5987) kshum (5987) 9 kshum (5987) Theorem msc 05B25