Sylvester matroid

In matroid theory, a Sylvester matroid is a matroid in which every pair of elements belongs to a three-element circuit (a triangle) of the matroid.^[1]^[2]

In the $n$ -point line (i.e., the rank 2 uniform matroid on $n$ elements, $U{}_{n}^{2}$ ) a set of elements is independent if and only if it contains at most two elements. It is a Sylvester matroid because every pair of elements is a basis and every triple is a circuit.

A Sylvester matroid of rank three may be formed from any Steiner triple system, a system of triples of elements such that each pair of elements is included in exactly one triple, by defining the lines of the matroid to be the triples of the system. The independent sets of the matroid are the subsets of at most two elements, and the sets of three elements that are not triples in the system.

Sylvester matroids of rank three may also be formed from Sylvester–Gallai configurations, configurations of points and lines (in non-Euclidean spaces) with no two-point line. For example, the Fano plane and the Hesse configuration give rise to Sylvester matroids with seven and nine elements respectively, and may be interpreted either as Steiner triple systems or as Sylvester–Gallai configurations.

Properties

A Sylvester matroid with rank $r$ must have at least $2^{r}-1$ elements; this bound is tight only for the projective spaces over GF(2), of which the Fano plane is an example.^[3]

In a Sylvester matroid, every independent set can be augmented by one more element to form a circuit of the matroid.^[1]^[4]

Sylvester matroids (other than $U{}_{n}^{2}$ ) cannot be represented over the real numbers (this is the Sylvester–Gallai theorem), nor can they be oriented.^[5]

Sylvester matroid

Properties

History

References

Related Articles