The Greedy Algorithm and Coxeter Matroids
A. Vince
University of Florida Department of Mathematics P.O. Box 118105 474 Little Hall Gainesville FL 32611 USA
DOI: 10.1023/A:1008780132748
Abstract
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 \mathbb E \mathbb{E} , and let
The L-assignment problem is to minimize the function f x, h f_{ξ,η} on a given subset L Í \subseteq W.
| f x, h ( w) = á w x, h ñ \text for x, h Ĩ \mathbb E, w Ĩ W. f_{ξ,η} (w) = \left\langle {wξ,η} \right\rangle {\text{ for }}ξ, η\in \mathbb{E},w \in W. |
Pages: 155–178
Keywords: greedy algorithm; Coxeter group; matroid; Bruhat order
Full Text: PDF
References
1. A. Barvinok and A. Vershik, “Convex hulls of orbits in the representations of finite groups and combinatorial optimization,” Funct. Anal. Appl. 22 (1988), 66-68.
2. A.V. Borovik, I.M. Gelfand, and N. White, “Symplectic matroids,” J. Alg. Combin. 8 (1998), 235-252.
3. A.V. Borovik, I.M. Gelfand, and N. White, Coxeter Matroids, Birkhauser, Boston.
4. A.V. Borovik, I.M. Gelfand, A. Vince, and N. White, “The lattice of flats and its underlying flag matroid polytope,” Annals of Combinatorics 1 (1998), 17-26. VINCE
5. A.V. Borovik and A. Vince, “An adjacency criterion for Coxeter matroids,” J. Alg. Combin. 9 (1999), 271-280.
6. A. Bouchet, “Greedy algorithm and symmetric matroids,” Math. Programming 38 (1987), 147-159.
7. V.V. Deodhar, “Some characterizations of Coxeter groups,” Enseignments Math. 32 (1986), 111-120.
8. D. Gale, “Optimal assignments in an ordered set: An application of matroid theory,” J. Combinatorial Theory 4 (1968), 1073-1082.
9. I.M. Gelfand, M. Goresky, R.D. MacPherson, and V.V. Serganova, “Combinatorial Geometries, convex polyhedra, and Schubert cells,” Adv. Math. 63 (1987), 301-316.
10. I.M. Gelfand and V.V. Serganova, “On a general definition of a matroid and a greedoid,” Soviet Math. Dokl. 35 (1987), 6-10.
11. I.M. Gelfand and V.V. Serganova, “Combinatorial geometries and torus strata on homogeneous compact manifolds,” Russian Math. Surveys 42 (1987), 133-168; I.M. Gelfand, Collected Papers, Vol. III, Springer- Verlag, New York, 1989, pp. 926-958.
12. H. Hiller, Geometry of Coxeter Groups, Pitman, Boston 1982.
13. B. Korte, L. Lovasz, and R. Schrader, Greedoids, Springer-Verlag, Berlin, 1991.
14. R. Proctor, “Bruhat lattices, plane partition generating functions, and minuscule representations,” Europ. J. Combinatorics 5 (1984), 331-350.
15. V.V. Serganova, A. Vince, and A.V. Zelevinski, “A geometric characterization of Coxeter matroids,” Annals of Combinatorics 1 (1998), 173-181.
16. V. Serganova and A. Zelevinsky, “Combinatorial optimization on Weyl groups, greedy algorithms and generalized matroids,” preprint, Scientific Council in Cybernetics, USSR Academy of Sciences, 1989.
17. J. Tits, A local approach to buildings, The Geometric Vein (the Coxeter Festschrift), Springer, 1981.
2. A.V. Borovik, I.M. Gelfand, and N. White, “Symplectic matroids,” J. Alg. Combin. 8 (1998), 235-252.
3. A.V. Borovik, I.M. Gelfand, and N. White, Coxeter Matroids, Birkhauser, Boston.
4. A.V. Borovik, I.M. Gelfand, A. Vince, and N. White, “The lattice of flats and its underlying flag matroid polytope,” Annals of Combinatorics 1 (1998), 17-26. VINCE
5. A.V. Borovik and A. Vince, “An adjacency criterion for Coxeter matroids,” J. Alg. Combin. 9 (1999), 271-280.
6. A. Bouchet, “Greedy algorithm and symmetric matroids,” Math. Programming 38 (1987), 147-159.
7. V.V. Deodhar, “Some characterizations of Coxeter groups,” Enseignments Math. 32 (1986), 111-120.
8. D. Gale, “Optimal assignments in an ordered set: An application of matroid theory,” J. Combinatorial Theory 4 (1968), 1073-1082.
9. I.M. Gelfand, M. Goresky, R.D. MacPherson, and V.V. Serganova, “Combinatorial Geometries, convex polyhedra, and Schubert cells,” Adv. Math. 63 (1987), 301-316.
10. I.M. Gelfand and V.V. Serganova, “On a general definition of a matroid and a greedoid,” Soviet Math. Dokl. 35 (1987), 6-10.
11. I.M. Gelfand and V.V. Serganova, “Combinatorial geometries and torus strata on homogeneous compact manifolds,” Russian Math. Surveys 42 (1987), 133-168; I.M. Gelfand, Collected Papers, Vol. III, Springer- Verlag, New York, 1989, pp. 926-958.
12. H. Hiller, Geometry of Coxeter Groups, Pitman, Boston 1982.
13. B. Korte, L. Lovasz, and R. Schrader, Greedoids, Springer-Verlag, Berlin, 1991.
14. R. Proctor, “Bruhat lattices, plane partition generating functions, and minuscule representations,” Europ. J. Combinatorics 5 (1984), 331-350.
15. V.V. Serganova, A. Vince, and A.V. Zelevinski, “A geometric characterization of Coxeter matroids,” Annals of Combinatorics 1 (1998), 173-181.
16. V. Serganova and A. Zelevinsky, “Combinatorial optimization on Weyl groups, greedy algorithms and generalized matroids,” preprint, Scientific Council in Cybernetics, USSR Academy of Sciences, 1989.
17. J. Tits, A local approach to buildings, The Geometric Vein (the Coxeter Festschrift), Springer, 1981.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition