2016/07/16 by Leonid Bunimovich, Bunimovich, Leonid, Pavel Skums +1
Computer Science · #05C10 (Primary) 05C62 #54F45 (Secondary) #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Digital Image Processing Techniques #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1607.04703
openalex publication_date 2016/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we introduce and study discrete analogues of Lebesgue and Hausdorff dimensions for graphs. It turned out that they are closely related to well-known graph characteristics such as rank dimension and Prague (or Nešetřil-Rödl) dimension. It allows us to formally define fractal graphs and establish fractality of some graph classes. We show, how Hausdorff dimension of graphs is related to their Kolmogorov complexity. We also demonstrate fruitfulness of this interdisciplinary approach by discovering a novel property of general compact metric spaces using ideas from hypergraphs theory and by proving an estimation for Prague dimension of almost all graphs using methods from algorithmic information theory.