Coxeter matroid
Group-theoretic generalization of matroids From Wikipedia, the free encyclopedia
Group-theoretic generalization of matroids From Wikipedia, the free encyclopedia
In mathematics, Coxeter matroids are generalization of matroids depending on a choice of a Coxeter group W and a parabolic subgroup P. Ordinary matroids correspond to the case when P is a maximal parabolic subgroup of a symmetric group W. They were introduced by Gelfand and Serganova (1987, 1987b), who named them after H. S. M. Coxeter.
Borovik, Gelfand & White (2003) give a detailed account of Coxeter matroids.
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.
Suppose that the Coxeter group W is the symmetric group Sn and P is the parabolic subgroup Sk×Sn–k. Then W/P can be identified with the k-element subsets of the n-element set {1,2,...,n} 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.