In mathematics, Coxeter matroids are generalization of

matroid In combinatorics, 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 Axiomatic system, axiomatically, the most significant being in terms ...

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 ref ...

''W'' and a

parabolic subgroup Parabolic subgroup may refer to: * a parabolic subgroup of a reflection group * a subgroup of an algebraic group that contains a Borel subgroup In the theory of algebraic groups, a Borel subgroup of an algebraic group ''G'' is a maximal Zarisk ...

''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. 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 the strong order, strong Bruhat order, Chevalley order, Bruhat–Chevalley order, or Chevalley–Bruhat order) is a partial order on the elements of a Coxeter group, that corresponds to the inclusion or ...

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 grou ...

''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 of ''k''-element subsets.

References

* * *{{Citation , last1=Gelfand , first1=I. M. , author1-link = Israel Gelfand , last2=Serganova , first2=V. V. , author2-link = Vera Serganova , title=Combinatorial geometries and the strata of a torus on homogeneous compact manifolds , doi= 10.1070/RM1987v042n02ABEH001308 , mr=0898623 , year=1987b , journal=Akademiya Nauk SSSR I Moskovskoe Matematicheskoe Obshchestvo. Uspekhi Matematicheskikh Nauk , issn=0042-1316 , volume=42 , issue=2 , pages=107–134 – English translation in Russian Mathematical Surveys 42 (1987), no. 2, 133–168 Matroid theory Coxeter groups