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]

Example

The -point line (i.e., the rank 2 uniform matroid on elements, ) 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, by defining the lines of the matroid to be the triples of 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 must have at least 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 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.

gollark: Fun Things to Do With a CB Prize:- breed with random high-gen messy- breed with own children- randomly dump 2Gs in the AP or offer them on trades for low-value stuff- ND the 2Gs- give the 2Gs only to those who figure out the answer to a riddle
gollark: Well, at least ones on here.
gollark: Yes, there are viewbombers secretly watching our every message.
gollark: I kind of want a CB prize just to irritate people with what I do with its offspring.
gollark: That must be it, then.

References
  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: 44–50, doi:10.1007/BF01817744, MR 0265186.
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.