×

Matroids on partially ordered sets. (English) Zbl 0908.05025

The concept of a matroid is known to be a fundamental concept in combinatorics and it is also known to be ubiquitous in mathematics in general (e.g., stratification of Grassmanians, arrangements of hyperplanes, optimization). In the literature there exist attempts to generalize this concept. Those generalizations are mostly driven by a particular choice of the numerous aspects of matroids. For example “greedoids” [see B. Korte, L. Lovász, and R. Schrader, Greedoids (1991; Zbl 0733.05023)] were defined inspired by the fact that matroids allow a characterization by greedy algorithms. In this paper the authors are driven by the “arrangement aspect” of matroids. Every arrangement of hyperplanes in a vector space over a field gives rise to a matroid; the independent sets are the sets of hyperplanes whose intersection has codimension equal to the cardinality of the set. Now if one replaces hyperplanes by general linear subspaces the situation becomes much less structured. The concept of poset matroid introduced by the authors is proposed as a generalization capturing this situation. Various results valid for matroids are verified in the same or slightly modified form for poset matroids. A poset matroid is a set of filters – the bases of the poset matroid – on a partially ordered set. The axioms say that no two bases are contained in each other and for two bases and two arbitrary filters, one a lower bound for the first base and one an upper bound for the second, there is a base that is bounded by both. Arrangements of general linear subspaces are shown to give rise to poset matroids by choosing the poset as a disjoint union of chains. There is some overlap with the paper [Adv. Math. 102, No. 2, 230-239 (1993; Zbl 0793.05035)], where the same set of authors first introduced the notion of poset matroid.
Reviewer: V.Welker (Essen)

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M., Combinatorial theory, Grundlehren Math. Wiss., 234 (1979) · Zbl 0415.05001
[2] Baer, R., Linear Algebra and Projective Geometry (1952), Academic Press: Academic Press New York · Zbl 0049.38103
[3] Barnabei, M.; Nicoletti, G., Axiomatizing matroids by means of the set of non-generators, Boll. Un. Mat. Ital. A (5), 17, 121-127 (1980) · Zbl 0503.05017
[4] Barnabei, M.; Nicoletti, G.; Pezzoli, L., The symmetric exchange property for poset matroids, Adv. Math., 102, 230-239 (1993) · Zbl 0793.05035
[5] Bertini, E., Introduzione alla Geometria Proiettiva degli Iperspazi (1923), Pricipato: Pricipato Messina · JFM 49.0484.08
[6] Birkhoff, G. D., Abstract linear dependence in lattices, Amer. J. Math., 57, 800-804 (1935) · Zbl 0013.00104
[7] Birkhoff, G. D., Lattice Theory,. Lattice Theory,, Colloquium Publication 25 (1967), American Mathematical Society: American Mathematical Society Providence
[8] Björner, A., Subspace arrangements, Proc. 1st European Cong. Math., Paris, 1992 (1994), North-Holland: North-Holland Amsterdam · Zbl 0844.52008
[9] Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G. M., Oriented matroids, Encyclopædia of Mathematics and Its Applications (1993), Cambridge Univ. Press: Cambridge Univ. Press London · Zbl 0773.52001
[10] Brualdi, R. A., Comments on bases in dependence structures, Bull. Austral. Math. Soc., 1, 161-167 (1969) · Zbl 0172.30703
[11] Brylawski, T. H., Some properties of basic families of subsets, Discrete Math.,, 6, 333-341 (1973) · Zbl 0274.05004
[12] Brylawski, T. H., Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc., 203, 1-44 (1975) · Zbl 0299.05023
[13] Brylawski, T. H.; Kelly, D., Matroids and Combinatorial Geometries (1980), Univ. of North Carolina Press: Univ. of North Carolina Press Chapel Hill · Zbl 0428.05016
[14] Crapo, H. H.; Rota, G.-C., Combinatorial Geometries (1970), MIT Press: MIT Press Cambridge · Zbl 0216.02101
[15] Crawley, P.; Dilworth, R. P., Algebraic Theory of Lattices (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 0494.06001
[16] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (1990), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0701.06001
[17] Dawson, J., A remark on an exchange theorem for bases, J. Math. Anal. Appl., 62, 354-355 (1978) · Zbl 0384.05014
[18] Dilworth, R. P., Dependence relations in a semimodular lattice, Duke Math J., 11, 575-587 (1944) · Zbl 0060.06101
[19] Dunstan, F. D.J.; Ingleton, A. W.; Welsh, D. I.A., Supermatroids, Proc. Conf. Comb. Math. Math. Inst. Oxford (1972), p. 72-122
[20] Edmonds, J., Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Stand., 69B, 241-245 (1967) · Zbl 0178.03002
[21] Edmonds, J., Matroid partition, (Dantzig, G.; Veinott, A., Mathematics of the Decision Sciences (1). Mathematics of the Decision Sciences (1), Lectures in Applied Mathematics, 11 (1968), American Mathematical Society: American Mathematical Society Providence), 335-345 · Zbl 0197.00802
[22] Edmonds, J., Submodular functions, matroids and certain polyhedra, (Guy, R., Combinatorial Structures and Their Applications (1969), Gordon & Breach: Gordon & Breach New York), 69-87
[23] Edmonds, J.; Rota, G.-C., Submodular set functions, Abstracts of the Waterloo Combinatorics Conference (1966), University of Waterloo: University of Waterloo Ontario
[24] Faigle, U., Geometries on partially ordered sets, J. Combin. Theory Ser. B, 28, 26-51 (1980) · Zbl 0359.05018
[25] Fujishige, S., Polymatroid dependence structure of a set of random variables, Inform. and Control (Shenyang), 39, 55-72 (1978) · Zbl 0388.94006
[26] Gabow, H., Decomposing symmetric exchanges in matroid bases, Math. Prog., 10, 271-276 (1976) · Zbl 0358.05019
[27] Grätzer, G., General Lattice Theory (1978), Birkhäuser: Birkhäuser Basel · Zbl 0385.06015
[28] Greene, C., Lectures on Combinatorial Geometries. Lectures on Combinatorial Geometries, Advanced Science Seminar in Combinatorial Theory (1971), Bowdoin College: Bowdoin College Bowdoin
[29] Greene, C., A multiple exchange property for bases, Proc. Amer. Math. Soc., 39, 45-50 (1973) · Zbl 0267.05028
[30] Greene, C., Another exchange property for bases, Proc. Amer. Math. Soc., 46, 155-156 (1974) · Zbl 0294.05012
[31] Guidotti, L.; Nicoletti, G., Caratterizzazione dei sistemi di indipendenza e delle matroidi mediante minori proibiti, Atti del Quinto Convegno A.M.A.S.E.S., Perugia, 1981 (1982), p. 185-191
[32] Guidotti, L.; Nicoletti, G., Minors in Boolean structure and matroids, Ann. Discrete Math., 14, 219-224 (1982) · Zbl 0498.05021
[33] Hall, P., On representatives of subsets, J. London Math. Soc., 10, 26-30 (1935) · Zbl 0010.34503
[34] Helgason, T., Aspects of the theory of hypermatroids, Hypergraph Seminar. Hypergraph Seminar, Springer Lecture Notes, 411 (1974), p. 191-214 · Zbl 0299.05127
[35] Higgs, D. A., Geometry. Geometry, Lecture Notes (1966), University of Waterloo: University of Waterloo Ontario
[36] Ingleton, A. W., A note on independence functions and rank, J. London Math. Soc., 34, 49-56 (1959) · Zbl 0089.01802
[37] Ingleton, A. W.; Piff, M. J., Gammoids and transversal matroids, J. Combin. Theory, 15, 51-68 (1973) · Zbl 0264.05021
[38] Knuth, D. E., Random matroids, Discrete Math., 12, 341-358 (1975) · Zbl 0314.05012
[39] Korte, B.; Hausmann, D., An analysis of the greedy heuristic for independence systems, Ann. Discrete Math., 2, 65-74 (1978) · Zbl 0392.90058
[40] Kung, J. P.S., Alternating basis exchanges in matroids, Proc. Amer. Math. Soc., 71, 355-358 (1978) · Zbl 0398.05025
[41] Kung, J. P.S., On specializations of matroids, Stud. Appl. Math., 62, 183-187 (1980) · Zbl 0434.05021
[42] Las Vergnas, M., Bases in oriented matroids, J. Combin. Theory Ser. B, 25, 283-289 (1978) · Zbl 0396.05005
[43] Lawrence, J., Oriented matroids and multiply ordered sets, Linear Algebra Appl., 48, 1-12 (1982) · Zbl 0506.05019
[44] Lazarson, T., The representation problem for independence functions, J. London Math. Soc., 33, 21-25 (1958) · Zbl 0083.00403
[45] MacLane, S., Some interpretations of abstract linear dependence in terms of projective geometry, Amer. J. Math., 58, 236-240 (1936) · JFM 62.0649.02
[46] Magnanti, T. L., Complementary bases of a matroid, Discrete Math., 8, 355-361 (1974) · Zbl 0294.05017
[47] Mason, J. H., Matroids as the study of geometrical configurations, (Aigner, M., Higher Combinatorics (1977), Reidel: Reidel Dordrecht), 133-176 · Zbl 0358.05017
[48] McDiarmid, C. J.M., An exchange theorem for independence structures, Proc. Amer. Math. Soc., 47, 513-514 (1975) · Zbl 0296.05005
[49] Mirsky, L.; Perfect, H., Application of the notion of independence to combinatorial analysis, J. Combin. Theory, 2, 327-357 (1967) · Zbl 0153.02201
[50] Nguyen, H. Q., Semi-modular functions and combinatorial geometries, Trans. Amer. Math. Soc., 238, 355-383 (1978) · Zbl 0411.05029
[51] Nicoletti, G., Generating cryptomorphic axiomatizations of matroids, (Artzy, R.; Vaisman, I., Geometry and Differential Geometry. Geometry and Differential Geometry, Lecture Notes in Mathematics, 792 (1979), Springer-Verlag: Springer-Verlag Berlin), 110-113
[52] Oxley, J. G., Matroid Theory (1992), Oxford University PressOxford Science Publications, The Clarendon Press: Oxford University PressOxford Science Publications, The Clarendon Press New York
[53] Perfect, H., Independence spaces and combinatorial problems, Proc. London Math. Soc., 19, 17-30 (1969) · Zbl 0176.28302
[54] Perfect, H., Independence theory and matroids, Math. Gaz., 65, 103-111 (1981) · Zbl 0467.05023
[55] Pezzoli, L., Sulle valutazioni nei reticoli modulari, Algebra e Geometria, Suppl. Boll. Un. Mat. Ital., 2, 341-353 (1980) · Zbl 0448.06008
[56] Pezzoli, L., Sistemi di indipendenza modulari, Boll. Un. Mat. Ital. B (5), 18-B, 575-590 (1981)
[57] Pezzoli, l., Iperpiani e circuiti delle matroidi sugli insiemi parzialmente ordinati, Atti del Convegno di Geom. Comb. e di Incidenza, Rend. Sem. Mat. Brescia (1982), p. 539-551
[58] Pezzoli, L., On D-complementation, Adv. Math., 51, 226-239 (1984) · Zbl 0546.05020
[59] Pezzoli, L., Teoria delle matroidi sugli insiemi parzialmente ordinati, (Nicoletti, G., Publications de l’Institut de Recherche Mathématique Avancée. Publications de l’Institut de Recherche Mathématique Avancée, Actes du 13° Séminaire Lotharingien de Combinatoire, 316 (1986)), 83-104
[60] Pezzoli, L.; Ross, N. J., The closure lattice of combinatorial schemes, C.N.R. Report (1990)
[61] Pym, J. S.; Perfect, H., Submodular functions and independence structures, J. Math. Anal. Appl., 30, 1-31 (1970) · Zbl 0169.01902
[62] Rado, R., A theorem on independence relations, Quart. J. Math. Oxford, 20, 95-104 (1949)
[63] Rockafellar, R. T., The elementary vectors of a subspace of\(R^n\), (Bose, R. C.; Dowling, T. A., Combinatorial Mathematics and Its Applications (1969), Univ. of North Carolina Press: Univ. of North Carolina Press Chapel Hill), 104-127 · Zbl 0229.90019
[66] Seymour, P. D., On the points-lines-planes conjecture, J. Combin. Theory Ser. B, 33, 17-26 (1982) · Zbl 0505.05024
[68] Todd, M. J., A combinatorial generalization of polytopes, J. Combin. Theory Ser. B, 20, 229-242 (1976) · Zbl 0295.05007
[69] Tutte, W. T., Lectures on matroids, J. Res. Nat. Bur. Standards, 69B, 1-47 (1965) · Zbl 0151.33801
[70] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002
[71] White, N. L., A basis extension property, J. London Math. Soc., 7, 662-664 (1974) · Zbl 0279.05023
[72] White, N. L., A unique exchange property for bases, Linear Algebra Appl., 31, 81-91 (1980) · Zbl 0458.05022
[73] White, N. L., Theory of matroids, Encyclopædia of Mathematics and Its Applications (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[74] White, N. L., Combinatorial geometries, Encyclopædia of Mathematics and Its Applications (1988), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0212.25503
[75] White, N. L., Matroid applications, Encyclopædia of Mathematics and Its Applications (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0742.00052
[76] Whitney, H., On the abstract properties of linear dependence, Amer. J. Math., 57, 509-533 (1935) · JFM 61.0073.03
[77] Woodall, D. R., An exchange theorem for bases of matroids, J. Combin. Theory, 16, 227-228 (1974) · Zbl 0275.05020
[78] Bonin, J. E., Matroid theory, AMS-IMS-SIAM Joint Summer Research Conference on Matroid Theory, July 2-6, 1995, University of Washington, Seattle, WA. AMS-IMS-SIAM Joint Summer Research Conference on Matroid Theory, July 2-6, 1995, University of Washington, Seattle, WA, Contemp. Math., 197 (1996), Amer. Math. Soc: Amer. Math. Soc Providence
[79] da Silva, I. P.F., Axioms for maximal vectors of an oriented matroid: A combinatorial characterization of the regions determined by an arrangement of pseudohyperplanes, Eur. J. Comb., 16, 125-145 (1995) · Zbl 0824.52018
[80] Massey, D. B.; Simion, R.; Stanley, R. P.; Vartigan, D.; Welsh, D. J.A.; Ziegler, G. M., Le numbers of arrangements and matroid identities, J. Comb. Theory Ser. B, 70, 118-133 (1997) · Zbl 0884.05029
[81] White, N. L., The bracket ring of a combinatorial geometry. I, Trans. Am. Math. Soc., 202, 79-95 (1975) · Zbl 0303.05022
[82] White, N. L., The bracket ring of a combinatorial geometry: II: Unimodular geometries, Trans. Am. Math. Soc., 214, 233-248 (1975) · Zbl 0294.05013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.