Matroid maps

A.V. Borovik, Department of Mathematics, UMIST

1. Notation

This paper continues the works [1,2] and uses, with some modification, their terminology and notation. Throughout the paper W is a Coxeter group (possibly infinite) and P a finite standard parabolic subgroup of W. We identify the Coxeter group W with its Coxeter complex and refer to elements of W as chambers, to cosets with respect to a parabolic subgroup as residues, etc. We shall use the calligraphic letter

Matroid mapsas a notation for the Coxeter complex of W and the symbol
Matroid mapsfor the set of left cosets of the parabolic subgroup P. We shall use the Bruhat ordering on
Matroid mapsin its geometric interpretation, as defined in [2, Theorem 5.7]. The w-Bruhat ordering on
Matroid mapsis denoted by the same symbol
Matroid mapsas the w-Bruhat ordering on
Matroid maps. Notation
Matroid maps, <w, >w has obvious meaning.

We refer to Tits [6] or Ronan [5] for definitions of chamber systems, galleries, geodesic galleries, residues, panels, walls, half-complexes. A short review of these concepts can be also found in [1,2].

2. Coxeter matroids

If W is a finite Coxeter group, a subset

Matroid mapsis called a Coxeter matroid (for W and P) if it satisfies the maximality property: for every
Matroid mapsthe set
Matroid mapscontains a unique w-maximal element A; this means that
Matroid mapsfor all
Matroid maps. If
Matroid mapsis a Coxeter matroid we shall refer to its elements as bases. Ordinary matroids constitute a special case of Coxeter matroids, for W=Symn and P the stabiliser in W of the set
Matroid maps[4]. The maximality property in this case is nothing else but the well-known optimal property of matroids first discovered by Gale [3].

In the case of infinite groups W we need to slightly modify the definition. In this situation the primary notion is that of a matroid map

Matroid maps

i.e. a map satisfying the matroid inequality

Matroid maps

The image

Matroid mapsof
Matroid mapsobviously satisfies the maximality property. Notice that, given a set
Matroid mapswith the maximality property, we can introduce the map
Matroid mapsby setting
Matroid mapsbe equal to the w-maximal element of
Matroid maps. Obviously,
Matroid mapsis a matroid map. In infinite Coxeter groups the image
Matroid mapsof the matroid map associated with a set
Matroid mapssatisfying the maximality property may happen to be a proper subset of
Matroid maps(the set of all `extreme' or `corner' chambers of
Matroid maps; for example, take for
Matroid mapsa large rectangular block of chambers in the affine Coxeter group
Matroid maps). This never happens, however, in finite Coxeter groups, where
Matroid maps.

So we shall call a subset

Matroid mapsa matroid if
Matroid mapssatisfies the maximality property and every element of
Matroid mapsis w-maximal in
Matroid mapswith respect to some
Matroid maps. After that we have a natural one-to-one correspondence between matroid maps and matroid sets.

We can assign to every Coxeter matroid

Matroid mapsfor W and P the Coxeter matroid for W and 1 (or W-matroid).

Теорема 1. [2, Lemma 5.15] A map

Matroid maps

is a matroid map if and only if the map

Matroid maps

defined by

Matroid mapsis also a matroid map.

Recall that

Matroid mapsdenotes the w-maximal element in the residue
Matroid maps. Its existence, under the assumption that the parabolic subgroup P is finite, is shown in [2, Lemma 5.14].


Matroid mapsis a matroid map, the map
Matroid mapsis called the underlying flag matroid map for
Matroid mapsand its image
Matroid mapsthe underlying flag matroid for the Coxeter matroid
Matroid maps. If the group W is finite then every chamber x of every residue
Matroid mapsis w-maximal in
Matroid mapsfor w the opposite to x chamber of
Matroid mapsand
Matroid maps, as a subset of the group W, is simply the union of left cosets of P belonging to
Matroid maps.

3. Characterisation of matroid maps

Two subsets A and B in

Matroid mapsare called adjacent if there are two adjacent chambers
Matroid mapsand
Matroid maps, the common panel of a and b being called a common panel of A and B.

Лемма 1. If A and B are two adjacent convex subsets of

Matroid mapsthen all their common panels belong to the same wall
Matroid maps.

We say in this situation that

Matroid mapsis the common wall of A and B.

For further development of our theory we need some structural results on Coxeter matroids.

Теорема 2. A map

Matroid mapsis a matroid map if and only if the following two conditions are satisfied.

(1) All the fibres

Matroid maps,
Matroid maps, are convex subsets of
Matroid maps.

(2) If two fibres

Matroid mapsand
Matroid mapsof
Matroid mapsare adjacent then their images A and B are symmetric with respect to the wall
Matroid mapscontaining the common panels of
Matroid mapsand
Matroid maps, and the residues A and B lie on the opposite sides of the wall
Matroid mapsfrom the sets
Matroid maps,
Matroid maps, correspondingly.

Доказательство. If

Matroid mapsis a matroid map then the satisfaction of conditions (1) and (2) is the main result of [2].

Assume now that

Matroid mapssatisfies the conditions (1) and (2).

First we introduce, for any two adjacent fibbers

Matroid mapsand
Matroid mapsof the map
Matroid maps, the wall
Matroid mapsseparating them. Let
Matroid mapsbe the set of all walls
Matroid maps.

Now take two arbitrary residues

Matroid mapsand chambers
Matroid mapsand
Matroid maps. We wish to prove
Matroid maps.

Consider a geodesic gallery

Matroid maps

connecting the chambers u and v. Let now the chamber x moves along

Matroid mapsfrom u to v, then the corresponding residue
Matroid mapsmoves from
Matroid mapsto
Matroid maps. Since the geodesic gallery
Matroid mapsintersects every wall no more than once [5, Lemma 2.5], the chamber x crosses each wall
Matroid mapsin
Matroid mapsno more than once and, if it crosses
Matroid maps, it moves from the same side of
Matroid mapsas u to the opposite side. But, by the assumptions of the theorem, this means that the residue
Matroid mapscrosses each wall
Matroid mapsno more than once and moves from the side of
Matroid mapsopposite u to the side containing u. But, by the geometric interpretation of the Bruhat order, this means [2, Theorem 5.7] that
Matroid mapsdecreases, with respect to the u-Bruhat order, at every such step, and we ultimately obtain
Matroid maps

Список литературы

Borovik A.V., Gelfand I.M. WP-matroids and thin Schubert cells on Tits systems // Advances Math. 1994. V.103. N.1. P.162-179.

Borovik A.V., Roberts K.S. Coxeter groups and matroids, in Groups of Lie Type and Geometries, W. M. Kantor and L. Di Martino, eds. Cambridge University Press. Cambridge, 1995 (London Math. Soc. Lect. Notes Ser. V.207) P.13-34.

Gale D., Optimal assignments in an ordered set: an application of matroid theory // J. Combinatorial Theory. 1968. V.4. P.1073-1082.

Gelfand I.M., Serganova V.V. Combinatorial geometries and torus strata on homogeneous compact manifolds // Russian Math. Surveys. 1987. V.42. P.133-168.

Ronan M. Lectures on Buildings - Academic Press. Boston. 1989.

Tits J. A local approach to buildings, in The Geometric Vein (Coxeter Festschrift) Springer-Verlag, New York a.o., 1981. P.317-322.


Все материалы в разделе "Иностранный язык"

ДОБАВИТЬ КОММЕНТАРИЙ  [можно без регистрации]
перед публикацией все комментарии рассматриваются модератором сайта - спам опубликован не будет

Ваше имя:


Хотите опубликовать свою статью или создать цикл из статей и лекций?
Это очень просто – нужна только регистрация на сайте.

Copyright © 2015-2018. All rigths reserved.