Shannon Capacity

Let  denote the independence number of a graph . Then the Shannon capacity , sometimes also denoted , of  is defined as

{{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]...□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]G_()_(k))]^(1/k), " src="https://mathworld.wolfram.com/images/equations/ShannonCapacity/NumberedEquation1.svg" style="height:54px; width:216px" />

where {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]" src="https://mathworld.wolfram.com/images/equations/ShannonCapacity/Inline6.svg" style="height:22px; width:14px" /> denoted the graph strong product (Shannon 1956, Alon and Lubetzky 2006). The Shannon capacity is an important information theoretical parameter because it represents the effective size of an alphabet in a communication model represented by a graph  (Alon 1998).

 satisfies

The Shannon capacity is in general very difficult to calculate (Brimkov et al. 2000). In fact, the Shannon capacity of the cycle graph  was not determined as  until 1979 (Lovász 1979), and the Shannon capacity of  is perhaps one of the most notorious open problems in extremal combinatorics (Bohman 2003).

Lovász (1979) showed that the Shannon capacity of the -Kneser graph is , that of a vertex-transitive self-complementary graph (which includes all Paley graphs)  is , and that of the Petersen graph is 4.

All graphs whose Shannon capacity is known attain their capacity either at  (i.e., at their independence number; e.g., perfect graphs),  (e.g., self-complementary vertex-transitive graphs-including the Paley graphs), or else do not attain it at any value of  (e.g., the graph union of the cycle graph  with a singleton graph) (Alon and Lubetzky 2006).

---

REFERENCES

Alon, N. "Explicit Ramsey Graphs and Orthonormal Labelings." Elec. J. Combin. 1, No. R12, 1-8, 1994.

Alon, N. "The Shannon Capacity of a Union." Combinatorica 18, 301-310, 1998.

Alon, N. and Lubetzky, E. "The Shannon Capacity of a Graph and the Independence Numbers of Its Powers." IEEE Trans. Inform. Th. 52, 2172-2176, 2006.

Bohman, T. "A Limit Theorem for the Shannon Capacities of Odd Cycles. I." Proc. Amer. Math. Soc. 131, 3559-3569, 2003.

Bohman, T. and Holzman, R. "A Nontrivial Lower Bound on the Shannon Capacities of the Complements of Odd Cycles." IEEE Trans. Inform. Th. 49, 721-722, 2003.

Brimkov, V. E.; Codenotti, B.; Crespi, V.; and Leoncini, M. "On the Lovász Number of Certain Circulant Graphs." In Algorithms and Complexity. Papers from the 4th Italian Conference (CIAC 2000) Held in Rome, March 1-3, 2000 (Ed. G. Bongiovanni, G. Gambosi, and R. Petreschi). Berlin: Springer-Verlag, pp. 291-305, 2000.

Haemers, W. "An Upper Bound for the Shannon Capacity of a Graph." In Algebraic Methods in Graph Theory. Szeged, Hungary: pp. 267-272, 1978.

Haemers, W. "On Some Problems of Lovász Concerning the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. 25, 231-232, 1979.

Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.Lovász, L. "On the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. IT-25, 1-7, 1979.

Riis, S. "Graph Entropy, Network Coding and Guessing." 27 Nov 2007. http://arxiv.org/abs/0711.4175v1.

Schrijver, A. "A Comparison of the Delsarte and Lovász Bounds." IEEE Trans. Inform. Th. 25, 425-429, 1979.

Shannon, C. E. "The Zero-Error Capacity of a Noisy Channel." IRE Trans. Inform. Th. 2, 8-19, 1956.van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1992.

اخر الاخبار

اخبار العتبة العباسية المقدسة

المجمع العلمي يواصل إقامة مسابقة الثقلين القرآنية لطلبة مدارس كربلاء

عضو مجلس إدارة العتبة العباسية المقدسة يطلع على آليات تطوير البرامج التعليمية في مجموعة العميد

مجموعة مناحل الكفيل تختتم مشاركتها في معرض السليمانية الدولي للزراعة والصناعات الغذائية

لتوثيق التراث العلمي.. وفد قسم شؤون المعارف يلتقي عددًا من أعلام مدينة النجف

المزيد

الآخبار الصحية

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ7 طرق بسيطة

لتحسين الهضم والتحكم في الشهية.. ما أفضل وقت لتناول التمر؟

خبراء يكشفون تأثير الاستحمام في الظلام على جودة النوم !

المزيد

الآخبار التكنلوجية

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

نظائر الهيليوم مقياس لاكتشاف رواسب الذهب.. كيف ذلك؟

الصين تطلق أول ناقلة نفط خام ذكية في العالم تعمل بالميثانول

الزمن على المريخ أسرع من الأرض.. دراسة علمية تكشف الفوارق

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength