On the discrete heat equation and Kolmogorov's complexity theory

Abstract

In this thesis we study the heat equation on graphs from the perspective of information theory. To this end, we introduce the discrete heat equation using the probabilistic approach of random walks on graphs. Then we present a basic introduction to the subject of information theory, both from a probabilistic and an algorithmic viewpoint. Here we define the concepts of Shannon entropy, Kolmogorov complexity and mutual information; and we use codes to give an interpretation of them. As an application, we show how random walks on graphs allow us to gain information about different graph parameters. Moreover, we use the heat diffusion process on a graph as a computational mechanism to approximate the Fourier expansion of a function defined on a finite abelian group.

En esta tesis estudiamos la ecuación del calor en grafos desde la perspectiva de la teoría de la información. Para ello, introducimos la ecuación del calor discreta utilizando el enfoque probabilístico de las caminatas aleatorias en grafos. Luego presentamos una introducción básica a la teoría de la información, tanto desde el punto de vista probabilístico como el algorítmico. Aquí definimos los conceptos de entropía de Shannon, complejidad de Kolmogorov e información mutua; y utilizamos códigos para dar una interpretación de los mismos. Como aplicación, mostramos cómo las caminatas aleatorias en grafos nos permiten obtener información sobre diferentes parámetros de ciertos grafos. Además, utilizamos el proceso de difusión de calor en un grafo como un mecanismo de cálculo para aproximar la expansión de Fourier de una función definida en un grupo abeliano finito.