Finite linear spaces

A finite linear space is a set $E$ of points together with a family $\mathcal{L}$ of lines with the property that

• every pair of points is on a line, and
• every line contains at least two points.

In matroidal terms, a finite linear space is a simple matroid of rank 3, given by its hyperplanes (unless all points are on a single line). We will drop the word “finite”, and simply talk about linear spaces instead.

How many lines must be in a linear space?

Let’s write $n = |E|$. As every pair of points defines a line, we immediately see that $|\mathcal{L}| \le \binom{n}{2}$. Equality holds when $\mathcal{L}$ is the family of all pairs in $E$; or equivalently, if $(E,\mathcal{L})$ is the rank-3 uniform matroid on $E$.

In $U_{3,n}$, all lines are as short as they can be. A more interesting question is: How many “long” lines can a linear space contain? Here, a line is long if it contains 3 or more points.

Proposition. A linear space on $n$ points contains at most $\frac{1}{3}\binom{n}{2}$ long lines.

Proof. Every pair of points is in at most one long line, and every long line contains at least three pairs of points. $\Box$

The proposition says that a simple rank-3 matroid on $n$ points has at most $\frac{1}{3}\binom{n}{2}$ long lines.

Equality holds if and only if each line contains exactly 3 points. In this case, $\mathcal{L}$ is the set of blocks of a Steiner triple system, and we necessarily have $n \equiv 1,3$ modulo 6.

In the other direction, we can ask: What is the smallest possible number of lines in a linear space? A reasonable guess is that this number is minimised when $\mathcal{L}$ consists one line containing all but one of the points, and $n-1$ two-point lines, each containing the remaining point of $E$. We know this as the matroid $U_{n-1,2} \oplus U_{1,1}$, but this linear space is also called a near-pencil.

• 

• 

Projective planes on $n$ points, when they exist, have $n$ lines as well. De Bruijn and Erdős showed that near-pencils and projective planes have the smallest number of lines among all linear spaces.

Theorem (De Bruijn–Erdős, 1948). A linear space on $n$ points, not all collinear, has at least $n$ lines. Equality holds if and only if the linear space is a near-pencil or a projective plane.

This translates to the following matroid version.

Theorem (De Bruijn–Erdős, matroid version). A simple rank-3 matroid $M$ on $n$ points has at least $n$ hyperplanes. Equality holds if and only if $M \cong U_{2,n-1} \oplus U_{1,1}$ or $M$ is a finite projective plane.

A slick proof due to Conway can be found in Jukna’s book Extremal Combinatorics. It was already noted by De Bruijn and Erdős that the Euclidean analogue of this theorem (i.e., when we assume that $M$ is real-representable) follows from the Sylvester–Gallai Theorem Jim Geelen discussed in a previous post.

Higher rank

Linear spaces can be generalised to higher dimensions. One such generalisation is known as a Hartmanis partition, which to the matroid theorist is probably better known as a paving matroid. A paving matroid is a matroid in which the only “interesting” flats are the hyperplanes: each flat of lower rank is an independent set (alternatively, each circuit has cardinality at least the rank of the matroid). For example, a matroid of rank 3 is paving if and only if it is simple, while the Vámos matroid is a paving matroid of rank 4.

The De Bruijn–Erdős Theorem is the base case of the following result.

Lemma. Let $3 \le r \le n$ and let $M$ be a paving matroid of rank $r$ on $n$ points. Then $M$ has at least $n$ hyperplanes.

Proof. For $r=3$, this is just the bound from the De Bruijn–Erdős Theorem. We proceed by induction on $r$. Suppose that the theorem holds for $r = s$, and let $M$ be a matroid of rank $s+1$. Let $e \in E(M)$. The hyperplanes of $M/e$ are in natural correspondence with the hyperplanes of $M$ that contain $e$. By induction, $M/e$ has at least $n-1$ hyperplanes, so $M$ has at least $n-1$ hyperplanes that contain $e$. Finally, as $e$ is not a loop, $M$ has at least one hyperplane that does not contain $e$. We conclude that $M$ has at least $n$ hyperplanes. $\Box$

It is not hard to construct rank-$r$ matroids with exactly $n$ hyperplanes—one example is $U_{2,n-r+2}\oplus U_{r-2,r-2}$. More generally, we can take any of the tight examples from the De Bruijn–Erdős Theorem on $n-r+3$ points and add $r-3$ coloops. However, the matroids obtained in this way are far from paving.

Question. For $r \ge 4$, is the bound on the number of hyperplanes in the previous lemma tight?

I suspect the answer is “no”. If I had to guess the correct number, it would be $1+\binom{n-1}{r-2}$, which is the number of hyperplanes of $U_{r-1,n-1}\oplus U_{1,1}$.

We now drop the assumption that $M$ is paving and write $f_k(r,n)$ for the minimal number of rank-$k$ flats in a simple matroid of rank $r$ on $n$ points. The De Bruijn–Erdős Theorem asserts that $f_2(3,n) = n$.

The following lemma shows that $f_k(r,n)$ is increasing in $r$. The truncation of a matroid is obtained by removing the hyperplanes from its lattice of flats; this operation decreases the rank of the matroid by 1.

Lemma. For all $2 \le k < r-1 < n$ we have $f_k(r,n) \ge f_k(r-1,n)$.

Proof. Let $M$ be a matroid of rank $r$ on $n$ points with $f_k(r,n)$ flats of rank $k$. The truncation of $M$ has rank $r-1$ and $f_k(r,n)$ flats of rank $k$. $\Box$

Let me conclude by asking about a higher-dimensional analogue of the De Bruijn–Erdős Theorem.

Question. For $2 \le k < r \le n$, what is $f_k(r,n)$?