1999/01/01 by Tromp, J., Buhrman, H.M., Li, M. +4 · 1 citation
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Graph theory and applications #Mathematical Dynamics and Fractals #advanced mathematical theories
paper · doi:10.1137/s0097539797327805
openalex publication_date 1999/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency (how far it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.