|
David Avis, McGill University, Computer Science, 3480 University St., Montréal, Québec, Canada, H3A 2A7
Hypermetric inequalities are a natural generalization of the triangle inequalities, and have been rediscovered many times. They find application, for example, in combinatorial optimization, geometry, physics and statistics. However, many very basic questions regarding them remain open.
In this talk I will give a survey of what is known about hypermetric inequalities, and a sketch of how they are applied. In particular I will describe how they are useful in solving the problem of finding a maximum edge cut in a graph and in deciding the embeddability of point sets in space, with prescribed L1
distances. I will discuss some of the interesting open problems surrounding these beautiful inequalities.
|