Monthly Archives: August 2021

The Sylvester-Gallai Theorem

Posted on by
Reply

Guest contributor: Jim Geelen

In this post we consider some problems related to the following classical result (posed by Sylvester in 1893 and proved by Gallai in 1944).

Sylvester-Gallai Theorem: Given any finite set of points in the real plane, not all on a line, we can find a line in the plane that contains exactly two of them.

That is, in matroid-thoretic language, every simple, rank-$3$, real-representable matroid contains a $2$-point line. Geometers have considered a number of related problems, but there does not seem to have been much work on this in the matroid theory community. I’ve not thought about these questions much, and have not done a thorough literature review, but I’m just going to put the problems out there for discussion. I’ll start with a brief discussion about what is known for real-representable, complex-representable, and binary matroids.

In geometry, an ordinary line is a line with exactly two points. This has an obvious generalization to higher rank flats, however, the term “ordinary flat” is used to describe a different, less natural, generalization of ordinary lines, which we define later. So, following conventions in geometry, we will call a flat in a matroid elementary if it is an independent set.

Does every simple real-representable matroid with rank at lest $4$ contain an elementary plane? This was answered in the negative by Motzkin in 1951 who presented two counterexamples; the first being the direct sum of two lines. The second example is more subtle; take $5$ planes in $\mathbb R^3$ in general position; any three of the planes intersect in a point, and these 10 points give a counterexample.  These were thought to be the only examples, until 1971, when Bonnice and Kelly presented an infinite family. Later, Hansen added to the list of known counterexamples.

Problem 1: Classify the simple rank-$4$ real-representable matroids that do not have an elementary plane.

Given the list of known examples, that problem is likely to be quite challenging.

Geometers have a non-trivial generalization of the Sylvester-Gallai Theorem, given below. A flat $F$ of a matroid $M$ is ordinary if $M|F$ has a coloop. Thus, in a simple matroid, elementary lines and ordinary lines are the same thing.

Hansen’s Theorem: For each $r\ge 3$, every simple rank-$r$ real-representable matroid contains an ordinary hyperplane.

The definition of ordinary flats seems a bit contrived, but the result does have interesting consequences.

Corollary 2: Every simple rank-5 real-representable matroid has an elementary plane.

Proof: Suppose that $M$ is a simple rank $5$ real-representable matroid. By Hansen’s Theorem there is an ordinary hyperplane $H$ in $M$. By definition, $H=P\cup \{e\}$ for some plane $P$ and element $\{e\}$. By the Sylvester-Gallai Theorem, $P$ contains an elementary line $\{f,g\}$. Now $\{e,f,g\}$ is an elementary plane.$\Box$

Moreover, the same idea easily generalizes to higher-dimensions.

Corollary 3: For each $k\ge 2$ and $r\ge 2k-1$, if $M$ is a simple rank-$r$ real-representable matroid, then $M$ has an elementary rank-$k$ flat.

Since the direct-sum of $k-1$ triangles does not contain an elementary rank=$k$ flat, this bound is best possible.

Complex-representable matroids

It is easy to construct simple rank-$3$ matroids with no ordinary lines; projective planes and affine planes (over fields of size at least $3$) give examples. It is not as easy to come up with examples that are representable over the complex numbers, however, the ternary affine plane is complex representable. There are, in fact, infinitely many examples known in rank-$3$, but the list of known examples is believed to be complete. Increasing the rank to $4$ yields an ordinary line.

Theorem [Kelly, 1986]: Every simple complex-representable matroid with rank at least $4$ contains an ordinary line.

It is natural to wonder whether Corollary 3 extends to complex-representable matroids. I really like this conjecture, but it is hard to imaging that it is new.

Conjecture 4: For each positive integer $k$ there is an integer $R$, such that, if  $M$ is a simple complex-representable matroid with rank at least $R$, then $M$ contains an elementary rank-$k$ flat.

Binary matroids

I was led to these problems by results on binary matroids that I came across in Kazuhiro Nomoto’s Ph.D thesis. In particular, Peter Nelson and Kazuhiro Nomoto characterized the simple binary matroids with no elementary plane. Their theorem statement is not particularly complicated, so I will state it, but it is not directly relavent to any of the conjectures, so I will not go into any detail.

Theorem [Nelson, Nomoto]: A simple binary matroid $M$  has no elementary plane if and only if it can be obtained via lift-joins from:

  • the direct sums of two projective geometries,
  • even-plane matroids, and
  • complements of triangle-free binary matroids,

Here a matroid is even-plane if each of its planes have an even number of points; these matroids have an unexpected description as roots of quadtratic equations. This class is particularly interesting as it has unbounded critical number. You might want to look at the the paper for a definition of a lift-join of simple binary matroids $N_1$ and $N_2$, but here is a cryptic definition; it is the unique maximal simple binary matroid $M$ spanned by the direct sum of $N_1$ and $N_2$ such that $M/E(N_2)$ is loopless and simplifies to $N_1$.

Since this result is already quite complicated, it would be presumably very hard to characterize the simple binary matroids with no elementary flat of rank $4$. For other finite fields $\mathbb F$ and integers $k\ge 2$, one could try to classify the simple $\mathbb F$-representable matroids with no elementary rank-$k$ flat. The only other instance of this problem that looks approachable is:

Exercise 5: Characterize the simple ternary matroids with no elementary line.

Hint: If you consider a simple ternary matroid as a restriction of a ternary projective geometry then the matroid has an elementary line if and only if its complement does. Show that if there is no elementary line then the matroid and its complement cannot both be spanning.

Matroids in general

The class of matroids with no ordinary line looks extremely complicated, but it would be nice to have some general Ramsey-theoretic tools for addressing Sylvester-Gallai-type problems. For example:

Conjecture 6: For any integer $k\ge 1$ there is an integer $R$ such that if $M$ is a simple matroid with rank at least $R$ then there is a rank-$k$ flat in $M$ such that either $M|F$ has no ordinary lines, or every line in $M|F$ is ordinary.

I don’t know whether I particularly believe this conjecture; it may be the case that $R$ may also depend on the maximum line-length.

Claim: Conjecture 6 implies Conjecture 4.

Proof. Consider the smallest integer $k$ such that Conjecture 3 fails. By Hansen’s Theorem, $k\ge 3$. Consider a simple complex-representable matroid $M$ with huge rank but with no elementary rank-$k$ flats. If Conjecture 5 were true we could find a large-rank flat $F$ in which all of the lines are ordinary. Now, for any $e\in F$, by induction $(M|F)/e$ has a rank-$(k-1)$ elementary flat $F’$. Then $F’\cup\{e\}$ is an elementary rank-$k$ flat in $M$. $\Box$

I will say that a class $\mathcal M$ of matroids satisfies the $k$-Sylvester Property if every simple matroid in $\mathcal M$ with sufficiently large rank contains an elementary rank-$k$ flat.  Note that if $\mathcal M$ does not satisfy the $k$-Sylvester Property, then $\mathcal M$ doe not satisfy the $k’$-sylvester Property for any $k’\ge k$. Using the proof idea from the previous claim, Conjecture 6 also implies:

Conjecture 7:  If $\mathcal M$ is a minor-closed class of matroids that satisfies the $2$-Sylvester property, then $\mathcal M$ satisfies the $k’$-Sylvester property for all $k’\ge 2$.

The following weakening of Conjecture 6 would already imply Conjecture 7.

Conjecture 8: For any integer $k\ge 1$ there is an integer $R$ such that if $M$ is a simple matroid with rank at least $R$ then there is a rank-$k$ flat in $M$ such that either there is a point in $M|F$ that is only on ordinary lines, or no line in $M|F$ is ordinary.

Elementary planes in triangle-free matroids

If $M$ is a triangle-free matroid with no elementary plane, then, for each element $e$ of $M$, the matroid $M/ e$ is simple and has no ordinary line. So results about ordinary lines can be lifted to give results about triangle-free matroids with no ordinary plane. For example, the Sylvester-Gallai Theorem implies that:

Theorem 9: If $M$ is a simple, triangle-free real-representable matroid with rank at least $4$, then $M$ has an elementary plane.

This result is implied by Hansen’s Theorem, but the proof of Hansen’s Theorem is considerably harder.

The next result follows from Kelly’s Theorem.

Theorem10: If $M$ is a simple, triangle-free complex-representable matroid with rank at least $5$, then $M$ has an elementary plane.

Projective geometries are the only simple binary matroids with no ordinary lines. Affine geometries are the only triangle-free, binary, single-element coextensions of binary projective geometries. Therefore:

Theorem [Nelson, Nomoto]: The only simple, triangle-free binary matroids with no elementary plane are the binary affine geometries.

To borrow a nice turn-of-phrase from Joseph Kung, the following conjecture reflects my current state of ignorance.

Conjecture 11: For any finite field $\mathbb F$ with odd characteristic, if $M$ is a simple, triangle-free $\mathbb F$-representable matroid with sufficiently large rank, then $M$ has an elementary plane.

Something much stronger may well hold:

Conjecture 12: For any finite field $\mathbb F$ with odd characteristic and integer $k\ge 3$, if $M$ is a simple, triangle-free $\mathbb F$-representable matroid with sufficiently large rank, then $M$ has an elementary rank-$k$ flat.

Higher girth

A matroid is simple and triangle-free if and only if it has girth at least $4$. If $e$ is an element in a matroid $M$ with girth $g$ and with no elementary rank-$k$ flat, then $M/e$ has girth $\ge g-1$ and has no elementary flat of rank $k-1$. Again this gives us an inductive tool.

Lemma: Every binary matroid with girth $\ge 5$ and rank $\ge 5$ contains an elementary rank-4 flat.

Proof. It suffices to prove the result when the rank and girth are both equal to $5$. Consider a binary matroid $M$ with rank and girth both $5$. Suppose that $M$ has no elementary rank-$4$ flat. For any element $e$ of $M$, the matroid $M/e$ is a simple, rank-$4$ triangle-free binary matroid with no elementary plane; therefore $M/e$ is isomorphic to the binary affine cube AG$(3,2)$. The binary affine cube is also known as the rank-$4$ binary spike, which is self-dual. Therefore $M^*$ is the unique binary single-element extension of the binary affine cube, which is the rank-$4$ binary spike with tip. However, this contradicts the fact that $M$ has girth $5$. $\Box$

Now an easy induction gives:

Theorem 13: For each $k\ge 4$, if $M$ is a binary matroid with rank and girth both at least $k+1$, then $M$ has an elementary rank-$k$ flat.

In fact, we can keep the girth at $5$ if we increase the rank.

Theorem 14: For each $k\ge 4$, if $M$ is a binary matroid  girth at least $5$ and with sufficiently large rank, then $M$ has an elementary rank-$k$ flat.

Proof. Fix a basis $B$, and for each element $e$ outside $B$ let $C_e$ be the unique circuit in $B\cup \{e\}$. We think of $C_e-\{e\}$ as a “hyper-edge” on the vertex set $B$ and apply the hypergraph Ramsey Theorem to get a $k$-element set $I\subseteq B$ such that, for each $t\in\{1,\ldots,k\}$, either all or none of the $t$-element subsets of $I$ are hyper-edges. We may assume that $I$ is not an elementary flat and hence there exists $t\in\{1,\ldots,k\}$ such that all of the $t$-element sets are hyperedges. Then there are two hyperedges whose symmetric difference has size two and hence $M$ has a circuit of size $4$.$\Box$

While it seems a bit wild, maybe we don’t even need representability.

Conjecture 15: For each $k\ge 4$, if $M$ is a matroid  with girth at least $5$ and with sufficiently large rank, then $M$ has an elementary rank-$k$ flat.

If you are not struck by this conjecture, read it again.

While writing this I benefitted from discussions with Nick Brettell, Rutger Campbell, James Davies, Matt Kroeker, Peter Nelson, and Geoff Whittle.

References