This thesis comprises three apparently very independent parts. However, there is a unity behind I would like to sketch very briefly.
Formally graphs are in the background of most chapters and so is the duality local versus global. The first section is concerned with globally coloring graphs under some local assumptions. Algorithmically it is an intrinsically difficult task and neural networks, the topic of the second part can be used to approach intractable problems. Simple local interactions with emergent collective behavior are one of the essential features of these networks. Their current models are similar to some of those encountered in statistical mechanics, like spin glasses. In the third part, we study ultrametricity, a concept recently rediscovered by theoretical physicists in the analysis of spin-glasses. Ultrametricity can be expressed as a local constraint on the shape of each triangle of the given metric space.
Unless otherwise stated, results in the first and second part are essentially original. Since the third part represents a joint work with Michael Aschbacher, Eric Baum and Richard Wilson, I should perhaps try to outline my contribution though paternity of collective results is somewhat fuzzy. While working on neural networks and spin glasses Eric and I got interested in ultrametricity. Several of us had found an initial polynomial upper bound, but the final results of "n + 1" was first reached independently by Michael and Richard. I think I obtained the theorems: 4.5, 6.1, 6.3 (using an idea of Eric), 6.4, 6.5, 6.6, 6.7 (with Richard and helpful references from Bruce Rothschild and Olga Taussky) and participated in some other results.
