# On distances and metrics in discrete ordered sets

Mathematica Bohemica (2021)

• Volume: 146, Issue: 3, page 251-262
• ISSN: 0862-7959

top

## Abstract

top
Discrete partially ordered sets can be turned into distance spaces in several ways. The distance functions may or may not satisfy the triangle inequality and restrictions of the distance to finite chains may or may not coincide with the natural, difference-of-height distance measured in a chain. It is shown that for semilattices the semimodularity ensures the good behaviour of the distances considered. The Jordan-Dedekind chain condition, which is weaker than semimodularity, is equivalent to the basic criterion that the graph-theoretic distance (realized by zig-zagging up and down freely in the poset to connect two points) is compatible with distances measured on chains by the relative height. Semimodularity is shown to be equivalent to the validity of the triangle inequality of a restricted graph-theoretic distance, called the up-down distance. The fact that the up-down distance corresponds to the computation of degrees of kinship in family trees leads to the observation that the less familiar canon-law method of computation corresponds also to a mathematically well behaved Chebyshev-type distance on discrete semilattices. For the Chebyshev distance also semimodularity is shown to imply the validity of the triangle inequality. The reverse implication fails, but assuming the validity of the triangle inequality, the semimodularity is shown to have a local characterization by a forbidden six-element subsemilattice. Like in the classical case of real spaces, the Chebyshev semilattice distance is shown to be the limit of a converging sequence of distances, all of them verifying the triangle inequality if the semilattice is semimodular.

## How to cite

top

Foldes, Stephan, and Radelecki, Sándor. "On distances and metrics in discrete ordered sets." Mathematica Bohemica 146.3 (2021): 251-262. <http://eudml.org/doc/297824>.

@article{Foldes2021,
abstract = {Discrete partially ordered sets can be turned into distance spaces in several ways. The distance functions may or may not satisfy the triangle inequality and restrictions of the distance to finite chains may or may not coincide with the natural, difference-of-height distance measured in a chain. It is shown that for semilattices the semimodularity ensures the good behaviour of the distances considered. The Jordan-Dedekind chain condition, which is weaker than semimodularity, is equivalent to the basic criterion that the graph-theoretic distance (realized by zig-zagging up and down freely in the poset to connect two points) is compatible with distances measured on chains by the relative height. Semimodularity is shown to be equivalent to the validity of the triangle inequality of a restricted graph-theoretic distance, called the up-down distance. The fact that the up-down distance corresponds to the computation of degrees of kinship in family trees leads to the observation that the less familiar canon-law method of computation corresponds also to a mathematically well behaved Chebyshev-type distance on discrete semilattices. For the Chebyshev distance also semimodularity is shown to imply the validity of the triangle inequality. The reverse implication fails, but assuming the validity of the triangle inequality, the semimodularity is shown to have a local characterization by a forbidden six-element subsemilattice. Like in the classical case of real spaces, the Chebyshev semilattice distance is shown to be the limit of a converging sequence of distances, all of them verifying the triangle inequality if the semilattice is semimodular.},
author = {Foldes, Stephan, Radelecki, Sándor},
journal = {Mathematica Bohemica},
keywords = {poset; semilattice; tree; semimodularity; chain condition; height; distance; metric; triangle inequality},
language = {eng},
number = {3},
pages = {251-262},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On distances and metrics in discrete ordered sets},
url = {http://eudml.org/doc/297824},
volume = {146},
year = {2021},
}

TY - JOUR
AU - Foldes, Stephan
TI - On distances and metrics in discrete ordered sets
JO - Mathematica Bohemica
PY - 2021
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 146
IS - 3
SP - 251
EP - 262
AB - Discrete partially ordered sets can be turned into distance spaces in several ways. The distance functions may or may not satisfy the triangle inequality and restrictions of the distance to finite chains may or may not coincide with the natural, difference-of-height distance measured in a chain. It is shown that for semilattices the semimodularity ensures the good behaviour of the distances considered. The Jordan-Dedekind chain condition, which is weaker than semimodularity, is equivalent to the basic criterion that the graph-theoretic distance (realized by zig-zagging up and down freely in the poset to connect two points) is compatible with distances measured on chains by the relative height. Semimodularity is shown to be equivalent to the validity of the triangle inequality of a restricted graph-theoretic distance, called the up-down distance. The fact that the up-down distance corresponds to the computation of degrees of kinship in family trees leads to the observation that the less familiar canon-law method of computation corresponds also to a mathematically well behaved Chebyshev-type distance on discrete semilattices. For the Chebyshev distance also semimodularity is shown to imply the validity of the triangle inequality. The reverse implication fails, but assuming the validity of the triangle inequality, the semimodularity is shown to have a local characterization by a forbidden six-element subsemilattice. Like in the classical case of real spaces, the Chebyshev semilattice distance is shown to be the limit of a converging sequence of distances, all of them verifying the triangle inequality if the semilattice is semimodular.
LA - eng
KW - poset; semilattice; tree; semimodularity; chain condition; height; distance; metric; triangle inequality
UR - http://eudml.org/doc/297824
ER -

## References

top
1. Bouchard, C. B., 10.2307/2846935, Speculum 56 (1981), 268-287. (1981) DOI10.2307/2846935
2. Burtsell, R., Canonical adoption, The Catholic Encyclopedia Vol. 1 Robert Appleton Company, New York (1907). Available at http://www.newadvent.org/cathen/01147b.htm.
3. Chartrand, G., Johns, G. L., Tian, S., Winters, S. J., 10.1002/jgt.3190170408, J. Graph Theory 17 (1993), 509-521. (1993) Zbl0781.05018MR1231014DOI10.1002/jgt.3190170408
4. Deza, M. M., Panteleeva, E., 10.1006/eujc.1999.0383, Eur. J. Comb. 21 (2000), 777-795. (2000) Zbl0966.52010MR1791206DOI10.1006/eujc.1999.0383
5. Foldes, S., Woodroofe, R., 10.1007/s11083-012-9248-2, Order 30 (2013), 351-361. (2013) Zbl1282.06009MR3063192DOI10.1007/s11083-012-9248-2
6. Garner, B. A., A Dictionary of Modern Legal Usage, Oxford University Press, Oxford (2001). (2001)
7. Haskins, L., Gudder, S., 10.1016/0012-365X(72)90014-3, Discrete Math. 2 (1972), 357-382. (1972) Zbl0238.06002MR0306059DOI10.1016/0012-365X(72)90014-3
8. Kharat, V. S., Waphare, B. N., Thakare, N. K., 10.1007/s00012-004-1851-7, Algebra Univers. 51 (2004), 111-124. (2004) Zbl1079.06006MR2067152DOI10.1007/s00012-004-1851-7
9. Monjardet, B., 10.1016/0012-365X(81)90206-5, Discrete Math. 35 (1981), 173-184. (1981) Zbl0463.46016MR0620670DOI10.1016/0012-365X(81)90206-5

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.