3 - Matroids and Coxeter groups

Summary

Abstract

The paper describes a few ways in which the concept of a Coxeter group (in its most ubiquitous manifestation, the symmetric group) emerges in the theory of ordinary matroids:

• Gale's maximality principle which leads to the Bruhat order on the symmetric group;

• Jordan–Hölder permutation which measures distance between two maximal chains in a semimodular lattice and which happens to be closely related to Tits' axioms for buildings;

• matroid polytopes and associated reflection groups;

• Gaussian elimination procedure, BN-pairs and their Weyl groups.

These observations suggest a very natural generalisation of matroids; the new objects are called Coxeter matroids and are related to other Coxeter groups in the same way as (classical) matroids are related to the symmetric group.

Introduction

Combinatorics studies structures on a finite set; many of the most interesting of these arise from elimination of continuous parameters in problems from other mathematical disciplines.

Matroid is a combinatorial concept which arises from the elimination of continuous parameters from one of the most fundamental notions of mathematics: that of linear dependence of vectors.

Indeed, let E be a finite set of vectors in a vector space ℝⁿ. Vectors α₁,…, α_k are linearly dependent if there exist real numbers c₁,…, c_k, not all of zero, such that c₁α₁+…+c_kα_k = 0. In this context, the coefficients c₁,…,c_k are continuous parameters; what properties of the set E remain after we decide never to mention them?