An Entropy-Based Proof for the Moore Bound for Irregular Graphs

摘要

We provide proofs of the following theorems by considering the entropy of random walks. Theorem 1 (Alon, Hoory and Linial) Let G be an undirected simple graph with n vertices, girth g, minimum degree at least 2 and average degree d. Odd girth If g = 2r + 1, then n ≥ 1 + d (r-1) ∑ (i=0)(d - 1)~i. Even girth If g = 2r, then n ≥ 2 (r-1) ∑ (i=0) (d - 1)~i. Theorem 2 (Hoory) Let G = (V_L, V_R, E) be a bipartite graph of girth g = 2r, with n_L = |V_L| and n_R = |V_R|, minimum degree at least 2 and the left and right average degrees d_L and d_R. Then, n_L ≥ (r-1) ∑ (i=0) (d_R-1)~(「i/2(」)) (d_L-1)~((「)i/2」), n_R ≥ (r-1) ∑ (i=0) (d_L-1)~(「i/2(」)) (d_R-1)~((「)i/2」).