# Independent Hyperplanes in Oriented Paving Matroids

Lamar Chidiac  Winfried Hochstättler

###### Abstract

In 1993, Csima and Sawyer [3] proved that in a non-pencil arrangement of n
pseudolines, there are at least $\frac{6}{13}n$ simple points of intersection.
Since pseudoline arrangements are the topological representations of
reorientation classes of oriented matroids of rank $3$, in this paper, we will
use this result to prove by induction that an oriented paving matroid of rank
$r\geq 3$ on $n$ elements, where $n\geq 5+r$, has at least
$\frac{12}{13(r-1)}\binom{n}{r-2}$ independent hyperplanes, yielding a new
necessary condition for a paving matroid to be orientable.

Fakultät für Mathematik und Informatik,
FernUniversität in Hagen, Germany,
<EMAIL_ADDRESS>

##  1 Introduction

In 1893 Sylvester asked in [18] the following question: “Prove that it is not
possible to arrange any finite number of real points so that a right line
through every two of them shall pass through a third, unless they all lie in
the same right line.” This question remained unsolved for almost 40 years,
until it was independently raised by Erdös and solved shortly after by Gallai
in 1933 [7, 8, 6] and later on several other proofs have been found (for
reference [16], p.451 and [2], p. 65).

In other words, the Sylvester-Gallai theorem states that given a set of non-
collinear points in the Euclidean plane, we can always find at least one line
that has exactly two of the given points, we call it an ordinary line. A
generalization of this theorem to higher dimension is not always true, i.e.
given a finite set of points in a d-dimensional Euclidean space which is not
contained in a hyperplane, we cannot always find a hyperplane containing
exactly d of the given points, which we call an independent hyperplane. A
counterexample would be a set of 6 points, 3 on each of two skew lines as seen
in Figure 1 below; there is no hyperplane spanned by these points that has
exactly 3 of them. This counterexample is by Hansen [11] and another one is
the Desargues configuration in 3-space [16, p. 452].

•••••• Figure 1: An illustration of Hansen’s construction [11]

Looking into Hansen’s counterexample we notice that the main issue lies in the
3-point lines, and we can actually forbid this by considering a more specific
type of point configuration. We consider oriented paving matroids which we
will define later. In fact, realizable simple oriented paving matroids of rank
4 are exactly the point configurations in three space that have no three point
lines. By considering this type of matroids we can go further with the
generalization and not only prove the existence of an independent hyperplane
but also examine how many do we have. To do so we will have to go back and
start with the 2-dimensional space.

Sylvester-Gallai’s theorem can surely be dualized to the projective plane,
where the theorem will be equivalent to the following: For every finite set of
lines, not all going through one point (non-pencil arrangement), then among
all the intersection points of these lines, at least one is incident with
exactly two of the lines. We call it a simple point.

After proving the existence of at least one simple point, Dirac turned to the
question of how many. He [5] proved that there are at least 3 simple points in
an arrangements of more than 2 lines and conjectured that there are at least
n/2 simple points in an arrangement of n lines. This is a long-standing
conjecture which has been known as the Dirac-Motzkin conjecture. Apparently
neither author formally conjectures this in print, but Dirac [5] states twice
that its truth is ”likely”. Motzkin [16] does not seem to mention it at all.
This conjecture was and still is a motivation for a lot of mathematicians to
work on a lower bound for the number of simple points in line arrangements but
very few results are known since then, the latest was Tao and Green’s result
in 2013 [10] where they proved Dirac’s conjecture when n is sufficiently
large. The conjecture however remains open in general.

A careful consideration of the proofs of most of the results for line
arrangements reveals that the straightening of the lines which form the
arrangements plays only a very limited role. This leads naturally to the idea
of investigating arrangements of more general types; arrangements of
pseudolines.

######  Definition 1.

An arrangement of pseudolines is a finite collection of simple curves (no self
intersection) in the real projective plane satisfying the following two
properties:

  1. 1.

any two curves intersect in exactly one point, where they cross.

  2. 2.

the intersection of all curves is empty.

As in line arrangements, a simple point in a pseudoline arrangement is the
point formed by the intersection of exactly 2 pseudolines (curves). In [3],
simple points are referred to as ordinary points.

In the following, we present our main result that concerns a lower bound for
the number of independent hyperplanes in an oriented paving matroid. In
Section 2, we show an application to this result and then give its proof in
Section 3. Before going any further, let’s see the main connection between
oriented matroids and pseudoline arrangements and the main motivation behind
paving matroids.

In this work we consider matroids to be pairs $M=(E,\mathcal{I})$ where $E$ is
a finite set and $\mathcal{I}$ is the collection of independent sets in $M$.
We denote by $M/e$ the matroid we get when we contract an element $e$ in $M$,
and $M\backslash e$ the matroid we get when we delete an element $e$ in $M$.

We assume basic familiarity with matroid theory and oriented matroids. The
standard references are [17, 1].

######  Definition 2.

Let $M$ be a matroid of rank $r$ and $H$ a hyperplane. We say that $H$ is

  * •

simple, if there exists $e\in H$ such that $H\backslash\\{e\\}$ is a flat.

  * •

independent if it has exactly $r-1$ elements i.e. if it is simple for every
element $e\in H$.

  * •

multiple if it is not simple.

After Hansen’s counterexample for the natural generalization of Sylvester’s
theorem to higher dimension, another generalization was proven by him in [11]
where he proved that any real point configuration of any dimension has a
simple hyperplane but not necessarily an independent one. Later on Murty [14]
conjectured that Hansen’s theorem is also true for oriented matroids i.e. any
simple oriented matroid (matroid without loops or parallels) has a simple
hyperplane.

As mentioned earlier, the main problem with Hansen’s counterexample is that
the 6 point configuration does not correspond to a paving matroid since we
have three points lying on the same line.

######  Definition 3.

A uniform matroid with a ground set $E$ of size $n$ and rank $r$ is a matroid
where every subset of $E$ of size $r$ is a basis. A paving matroid is a
matroid in which every circuit has size either $r$ or $r+1$, where $r$ is the
rank of the matroid. In a point configuration, this means that no $r-1$ points
lie on a same flat of co-dimension 2.

Note that paving matroids are those matroids which are uniform or only
slightly deviate from being uniform. Mayhew et al. [15] conjecture that almost
all matroids are paving. This is mainly why we find paving matroids to be
interesting specially since in rank 3, all simple matroids are paving. The
following is immediate:

######  Proposition 1.

The class of paving matroid is closed under minors.

Oriented matroids and pseudoline arrangements are strongly connected by the
topological representation theorem.

######  Theorem 1 (The Topological Representation Theorem [9, 12]).

Any reorientation class of a rank-3 oriented matroid has a representation as a
pseudoline arrangement.

In this representation, the pseudolines in the pseudoline arrangement are the
elements of the oriented matroid. Their intersection points are the
hyperplanes of the matroids and their simple points of intersection are
exactly the independent hyperplanes in the oriented matroid. Therefore,
counting simple points in a pseudoline arrangement is actually counting
independent hyperplanes in the oriented matroid.

Only two main results on the lower bound of simple points in line arrangement
were found after Dirac’s conjecture in 1951. The first was by Kelly and Moser
in 1958 [13], where they proved that we have at least 3n/7 simple points in an
arrangement of n lines, with equality occurring in the Kelly-Moser
configuration shown in Figure 2, and the second was by Csima and Sawyer in
1993, [3] where they improved Kelly and Moser’s bound to 6n/13 with of course
the Kelly-Moser configuration being the only exception. In the same paper,
Csima and Sawyer indicated that their proof easily extends to arrangement of
pseudolines. This is why we were able to use their result to prove our main
result concerning a lower bound for independent hyperplanes in oriented paving
matroids.

Figure 2: The Kelly-Moser configuration [13].

######  Theorem 2.

An oriented paving matroid $M$ of rank $r\geq 3$, on n elements, where $n\geq
5+r$, has at least

$f(n,r)=\dfrac{12}{13(r-1)}\,\,\binom{n}{r-2}$

independent hyperplanes.

The proof can be found in Section 3.

##  2 Application of Theorem 2

We apply Theorem 2 to give a short proof that the Matroid $AG(3,2)^{\prime}$
is not orientable. The matroid $AG(3,2)^{\prime}$ shown in Figure 3, is the
unique relaxation of the binary affine cube AG(3,2). It’s an 8-element matroid
of rank 4 where the 4 point planes are the six faces of the cube, the six
diagonals such as {1,2,7,8}, and one twisted plane {1,8,3,6}.

41235678••••••••• Figure 3: An illustration of the non-orientable simple
paving matroid $AG(3,2)^{\prime}$. (Check [17] page 508)

$AG(3,2)^{\prime}$ is a simple paving matroid of rank 4. By our theorem, in
order for $AG(3,2)^{\prime}$ to be orientable, it should have at least

$f(8,4)=\dfrac{12}{13\cdot 3}\,\,\binom{8}{2}=\dfrac{336}{39}\cong 8.6$

independent hyperplanes. The independent hyperplanes in this matroid are the
sets of 3 elements that do not lie on a common 4-point plane. After looking at
the figure we notice that there are only 4 independent hyperplanes, namely:
{2,4,5}, {2,4,7}, {5,7,2} and {5,7,4}. Therefore, by Theorem 2,
$AG(3,2)^{\prime}$ is not orientable. This is already known by da Silva in
[4], where she actually proves a more general and stronger result, but by a
more complicated argument.

##  3 Proof of Theorem 2

We proceed by induction on $r\geq 3$.

By the Topological Representation Theorem 1, a rank-3 oriented matroid has a
representation as a pseudoline arrangement in the projective plane. By Csima
and Sawyer [3], except for the Kelly-Moser configuration, a pseudoline
arrangement has a least $6n/13$ simple points. Since $n\geq 5+r$ the Kelly-
Moser configuration is excluded. In matroid terms, this corresponds to $6n/13$
independent hyperplanes in a rank $3$ oriented matroid founding our induction.

Now assume $r>3$. We fix an element $e\in E$. By Proposition 1, the
contraction $M/e$ is paving and has at least 5+(r-1) elements, so by
induction, $M/e$ has at least

$f(n-1,r-1)=\dfrac{12}{13(r-2)}\,\,\binom{n-1}{r-3}$

independent hyperplanes.

Now any independent hyperplane in $M/e$ can be extended by $e$ to an
independent hyperplane in $M$. To prove this, we take an independent
hyperplane $H$ in $M/e$ and prove that $H\cup e$ is an independent hyperplane
in $M$.

We have that $r(H)=r-2$, thus $r(H\cup e)=r-1=|H\cup e|$. Therefore $H\cup e$
is independent. It is also a flat, because if it wasn’t i.e. if there exists
an element $x\in\operatorname{cl}(H\cup e)\backslash(H\cup e)$ then
$x\in\operatorname{cl}_{M/e}(H)\backslash H$ contradicting, $H$ being closed
in $M/e$. Therefore $H\cup e$ is an independent flat of rank $r-1$, thus an
independent hyperplane in $M$.

Since each of the $f(n-1,r-1)$ independent hyperplanes in $M/e$ can be
extended by $e$ to obtain an independent hyperplane in $M$ and since this is
the case for any element $e$ of the matroid, each of these independent
hyperplanes will be counted $r-1$ times, and so $M$ has at least

$\frac{n}{r-1}f(n-1,r-1)=\dfrac{12}{13(r-1)}\,\,\binom{n}{r-2}=f(n,r)$

independent hyperplanes. This concludes the proof of Theorem 2.

##  4 Discussion

In the rank three case all simple matroids are paving, thus being paving is a
restriction only in rank at least four. While in the pseudoline case the bound
is known to be almost tight [3], one might expect, that due to the simplicity
of the proof our bound should be quite weak for higher dimension. But
considering $n-1$ points in general position in $\mathbb{R}^{d-1}$ and an
extra point increasing the dimension, this configuration yields a paving
matroid of rank $d+1$ with one multiple hyperplane and
$\binom{n-1}{d-1}=\binom{n-1}{r-2}$ independent ones. Note, that in this
example all but one hyerplane are independent. It still seems possible, that
always at least a linear fraction of the hyperplanes in rank at least $4$ is
independent.

As we have seen, paving matroids are closed under minors. But they are not
closed under taking duals. A paving matroid where the dual is paving as well
is called sparse paving. It is easy to see that a paving matroid is sparse
paving if for any two circuits $C_{1},C_{2}$ such that $|C_{1}|=|C_{2}|=r$ we
must have $|C_{1}\cap C_{2}|\leq r-2$.

One can be interested in the following two problems:

######  Problem 1.

Is there a class of sparse paving matroids of rank $4$ with only a subcubic
number of independent hyperplanes?

Finally, coming back to the simple hyperplanes we would be interested in the
following

######  Problem 2.

Does any paving matroid of rank at least $4$ always have $r-2$ points which
belong to at least as many simple as multiple hyperplanes?

Note that in rank 3 the matroid of $K_{4}$ is a counterexample to the above.

### Acknowledgment

The authors would like to thank Manfred Scheucher for his collaboration and
efforts which helped to enhance the presentation of the results.

## References

  * [1] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler.  Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, second edition, 1999.
  * [2] H. S. M. Coxeter.  Introduction to geometry.  John Wiley & Sons, Inc., New York-London, 1961.
  * [3] J. Csima and E. T. Sawyer.  There exist $6n/13$ ordinary points.  Discrete Comput. Geom., 9(2):187–202, 1993.
  * [4] I.P.F. da Silva.  Orientability of cubes and las vergnas cube conjecture.  preprint, 2006.
  * [5] G. A. Dirac.  Collinearity properties of sets of points.  Quart. J. Math. Oxford Ser. (2), 2:221–227, 1951.
  * [6] P. Erdős.  Personal reminiscences and remarks on the mathematical work of Tibor Gallai.  Combinatorica, 2(3):207–212, 1982.
  * [7] P. Erdős, Richard Bellman, H. S. Wall, James Singer, and V. Thébault.  Problems and Solutions: Advanced Problems: Problems for Solution: 4065-4069.  Amer. Math. Monthly, 50(1):65–66, 1943.
  * [8] P. Erdős and Robert Steinberg.  Problems and Solutions: Advanced Problems: Solutions: 4065.  Amer. Math. Monthly, 51(3):169–171, 1944.
  * [9] Jon Folkman and Jim Lawrence.  Oriented matroids.  J. Combin. Theory Ser. B, 25(2):199–236, 1978.
  * [10] Ben Green and Terence Tao.  On sets defining few ordinary lines.  Discrete Comput. Geom., 50(2):409–468, 2013.
  * [11] Sten Hansen.  A generalization of a theorem of Sylvester on the lines determined by a finite point set.  Math. Scand., 16:175–180, 1965.
  * [12] W. Hochstättler.  Oriented matroids from wild spheres.  In Proceedings of the Colloguy “Discrete Optimization—Structure and Stability of Dynamical Systems” (Cologne, 2000), volume 7, pages 16–26, 2002.  Special Issue.
  * [13] L. M. Kelly and W. O. J. Moser.  On the number of ordinary lines determined by $n$ points.  Canadian J. Math., 10:210–219, 1958.
  * [14] Arnaldo Mandel.  Topology of oriented matroids.  ProQuest LLC, Ann Arbor, MI, 1982.  Thesis (Ph.D.)–University of Waterloo (Canada).
  * [15] Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle.  On the asymptotic proportion of connected matroids.  European J. Combin., 32(6):882–890, 2011.
  * [16] Th. Motzkin.  The lines and planes connecting the points of a finite set.  Trans. Amer. Math. Soc., 70:451–464, 1951.
  * [17] James Oxley.  Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [18] James Joseph Sylvester.  Mathematical question 11851.  Educational Times, 59(98):256, 1893.