In mathematics, Coxeter matroids are generalization of

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

s depending on a choice of a

Coxeter group In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean refl ...

''W'' and a

parabolic subgroup In the theory of algebraic groups, a Borel subgroup of an algebraic group ''G'' is a maximal Zariski closed and connected solvable algebraic subgroup. For example, in the general linear group ''GLn'' (''n x n'' invertible matrices), the subgroup ...

''P''. Ordinary matroids correspond to the case when ''P'' is a maximal parabolic subgroup of a symmetric group ''W''. They were introduced by , who named them after

H. S. M. Coxeter Harold Scott MacDonald "Donald" Coxeter, (9 February 1907 – 31 March 2003) was a British and later also Canadian geometer. He is regarded as one of the greatest geometers of the 20th century. Biography Coxeter was born in Kensington t ...

. give a detailed account of Coxeter matroids.

Definition

Suppose that ''W'' is a Coxeter group, generated by a set ''S'' of involutions, and ''P'' is a parabolic subgroup (the subgroup generated by some subset of ''S''). A Coxeter matroid is a subset ''M'' of ''W''/''P'' that for every ''w'' in ''W'', ''M'' contains a unique minimal element with respect to the ''w''-

Bruhat order In mathematics, the Bruhat order (also called strong order or strong Bruhat order or Chevalley order or Bruhat–Chevalley order or Chevalley–Bruhat order) is a partial order on the elements of a Coxeter group, that corresponds to the inclusion o ...

Relation to matroids

Suppose that the Coxeter group ''W'' is the

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...

''S''_''n'' and ''P'' is the parabolic subgroup ''S''_''k''×''S''_{''n''–''k''}. Then ''W''/''P'' can be identified with the ''k''-element subsets of the ''n''-element set and the elements ''w'' of ''W'' correspond to the linear orderings of this set. A Coxeter matroid consists of ''k'' elements sets such that for each ''w'' there is a unique minimal element in the corresponding Bruhat ordering of ''k''-element subsets. This is exactly the definition of a matroid of rank ''k'' on an ''n''-element set in terms of bases: a matroid can be defined as some ''k''-element subsets called bases of an ''n''-element set such that for each linear ordering of the set there is a unique minimal base in the

Gale ordering A gale is a strong wind; the word is typically used as a descriptor in nautical contexts. The U.S. National Weather Service defines a gale as sustained surface winds moving at a speed of between 34 and 47 knots (, or ).Matroid theory Coxeter groups