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]

Examples

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]

History

Sylvester matroids were studied and named by Murty (1969) after James Joseph Sylvester, because they violate the Sylvester–Gallai theorem (for points and lines in the Euclidean plane, or in higher-dimensional Euclidean spaces) that for every finite set of points there is a line containing only two of the points.

References

^ ^a ^b Murty, U. S. R. (1969), "Sylvester matroids", Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), New York: Academic Press, pp. 283–286, MR 0255432.
^ Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 297, ISBN 9780486474397.
^ Murty, U. S. R. (1970), "Matroids with Sylvester property", Aequationes Mathematicae, 4 (1–2): 44–50, doi:10.1007/BF01817744, MR 0265186, S2CID 189832452.
^ Bryant, V. W.; Dawson, J. E.; Perfect, Hazel (1978), "Hereditary circuit spaces", Compositio Mathematica, 37 (3): 339–351, MR 0511749.
^ Ziegler, Günter M. (1991), "Some minimal non-orientable matroids of rank three", Geometriae Dedicata, 38 (3): 365–371, doi:10.1007/BF00181199, MR 1112674, S2CID 14993704.

[m69-1] Murty, U. S. R. (1969), "Sylvester matroids", Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), New York: Academic Press, pp. 283–286, MR 0255432.

[2] Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 297, ISBN 9780486474397.

[3] Murty, U. S. R. (1970), "Matroids with Sylvester property", Aequationes Mathematicae, 4 (1–2): 44–50, doi:10.1007/BF01817744, MR 0265186, S2CID 189832452.

[4] Bryant, V. W.; Dawson, J. E.; Perfect, Hazel (1978), "Hereditary circuit spaces", Compositio Mathematica, 37 (3): 339–351, MR 0511749.

[5] Ziegler, Günter M. (1991), "Some minimal non-orientable matroids of rank three", Geometriae Dedicata, 38 (3): 365–371, doi:10.1007/BF00181199, MR 1112674, S2CID 14993704.

[1]

[2]

[3]

[4]

[5]