# 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

as a notation for the Coxeter complex of W and the symbol
for the set of left cosets of the parabolic subgroup P. We shall use the Bruhat ordering on
in its geometric interpretation, as defined in [2, Theorem 5.7]. The w-Bruhat ordering on
is denoted by the same symbol
as the w-Bruhat ordering on
. Notation
, <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

is called a Coxeter matroid (for W and P) if it satisfies the maximality property: for every
the set
contains a unique w-maximal element A; this means that
for all
. If
is 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
[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

i.e. a map satisfying the matroid inequality

The image

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

So we shall call a subset

a matroid if
satisfies the maximality property and every element of
is w-maximal in
with respect to some
. After that we have a natural one-to-one correspondence between matroid maps and matroid sets.

We can assign to every Coxeter matroid

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

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

is a matroid map if and only if the map

defined by

is also a matroid map.

Recall that

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

In

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

3. Characterisation of matroid maps

Two subsets A and B in

and
, 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

then all their common panels belong to the same wall
.

We say in this situation that

is the common wall of A and B.

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

Теорема 2. A map

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

(1) All the fibres

,
, are convex subsets of
.

(2) If two fibres

and
of
are adjacent then their images A and B are symmetric with respect to the wall
containing the common panels of
and
, and the residues A and B lie on the opposite sides of the wall
from the sets
,
, correspondingly.

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

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

Assume now that

satisfies the conditions (1) and (2).

First we introduce, for any two adjacent fibbers

and
of the map
, the wall
separating them. Let
be the set of all walls
.

Now take two arbitrary residues

and chambers
and
. We wish to prove
.

Consider a geodesic gallery

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

from u to v, then the corresponding residue
moves from
to
. Since the geodesic gallery
intersects every wall no more than once [5, Lemma 2.5], the chamber x crosses each wall
in
no more than once and, if it crosses
, it moves from the same side of
as u to the opposite side. But, by the assumptions of the theorem, this means that the residue
crosses each wall
no more than once and moves from the side of
opposite u to the side containing u. But, by the geometric interpretation of the Bruhat order, this means [2, Theorem 5.7] that
decreases, with respect to the u-Bruhat order, at every such step, and we ultimately obtain

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

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.

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

Ваше имя:

Комментарий

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

## Видео

Let's Play: StarCraft 2 Heart Of The Swarm - Original Mothership Map - Matroid  [ВИДЕО]Let's Play: StarCraft 2 Heart Of The Swarm - Arcade - Custom LoTv Map - Matroid  [ВИДЕО]
 ● MATRIOD SERVER TOUR  [ВИДЕО] ● Monotone submodular maximization over a matroid - Yuval Filmus  [ВИДЕО] ● StarCraft 2 Original Mothership recreated - version 2  [ВИДЕО] ● Starcraft 2 editor - Original mothership recreated - version 1 (mothership missiles, planet cracker)  [ВИДЕО] ● StarCraft II Editor + Matches  [ВИДЕО] ● Greg Henselman "Topological Network Analysis: Theory & Applications"  [ВИДЕО] ● let's play mario maker online #4 |ICH BIN MATROID xD  [ВИДЕО] ● Minecraft: CATWOMAN CHALLENGE GAMES - Lucky Block Mod - Modded Mini-Game  [ВИДЕО] ● Let´s Play Matroid Prime #31 [FINALE]: Das war Metroid Prime  [ВИДЕО] ● Let's Play: Heroes Of The Storm - BETA - Part 4 - Matroid Rises WIth Valla  [ВИДЕО]