Cartesian products of graphs and metric spaces
by
Dmitry Fon-Der-Flaass
Sobolev Institute of Mathematics, Novosibirsk, Russia
Coauthors: Sergey Avgustinovich (Sobolev Institute of Mathematics)

We prove uniqueness of decomposition of a finite metric space into a product of metric spaces for a wide class of product operations. In particular, this gives the positive answer to the long-standing question of S.Ulam [1, Problem 77(b)] and [2]: Ïf U+AFw-times U+AFw-simeq V+AFw-times V with U, V compact metric spaces, will then U and V be isometric?" in the case of finite metric spaces.

In the proof we use uniqueness of cartesian decomposition of connected graphs; a known fact to which we give a new proof which is shorter and more transparent than existing ones (cf. for instance [3]).

References:

[1] R.D. Maudlin (ed.), The Scottish Book, Birkhauser, 1981.

[2] M. Moszy+AFw-'nska, On the uniqueness problem for metric products, Glasnik Matematicki 27(47) (1992), 145-158.

[3] V.G.Vizing, The cartesian product of graphs. Vychisl. Sistemy 9 (1963), 30-43. (English translation: Electron. Comput. System, 2 (1966), 352-365.

The work of Avgustinovich was partially supported by grant 1792 of the Universities of Russia - Fundamental Research Program. The work of Fon-Der-Flaass was partially supported by grant 99-01-00581 of the Russian Foundation for Basic Research

Date received: February 22, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadw-39.