×

Superextensions and the depth of median graphs. (English) Zbl 0756.05091

Authors’ abstract: An invariant of convex structures — the depth — is used to study the structure of finite median graphs. The main result is a recursive description of graphs of given depth. This leads to a complete description of the cubical structure of the superextension \(\lambda(\mathbf{5})\) and to a (less complete) description of superextensions \(\lambda({\mathbf r})\) for \(r>5\). An important tool is the construction of certain graphs \(p({\mathbf r})\) of linked bipartitions of the \(r\)-point set \({\mathbf r}\). For each \(r\geq 3\), the graphs \(\lambda({\mathbf r})\) and \(p({\mathbf r})\) have the same number of vertices, but they are isomorphic (modulo extreme points) for \(r\leq 5\) only.

MSC:

05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bandelt, H.-J., Tolerances on median algebras, Czechoslovak Math. J., 33, No. 108, 344-347 (1983) · Zbl 0538.08003
[2] Bandelt, H.-J.; Hedli´kova´, J., Median algebras, Discrete Math., 45, 1-30 (1983) · Zbl 0506.06005
[3] Bandelt, H.-J.; Prisner, E., Clique graphs and Helly graphs (1987), preprint
[4] Bandelt, H.-J.; van de Vel, M., Embedding topological median algebras in products of dendrons, (Proc. London Math. Soc., 58 (1989)), 439-453, (3) · Zbl 0682.05031
[5] Eckhoff, J., Der Satz von Radon in konvexen Produktstrukturen II, Monatsh. Math., 73, 7-30 (1969) · Zbl 0174.53701
[6] Erdo˝s, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford (2), 12, 313-320 (1961) · Zbl 0100.01902
[7] Escalante, F., U¨ber iterierte Clique-Graphen, Abh. Math. Sem. Univ. Hamburg, 39, 59-68 (1973) · Zbl 0266.05116
[8] Isbell, J. R., Median algebra, Trans. Amer. Math. Soc., 260, 319-362 (1980) · Zbl 0446.06007
[9] Jamison, R. E., A General Theory of Convexity, (Dissertation (1974), Univ. of Washington: Univ. of Washington Seattle) · Zbl 0282.28001
[10] van Mill, J., Supercompactness and Wallman spaces, (Math. Centre Tracts, Vol. 85 (1977)), Amsterdam · Zbl 0407.54001
[11] Monjardet, B., Ele´ments ipsoduaux du treillis distributif libre et familles de Sperner ipsotransversales, J. Combin. Theory, 19, 160-176 (1975) · Zbl 0322.06013
[12] Mulder, H. M., The interval function of a graph, (Math. Centre Tracts, Vol. 132 (1980)), Amsterdam · Zbl 0446.05039
[13] Quilliot, A., On the Helly property working as a compactness criterion on graphs, J. Combin. Theory Ser. A, 40, 186-193 (1985) · Zbl 0575.05026
[14] Sierksma, G., Axiomatic Convexity Theory and the Convex Product Space, (Dissertation (1976), Univ. of Groningen) · Zbl 0336.52001
[15] Sholander, M., Medians, lattices, and trees, (Proc. Amer. Math. Soc., 5 (1954)), 808-812 · Zbl 0056.26201
[16] van de Vel, M., Superextensions and Lefschetz fixed point structures, Fund. Math., 104, 27-42 (1979) · Zbl 0423.54014
[17] van de Vel, M., Pseudo-boundaries and pseudo-interiors for topological convexities, Dissertationes Math. (Rozprawy Mat.), 210, 1-72 (1983) · Zbl 0528.52004
[18] van de Vel, M., Finite dimensional convex structures. II. The invariants, Topology Appl., 16, 81-105 (1983) · Zbl 0556.52001
[19] van de Vel, M., Matching binary convexities, Topology Appl., 16, 207-235 (1983) · Zbl 0543.52001
[20] van de Vel, M., Binary convexities and distributive lattices, (Proc. London Math. Soc., 48 (1984)), 1-33, (3) · Zbl 0505.06005
[21] Verbeek, A., Superextensions of topological spaces, (Math. Centre Tracts, Vol. 41 (1972)), Amsterdam · Zbl 0256.54014
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.