Generalizaciones de la fórmula de Graham-Pollak. Una prueba combinatoria.

Abstract

A famous formula of Graham and Pollak (1971) describes the determinant of the distance matrix of a tree T of order n: detM(T) = (−1)n−1(n − 1)2n−2. Remarkably, this formula shows that the value of this determinant only depends on n, the number of vertices of T, and not on its tree structure. In this senior thesis, we present a long sought after combinatorial proof for the elegant formula of Graham and Pollak. Moreover, we show how our framework can be used to derive combinatorially many of its existing generalizations, and even to obtain suggestions for new ones.

Una famosa fórmula de Graham y Pollak (1971) describe el determinante de la distancia matriz de un árbol T de orden n. detM(T) = (−1)n−1(n − 1)2n−2. Sorprendentemente, esta fórmula revela que el valor de este determinante solo depende de n, su número de vértices, pero no de la estructura del árbol. En este trabajo de fin de grado presentamos la tan buscada prueba combinatoria de la elegante fórmula de Graham y Pollak. Además, mostramos como nuestro marco de trabajo puede usarse para derivar combinatoriamente varias de sus generalizaciones e, incluso, sugerir otras nuevas.