2015/08/09 by Oliver Knill, Knill, Oliver · 3 citations
Computer Science · Mathematics · #05C50 #37Dxx #57M15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Mathematical Dynamics and Fractals #Spectral Theory (math.SP) #Topological and Geometric Data Analysis #cs.DM #math.CO #math.SP #msc:05C50 #msc:37Dxx #msc:57M15
paper · pdf · doi:10.48550/arxiv.1508.02027
20 pages 12 figures
arxiv created 2015/08/09 · openalex publication_date 2015/08/09 · arxiv updated 2015/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a finite simple graph G, let G' be its barycentric refinement: it is the graph in which the vertices are the complete subgraphs of G and in which two such subgraphs are connected, if one is contained into the other. If L(0)=0<L(1) <= L(2) ... <= L(n) are the eigenvalues of the Laplacian of G, define the spectral function F(x) as the function F(x) = L([n x]) on the interval [0,1], where [r] is the floor function giving the largest integer smaller or equal than r. The graph G' is known to be homotopic to G with Euler characteristic chi(G')=chi(G) and dim(G') >= dim(G). Let G(m) be the sequence of barycentric refinements of G=G(0). We prove that for any finite simple graph G, the spectral functions F(G(m)) of successive refinements converge for m to infinity uniformly on compact subsets of (0,1) and exponentially fast to a universal limiting eigenvalue distribution function F which only depends on the clique number respectively the dimension d of the largest complete subgraph of G and not on the starting graph G. In the case d=1, where we deal with graphs without triangles, the limiting distribution is the smooth function F(x) = 4 sin2(pi x/2). This is related to the Julia set of the quadratic map T(z) = 4z-z2 which has the one dimensional Julia set [0,4] and F satisfies T(F(k/n))=F(2k/n) as the Laplacians satisfy such a renormalization recursion. The spectral density in the d=1 case is then the arc-sin distribution which is the equilibrium measure on the Julia set. In higher dimensions, where the limiting function F still remains unidentified, F' appears to have a discrete or singular component.