The Greedy Algorithm and Coxeter Matroids

The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair (W, P) consisting of a finite irreducible Coxeter group W and parabolic subgroup P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are a special case, the case W = A (isomorphic to the symmetric group Sym_{_n+1}) and P a maximal parabolic subgroup. The main result of this paper is that for Coxeter matroids, just as for ordinary matroids, the greedy algorithm provides a solution to a naturally associated combinatorial optimization problem. Indeed, in many important cases, Coxeter matroids are characterized by this property. This result generalizes the classical Rado-Edmonds and Gale theorems.A corollary of our theorem is that, for Coxeter matroids L, the greedy algorithm solves the L-assignment problem. Let W be a finite group acting as linear transformations on a Euclidean space , and let

An Adjacency Criterion for Coxeter Matroids

A Coxeter matroid is a generalization of matroid, ordinary matroid being the case corresponding to the family of Coxeter groups A _n , which are isomorphic to the symmetric groups. A basic result in the subject is a geometric characterization of Coxeter matroid in terms of the matroid polytope, a result first stated by Gelfand and Serganova. This paper concerns properties of the matroid polytope. In particular, a criterion is given for adjacency of vertices in the matroid polytope.     

Boundaries of right-angled Coxeter groups with manifold nerves

All abstract reflection groups act geometrically on non-positively curved geodesic spaces. Their natural space at infinity, consisting of (bifurcating) infinite geodesic rays emanating from a fixed base point, is called a boundary of the group.We will present a condition on right-angled Coxeter groups under which they have topologically homogeneous boundaries. The condition is that they have a nerve which is a connected closed orientable PL manifold.In the event that the group is generated by the reflections of one of Davis’ exotic open contractible n-manifolds (n?4), the group will have a boundary which is a homogeneous cohomology manifold. This group boundary can then be used to equivariantly Z-compactify the Davis manifold.If the compactified manifold is doubled along the group boundary, one obtains a sphere if n?5. The system of reflections extends naturally to this sphere and can be augmented by a reflection whose fixed point set is the group boundary. It will be shown that the fixed point set of each extended original reflection on the thus formed sphere is a tame codimension-one sphere.     

Symplectic Matroids

A symplectic matroid is a collection B of k-element subsets of J = {1, 2, ..., n, 1*, 2*, ...; n*}, each of which contains not both of i and i* for every i n, and which has the additional property that for any linear ordering of J such that i j implies j* i* and i j* implies j i* for all i, j n, B has a member which dominates element-wise every other member of B. Symplectic matroids are a special case of Coxeter matroids, namely the case where the Coxeter group is the hyperoctahedral group, the group of symmetries of the n-cube. In this paper we develop the basic properties of symplectic matroids in a largely self-contained and elementary fashion. Many of these results are analogous to results for ordinary matroids (which are Coxeter matroids for the symmetric group), yet most are not generalizable to arbitrary Coxeter matroids. For example, representable symplectic matroids arise from totally isotropic subspaces of a symplectic space very similarly to the way in which representable ordinary matroids arise from a subspace of a vector space. We also examine Lagrangian matroids, which are the special case of symplectic matroids where k = n, and which are equivalent to Bouchet's symmetric matroids or 2-matroids.     

Basis-Transitive Matroids

We consider the problem of classifying all finite basis-transitive matroids and reduce it to the classification of the finite basis-transitive and point-primitive simple matroids (or geometric lattices, or dimensional linear spaces). Our main result shows how a basis- and point-transitive simple matroid is decomposed into a so-called supersum. In particular each block of imprimitivity bears the structure of two closely related simple matroids, and the set of blocks of imprimitivity bears the structure of a point- and basis-transitive matroid.     

Almost-Graphic Matroids

A nongraphic matroid M is said to be almost-graphic if, for all elements e, either M\e or M/e is graphic. We determine completely the class of almost-graphic matroids, thereby answering a question posed by Oxley in his book “Matroid Theory.” A nonregular matroid is said to be almost-regular if, for all elements e, either M\e or M/e is regular. An element e for which both M\e and M/e are regular is called a regular element. We also determine the almost-regular matroids with at least one regular element.     

初等模糊拟阵与基本截片模糊拟阵的若干性质

对两种初等模糊拟阵和基本截片模糊拟阵的定义进行了比较,研究了它们之间的关系.研究了初等模糊拟阵的若干性质,得到了初等模糊拟阵和基本截片模糊拟阵为闭正则模糊拟阵等结论,给出了初等模糊拟阵的等价刻画以及初等模糊拟阵与其截拟阵之间的关系.     

On Coxeter recurrences

An interesting family of recurrences of order n ≥ 2, which are globally (n+3)-periodic was introduced by Coxeter in 1971. We prove a surprising property of this family: ‘all’ the possible geometrical behaviours that linear real (n+3)-periodic recurrences can have are present inside the Coxeter recurrences.     

Matroids without adjoint

The purpose of this note is to give an example of a rank-4 matroid which not only shows that Levi's intersection property is not a sufficient condition for the existence of an adjoint but also seems to have an interesting structure of the lattice of flats.     

Coxeter groups,Coxeter monoids and the Bruhat order

Associated with any Coxeter group is a Coxeter monoid, which has the same elements, and the same identity, but a different multiplication. (Some authors call these Coxeter monoids 0-Hecke monoids, because of their relation to the 0-Hecke algebras—the q=0 case of the Hecke algebra of a Coxeter group.) A Coxeter group is defined as a group having a particular presentation, but a pair of isomorphic groups could be obtained via non-isomorphic presentations of this form. We show that when we have both the group and the monoid structure, we can reconstruct the presentation uniquely up to isomorphism and present a characterisation of those finite group and monoid structures that occur as a Coxeter group and its corresponding Coxeter monoid. The Coxeter monoid structure is related to this Bruhat order. More precisely, multiplication in the Coxeter monoid corresponds to element-wise multiplication of principal downsets in the Bruhat order. Using this property and our characterisation of Coxeter groups among structures with a group and monoid operation, we derive a classification of Coxeter groups among all groups admitting a partial order.     

Coxeter cochain complexes

We define the Coxeter cochain complex of a Coxeter group (G, S) with coefficients in a ?[G]-module A. This is closely related to the complex of simplicial cochains on the abstract simplicial complex I(S) of the commuting subsets of S. We give some representative computations of Coxeter cohomology and explain the connection between the Coxeter cohomology for groups of type A, the (singular) homology of certain configuration spaces, and the (Tor) homology of certain local Artin rings.     

Chordal Coxeter groups

A solution of the isomorphism problem is presented for the class of Coxeter groups W that have a finite set of Coxeter generators S such that the underlying graph of the presentation diagram of the system (W,S) has the property that every cycle of length at least four has a chord. As an application, we construct counterexamples to two conjectures concerning the isomorphism problem for Coxeter groups.      

Rigidity of Coxeter groups

Let be a Coxeter group acting properly discontinuously and cocompactly on manifolds and such that the fixed point sets of finite subgroups are contractible. Let be a -homotopy equivalence which restricts to a -homeomorphism on the boundary. Under an assumption on the three dimensional fixed point sets, we show that then is -homotopic to a -homeomorphism.