The algebra of metric betweenness. I: Subdirect representation and retraction. (English) Zbl 1122.05083
The authors bring together concepts from graph theory and algebra. They aim for developing a structure theory for graphs from the algebraic point of view. For that they use equational classes, subdirect products, retractions and gated amalgamations.
They investigate classes of graphs which posses distinctive features of the geometry of their shortest paths. So the starting point are median graphs which can be characterized by the property that for each triple \((u,v,w)\) of vertices there is a unique vertice \(x\), the median of \((u,v,w)\), lying simultaneously on shortest paths between the three pais of the triplet. Thus there is a ternary operation and this operation can be used to define equational classes of the corresponding algebras. Generalizations lead to the new classes of quasi-median and weakly median graphs. These classes allow a decomposition into simple building blocks, which have a geometric interpretation.
As the main result the authors show that successive fiber amalgamations from Cartesian products lead to the subdirect representation of the resulting associated algera by subdirectly irreducibles whenever they begin with a class of (“prime”) graphs that posses only trivial gated subgraphs. The authors also consider infinite weakly median graphs.
They investigate classes of graphs which posses distinctive features of the geometry of their shortest paths. So the starting point are median graphs which can be characterized by the property that for each triple \((u,v,w)\) of vertices there is a unique vertice \(x\), the median of \((u,v,w)\), lying simultaneously on shortest paths between the three pais of the triplet. Thus there is a ternary operation and this operation can be used to define equational classes of the corresponding algebras. Generalizations lead to the new classes of quasi-median and weakly median graphs. These classes allow a decomposition into simple building blocks, which have a geometric interpretation.
As the main result the authors show that successive fiber amalgamations from Cartesian products lead to the subdirect representation of the resulting associated algera by subdirectly irreducibles whenever they begin with a class of (“prime”) graphs that posses only trivial gated subgraphs. The authors also consider infinite weakly median graphs.
Reviewer: Martin Weese (Potsdam)
References:
| [1] | Avann, S. P., Ternary distributive semi-lattices, Bull. Amer. Math. Soc., 54, 79 (1948) · Zbl 0099.02201 |
| [2] | Avann, S. P., Metric ternary distributive semi-lattices, Proc. Amer. Math. Soc., 12, 407-414 (1961) · Zbl 0099.02201 |
| [3] | Bandelt, H.-J., Tolerances on median algebras, Czechoslovak Math. J., 33, 344-347 (1983) · Zbl 0538.08003 |
| [4] | Bandelt, H.-J., Tolerante Catalanzahlen, Arch. Math. (Brno), 3, 113-116 (1983) · Zbl 0553.06010 |
| [5] | Bandelt, H.-J., Retracts of hypercubes, J. Graph Theory, 8, 501-510 (1984) · Zbl 0551.05060 |
| [6] | Bandelt, H.-J.; Chepoi, V., A Helly theorem in weakly modular space, Discrete Math., 126, 25-39 (1996) · Zbl 0864.05049 |
| [7] | Bandelt, H.-J.; Chepoi, V., Decomposition and \(l_1\)-embedding of weakly median graphs, European J. Combin., 21, 701-714 (2000) · Zbl 0965.05081 |
| [8] | H.-J. Bandelt, V. Chepoi, M. van de Vel, Pasch-Peano spaces and graphs, 1993 (Preprint); H.-J. Bandelt, V. Chepoi, M. van de Vel, Pasch-Peano spaces and graphs, 1993 (Preprint) |
| [9] | Bandelt, H.-J.; Hedlíková, J., Median algebras, Discrete Math., 45, 1-30 (1983) · Zbl 0506.06005 |
| [10] | Bandelt, H.-J.; Mulder, H. M., Pseudo-modular graphs, Discrete Math., 62, 245-260 (1986) · Zbl 0606.05053 |
| [11] | Bandelt, H.-J.; Mulder, H. M., Cartesian factorization of interval-regular graphs having no long isometric odd cycles, (Alavi, Y.; Chartrand, G.; Oellermann, O. R.; Schwenk, A. J., Graph Theory, Combinatorics, and Applications, vol. 1 (1991), Wiley), 55-75 · Zbl 0840.05074 |
| [12] | Bandelt, H.-J.; Mulder, H. M.; Wilkeit, E., Quasi-median graphs and algebras, J. Graph Theory, 18, 681-703 (1994) · Zbl 0810.05057 |
| [13] | Bandelt, H.-J.; Pesch, E., Dismantling absolute retracts of reflexive graphs, European J. Combin., 10, 211-220 (1989) · Zbl 0674.05065 |
| [14] | Bandelt, H.-J.; van de Vel, M.; Verheul, E., Modular interval spaces, Math. Nachr., 163, 177-201 (1993) · Zbl 0808.46011 |
| [15] | Bergman, G., On the existence of subalgebras of direct products with prescribed \(d\)-fold projections, Algebra Universalis, 7, 341-356 (1977) · Zbl 0327.08004 |
| [16] | Brešar, B., On the natural imprint function of a graph, European J. Combin., 23, 149-161 (2002) · Zbl 1002.05061 |
| [17] | Cameron, P., Dual polar spaces, Geom. Dedicata, 12, 75-85 (1982) · Zbl 0473.51002 |
| [18] | Chastand, M., Retracts of infinite Hamming graphs, J. Combin. Theory Ser., B 71, 54-66 (1997) · Zbl 0901.05040 |
| [19] | Chastand, M., Fiber-complemented graphs I: Structure and invariant subgraphs, Discrete Math., 226, 107-141 (2001) · Zbl 0961.05019 |
| [20] | Chastand, M., Fiber-complemented graphs II: Retractions and endomorphisms, Discrete Math., 268, 81-101 (2003) · Zbl 1022.05025 |
| [21] | Chastand, M.; Laviolette, F.; Polat, N., On constructible graphs, infinite bridged graphs and weakly cop-win graphs, Discrete Math., 224, 61-78 (2000) · Zbl 0961.05066 |
| [22] | Chepoi, V., Classifying graphs by metric triangles, Metody Diskretnogo Analiza, 49, 75-93 (1989), (in Russian) · Zbl 0736.05037 |
| [23] | Chepoi, V., Separation of two convex sets in convexity structures, J. Geom., 50, 30-51 (1994) · Zbl 0807.52002 |
| [24] | Chepoi, V., Bridged graphs are cop-win graphs: An algorithmic proof, J. Combin. Theory Ser., B 69, 97-100 (1997) · Zbl 0873.05060 |
| [25] | Chepoi, V., Graphs of some CAT(0) complexes, Advances Appl. Math., 24, 125-179 (2000) · Zbl 1019.57001 |
| [26] | Chung, F. R.K.; Graham, R. L.; Saks, M. E., A dynamic location problem for graphs, Combinatorica, 9, 111-132 (1989) · Zbl 0692.05055 |
| [27] | Crawley, P.; Dilworth, R. P., Algebraic Theory of Lattices (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0494.06001 |
| [28] | Czédli, G.; Horváth, E. K.; Radeleczki, S., On tolerance lattices of algebras in congruence modular varieties, Acta Math. Hungar., 100, 9-17 (2003) · Zbl 1049.08007 |
| [29] | Davey, B. A.; Idziak, P. M.; Lampe, W. A.; McNulty, G. F., Dualisability and graph algebras, Discrete Math., 214, 145-172 (2000) · Zbl 0945.08001 |
| [30] | Dorninger, D.; Nöbauer, W., Local polynomial functions on lattices and universal algebras, Colloq. Math., 42, 83-93 (1979) · Zbl 0432.06005 |
| [31] | Dress, A. W.M.; Scharlau, R., Gated sets in metric spaces, Aequationes Math., 34, 112-120 (1987) · Zbl 0696.54022 |
| [32] | Epstein, D. B.A.; Cannon, J. W.; Holt, D. F.; Levy, S. V.F.; Paterson, M. S.; Thurston, W. P., Word Processing in Groups (1992), Jones and Bartlett: Jones and Bartlett Boston · Zbl 0764.20017 |
| [33] | Farber, M.; Jamison, R. E., On local convexity in graphs, Discrete Math., 66, 231-247 (1987) · Zbl 0619.05032 |
| [34] | Feder, T., Product graph representations, J. Graph Theory, 16, 467-488 (1992) · Zbl 0766.05092 |
| [35] | Feder, T., Stable networks and product graphs, Mem. Amer. Math. Soc., 555, 223+xii (1995) · Zbl 0875.68397 |
| [36] | Fried, E.; Pixley, A. F., The dual discriminator in universal algebra, Acta Sci. Math. (Szeged), 41, 83-100 (1979) · Zbl 0395.08001 |
| [37] | Graham, R. L.; Winkler, P. M., On isometric embeddings of graphs, Trans. Amer. Math. Soc., 288, 527-536 (1985) · Zbl 0576.05017 |
| [38] | Grätzer, G., Universal Algebra (1979), Springer-Verlag: Springer-Verlag New York · Zbl 0182.34201 |
| [39] | Hell, P., Subdirect products of bipartite graphs, infinite and finite sets, Colloq. Math. Soc. János Bolyai, 10, 857-866 (1973) · Zbl 0308.05125 |
| [40] | Hell, P.; Rival, I., Absolute retracts and varieties of reflexive graphs, Canad. J. Math., 39, 544-567 (1987) · Zbl 0627.05039 |
| [41] | Hule, H.; Nöbauer, W., Local polynomial functions on universal algebras, An. Acad. Brasil. Ciênc., 49, 365-372 (1977) · Zbl 0377.08010 |
| [42] | Imrich, W.; Klavžar, S., Product Graphs. Structure and Recognition (2000), Wiley-Interscience: Wiley-Interscience New York · Zbl 0963.05002 |
| [43] | Isbell, J. R., Median algebra, Trans. Amer. Math. Soc., 260, 319-362 (1980) · Zbl 0446.06007 |
| [44] | H.M. Mulder, The Interval Function of a Graph, in: Mathematical Centre Tracts, vol. 132, Amsterdam, 1980; H.M. Mulder, The Interval Function of a Graph, in: Mathematical Centre Tracts, vol. 132, Amsterdam, 1980 · Zbl 0446.05039 |
| [45] | Polat, N., Fixed finite subgraph theorems in infinite weakly modular graphs, Discrete Math., 285, 239-256 (2004) · Zbl 1044.05036 |
| [46] | Prenowitz, W.; Jantosciak, J., Geometries and join spaces, J. Reine Angew. Math., 257, 100-128 (1972) · Zbl 0264.50002 |
| [47] | Sabidussi, G., Subdirect representations of graphs, infinite and finite sets, Colloq. Math. Soc. János Bolyai, 10, 1199-1226 (1973) · Zbl 0308.05124 |
| [48] | C.R. Shallen, Nonfinitely Based Binary Algebras Derived from Lattices, Ph.D. Thesis, University of California at Los Angeles, 1979; C.R. Shallen, Nonfinitely Based Binary Algebras Derived from Lattices, Ph.D. Thesis, University of California at Los Angeles, 1979 |
| [49] | Sholander, M., Trees, lattices, order, and betweenness, Proc. Amer. Math. Soc., 3, 369-381 (1952) · Zbl 0047.05401 |
| [50] | Sholander, M., Medians and betweenness, Proc. Amer. Math. Soc., 5, 801-807 (1954) · Zbl 0056.26101 |
| [51] | Sholander, M., Medians, lattices, and trees, Proc. Amer. Math. Soc., 5, 808-812 (1954) · Zbl 0056.26201 |
| [52] | Soltan, V.; Chepoi, V., Conditions for invariance of set diameters under \(d\)-convexification in a graph, Cybernetics, 19, 750-756 (1983) · Zbl 0564.05037 |
| [53] | Tardif, C., Prefibers and the cartesian product of metric spaces, Discrete Math., 109, 283-288 (1992) · Zbl 0777.05097 |
| [54] | Tardif, C., A fixed box theorem for the cartesian product of graphs and metric spaces, Discrete Math., 171, 237-248 (1997) · Zbl 0879.05067 |
| [55] | van de Vel, M., Matching binary convexities, Topology Appl., 16, 207-235 (1983) · Zbl 0543.52001 |
| [56] | van de Vel, M., Theory of Convex Structures (1993), Elsevier: Elsevier Amsterdam · Zbl 0785.52001 |
| [57] | H. Werner, Einführung in die allgemeine Algebra, Bibliographisches Institut, Mannheim, 1978; H. Werner, Einführung in die allgemeine Algebra, Bibliographisches Institut, Mannheim, 1978 · Zbl 0383.08001 |
| [58] | Wilkeit, E., The retracts of Hamming graphs, Discrete Math., 102, 197-218 (1992) · Zbl 0759.05085 |
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.
