Shannon Entropy of Ramsey Graphs
Edward Yu. Bormashenko, Mark Frenkel, Shraga Shoval · Preprints.org · 2023
Shannon entropy quantifying bi-colored Ramsey complete graphs is introduced. Complete graphs in which vertices are connected with two types of links, labeled as α-links and β-links are considered. Shannon-entropy is introduced according to the classical Shannon formula considering the fractions of monochromatic convex α-colored polygons with n α-sides or edges, and the fraction of monochromatic β-colored convex polygons with m β-sides in the given complete graph. Introduced Shannon entropy is insensitive to the exact shape of the graph, but it is sensitive to the distribution of monochromatic polygons in a given graph. The introduced Shannon Entropies Sα and Sβ are interpreted as follows: Sα is interpreted as an average uncertainty to find the green α-polygon in the given graph, Sβ is, in turn, an average uncertainty to find the red β-polygon in the same graph. The re-shaping of the Ramsey theorem in terms of the Shannon Entropy is suggested. Various measures quantifying the Shannon Entropy of the entire complete bi-colored graphs are suggested. Physical interpretations of the suggested Shannon Entropies are discussed.