Kolmogorov Complexity of Graphs

Author

John Hearn, Harvey Mudd College

Graduation Year

2006

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science

Department

Mathematics

Reader 1

Ran Libeskind-Hadas

Reader 2

Michael Orrison

Abstract

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.

Recommended Citation

Hearn, John, "Kolmogorov Complexity of Graphs" (2006). HMC Senior Theses. 182.
https://scholarship.claremont.edu/hmc_theses/182