New Bound for Classical Zero-Error Capacity using Partially Commutative Monoids as Counting Tools

Andresso da Silva, Francisco M. Assis

DOI: 10.14209/sbrt.2023.1570922082

Evento: XLI Simpósio Brasileiro de Telecomunicações e Processamento de Sinais (SBrT2023)

Keywords: Partially Commutative Monoid Zero-Error Capacity Partial Order

Abstract

In this paper we propose a new bound for the classical zero-error capacity of a communication channel using partially commutative monoids as enumeration tools. Specifically, we analyze the relationship between classical zero-error capacity and the growth factor of the monoid, \(\beta(G)\), of a graph \(G\). Although the value of \(\beta(G)\) allows us to calculate an upper bound for the classical zero-error capacity, determining it requires counting the number of cliques in a graph, which is an NP-Complete problem. Our main result is that the classical zero-error capacity is always lower than the integer part of \(\beta(G)\).

Download