Cargando…
Shannon Entropy of Ramsey Graphs with up to Six Vertices
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 accordi...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2023
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10606126/ https://www.ncbi.nlm.nih.gov/pubmed/37895548 http://dx.doi.org/10.3390/e25101427 |
_version_ | 1785127241007497216 |
---|---|
author | Frenkel, Mark Shoval, Shraga Bormashenko, Edward |
author_facet | Frenkel, Mark Shoval, Shraga Bormashenko, Edward |
author_sort | Frenkel, Mark |
collection | PubMed |
description | 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 [Formula: see text]-colored polygons with n α-sides or edges, and the fraction of monochromatic [Formula: see text]-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 [Formula: see text] and [Formula: see text] are interpreted as follows: [Formula: see text] is interpreted as an average uncertainty to find the green [Formula: see text] polygon in the given graph; [Formula: see text] is, in turn, an average uncertainty to find the red [Formula: see text] 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. |
format | Online Article Text |
id | pubmed-10606126 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-106061262023-10-28 Shannon Entropy of Ramsey Graphs with up to Six Vertices Frenkel, Mark Shoval, Shraga Bormashenko, Edward Entropy (Basel) Article 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 [Formula: see text]-colored polygons with n α-sides or edges, and the fraction of monochromatic [Formula: see text]-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 [Formula: see text] and [Formula: see text] are interpreted as follows: [Formula: see text] is interpreted as an average uncertainty to find the green [Formula: see text] polygon in the given graph; [Formula: see text] is, in turn, an average uncertainty to find the red [Formula: see text] 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. MDPI 2023-10-09 /pmc/articles/PMC10606126/ /pubmed/37895548 http://dx.doi.org/10.3390/e25101427 Text en © 2023 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Frenkel, Mark Shoval, Shraga Bormashenko, Edward Shannon Entropy of Ramsey Graphs with up to Six Vertices |
title | Shannon Entropy of Ramsey Graphs with up to Six Vertices |
title_full | Shannon Entropy of Ramsey Graphs with up to Six Vertices |
title_fullStr | Shannon Entropy of Ramsey Graphs with up to Six Vertices |
title_full_unstemmed | Shannon Entropy of Ramsey Graphs with up to Six Vertices |
title_short | Shannon Entropy of Ramsey Graphs with up to Six Vertices |
title_sort | shannon entropy of ramsey graphs with up to six vertices |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10606126/ https://www.ncbi.nlm.nih.gov/pubmed/37895548 http://dx.doi.org/10.3390/e25101427 |
work_keys_str_mv | AT frenkelmark shannonentropyoframseygraphswithuptosixvertices AT shovalshraga shannonentropyoframseygraphswithuptosixvertices AT bormashenkoedward shannonentropyoframseygraphswithuptosixvertices |