• Senior Thesis
• Department of Mathematics
• Harvey Mudd College

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 math.hmc.edu

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.