- \n
- every pair of points is on a line, and<\/li>\n
- every line contains at least two points.<\/li>\n<\/ul>\n
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.<\/p>\n\n\n\n
How many lines must be in a linear space?<\/h2>\n\n\n\n
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$.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Proposition.<\/strong> A linear space on $n$ points contains at most $\\frac{1}{3}\\binom{n}{2}$ long lines.<\/p>\n\n\n\n
Proof.<\/em> Every pair of points is in at most one long line, and every long line contains at least three pairs of points. $\\Box$<\/p>\n\n\n\n
The proposition says that a simple rank-3 matroid on $n$ points has at most $\\frac{1}{3}\\binom{n}{2}$ long lines.<\/p>\n\n\n\n
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<\/a>, and we necessarily have $n \\equiv 1,3$ modulo 6.<\/p>\n\n\n\n
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<\/em>.<\/p>\n\n\n\n
![\"\"](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2021\/11\/near-pencil-2-1024x792.png\")
<\/a>A near-pencil on 7 points has 7 lines.<\/figcaption><\/figure><\/li> ![\"\"](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2021\/11\/far-pencil.jpg\")
<\/a>A pencil, just out of reach.<\/figcaption><\/figure><\/li><\/ul><\/figure>\n\n\n\n Projective planes<\/a>\u00a0on $n$ points, when they exist, have $n$ lines as well. De Bruijn and Erd\u0151s showed that near-pencils and projective planes have the smallest number of lines among all linear spaces.<\/p>\n\n\n\n
Theorem (De Bruijn\u2013Erd\u0151s, 1948<\/a>).<\/strong> 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.<\/p>\n\n\n\n
This translates to the following matroid version.<\/p>\n\n\n\n
Theorem (De Bruijn\u2013Erd\u0151s, matroid version).<\/strong> 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.<\/p>\n\n\n\n
A slick proof due to Conway can be found in Jukna’s book\u00a0Extremal Combinatorics<\/a>. It was already noted by De Bruijn and Erd\u0151s that the Euclidean analogue of this theorem (i.e., when we assume that\u00a0$M$\u00a0is real-representable) follows from the Sylvester\u2013Gallai Theorem Jim Geelen discussed in a\u00a0previous post<\/a>.<\/p>\n\n\n\n
Higher rank<\/h2>\n\n\n\n
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\u00a0paving matroid<\/a>. 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\u00a0V\u00e1mos matroid<\/a>\u00a0is a paving matroid of rank 4.<\/p>\n\n\n\n
The De Bruijn\u2013Erd\u0151s Theorem is the base case of the following result.<\/p>\n\n\n\n
Lemma.<\/strong> 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.<\/p>\n\n\n\n
Proof.<\/em> For $r=3$, this is just the bound from the De Bruijn\u2013Erd\u0151s 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$<\/p>\n\n\n\n
It is not hard to construct rank-$r$ matroids with exactly $n$ hyperplanes\u2014one 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\u2013Erd\u0151s Theorem on $n-r+3$ points and add $r-3$ coloops. However, the matroids obtained in this way are far from paving.<\/p>\n\n\n\n
Question.<\/strong> For $r \\ge 4$, is the bound on the number of hyperplanes in the previous lemma tight?<\/p>\n\n\n\n
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}$.<\/p>\n\n\n\n
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\u2013Erd\u0151s Theorem asserts that $f_2(3,n) = n$.<\/p>\n\n\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.<\/p>\n\n\n\n
Lemma.<\/strong> For all $2 \\le k < r-1 < n$ we have $f_k(r,n) \\ge f_k(r-1,n)$.<\/p>\n\n\n\n
Proof.<\/em> 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$<\/p>\n\n\n\n
Let me conclude by asking about a higher-dimensional analogue of the De Bruijn\u2013Erd\u0151s Theorem.<\/p>\n\n\n\n
Question.<\/strong> For $2 \\le k < r \\le n$, what is $f_k(r,n)$?<\/p>\n","protected":false},"excerpt":{"rendered":"
Finite linear spaces A\u00a0finite 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 … Continue reading