John D. Hearn

Harvey Mudd College Mathematics 2006

Thesis Proposal: Kolmogorov Complexity of Graphs
Mid-year Report: Kolmogorov Complexity of Unlabeled Graphs
Presentation Poster: Kolmogorov Complexity and Graphs
Thesis Advisor: Prof. Ran Libeskind-Hadas
Second Reader: Prof. Michael E. Orrison
E-Mail: jhearn at

Kolmogorov Complexity of Unlabeled Graphs

Kolmogorov complexity is a theory based on the premise that the complexity of a binary string can be measured by its compressibility; that is, a string's complexity is the length of the shortest program that produces that string. We explore applications of this measure to graph theory.