We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Shannon Entropy of Ramsey Graphs with up to Six Vertices.
- Authors
Frenkel, Mark; Shoval, Shraga; Bormashenko, Edward
- Abstract
Shannon entropy quantifying bi-colored Ramsey complete graphs is introduced and calculated for complete graphs containing up to six vertices. 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. The introduced Shannon entropy is insensitive to the exact shape of the polygons, but it is sensitive to the distribution of monochromatic polygons in a given complete 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. Generalization for multi-colored complete graphs is proposed. Various measures quantifying the Shannon entropy of the entire complete bi-colored graphs are suggested. Physical interpretations of the suggested Shannon entropies are discussed.
- Subjects
UNCERTAINTY (Information theory); COMPLETE graphs; POLYGONS; RAMSEY numbers
- Publication
Entropy, 2023, Vol 25, Issue 10, p1427
- ISSN
1099-4300
- Publication type
Article
- DOI
10.3390/e25101427