criterion for a near-linear space being a linear space

Theorem

Suppose $𝒮$ 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,\mathrm{\dots },b$. Then

$$\sum _{i=1}^b{s}_i(s_i-1)\le v(v-1),$$

and equality holds if and only if $𝒮$ 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\le v(v-1).$$

Title	criterion for a near-linear space being a linear space
Canonical name	CriterionForANearlinearSpaceBeingALinearSpace
Date of creation	2013-03-22 14:32:47
Last modified on	2013-03-22 14:32:47
Owner	kshum (5987)
Last modified by	kshum (5987)
Numerical id	9
Author	kshum (5987)
Entry type	Theorem
Classification	msc 05B25