LQ placeholderPoint, line, square, cube, tesseract

Point, line, square, cube, tesseract

Exploring the spectral properties of subgraphs of the hypercube and Hamming graphs for insights into coding theory and models of evolution.

In information theory, messages are sent as strings which are subject to errors in transmission. When the distance between two strings is the number of spelling mistakes between them, the space defined by this distance is a Hamming graph (or hypercube when the string is binary). To correct for errors in transmission, variants of a string must code for the same message as the string itself. In this way error correction is deeply connected to partitioning the Hamming graph into compact clusters.

In this project, we investigate the spectral properties of subgraphs of the hypercube and Hamming graphs.
By studying a population on these graphs that diffuses via point mutations, we develop an analogy between mutational robustness and the eigenvalues of subgraphs that code for the same phenotype.

The spectral theory of Hamming graphs has direct applications to the theory of neutral evolution, in which biological information is carried by strings of nucleotides or amino acids. It is also at the heart of Hamming and other error correcting codes, and Hamming graphs feature in association schemes in coding theory.