Blog
About

1
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      New lower bound on the Shannon capacity of C7 from circular graphs

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We give an independent set of size \(367\) in the fifth strong product power of \(C_7\), where \(C_7\) is the cycle on \(7\) vertices. This leads to an improved lower bound on the Shannon capacity of \(C_7\): \(\Theta(C_7)\geq 367^{1/5} > 3.2578\). The independent set is found by computer, using the fact that the set \(\{t \cdot (1,7,7^2,7^3,7^4) \,\, | \,\, t \in \mathbb{Z}_{382}\} \subseteq \mathbb{Z}_{382}^5\) is independent in the fifth strong product power of the circular graph \(C_{108,382}\). Here the circular graph \(C_{k,n}\) is the graph with vertex set \(\mathbb{Z}_{n}\), the cyclic group of order \(n\), in which two distinct vertices are adjacent if and only if their distance (mod \(n\)) is strictly less than \(k\).

          Related collections

          Most cited references 6

          • Record: found
          • Abstract: not found
          • Article: not found

          The zero error capacity of a noisy channel

           C Shannon (1956)
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            On the Shannon capacity of a graph

             L Lovász (1979)
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              On Some Problems of Lovász Concerning the Shannon Capacity of a Graph

               W. Haemers (1979)
                Bookmark

                Author and article information

                Journal
                22 August 2018
                Article
                1808.07438

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                05C69, 94A24
                5 pages
                math.CO cs.IT math.IT

                Numerical methods, Combinatorics, Information systems & theory

                Comments

                Comment on this article