LQ placeholderPoint, line, square, cube, tesseract

Point, line, square, cube, tesseract

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

Background In information theory, messages are sent as strings of characters which are subject to errors in transmission or copying. If we take the distance between two strings to be the number of spelling mistakes between them, then the space defined by this distance function is a Hamming graph over all possible strings. To correct for mistakes, a string and its variants must all code for the same message, and this bundle of strings forms a subgraph of a Hamming graph.

Project Biological information is carried by strings of nucleotides or amino acids. Point mutations correspond to traversing an edge in the associated Hamming graph. But not every genetic change affects an organism, so genetic space (the Hamming graph of all genotypes) is split up into subgraphs called neutral networks, each representing a distinct phenotype, or message. We investigate bounds on the spectral radius of subgraphs of Hamming graphs, which directly relate to the robustness and number of allowable phenotypes.

Consequences The theory of neutral evolution is only one application of the properties of subgraphs of Hamming graphs. Understanding how to pack Hamming balls into a Hamming graph is at the heart of many error correcting codes, and Hamming graphs feature in association schemes in coding theory.

LQ placeholder

< Previous

LQ placeholder

Next >