APLICAÇÃO DO MÉTODO DA ENTROPIA EM COMBINATÓRIA

Abstract

O conceito de entropia, no contexto da Teoria da Informação, foi criado em 1948, por Claude Shannon. Essencialmente, a entropia de uma variável aleatória X é uma medida do nível médio de surpresa ou de aleatoriedade associado aos possíveis resultados de X. De forma precisa, sendo X uma variável aleatória e denotando a probabilidade Pr({X=x}) por p(x), a entropia de X é definida como H(X) = sum_{x} p(x).log[1/p(x)], onde x varia em range(X) (o conjunto de valores que X pode tomar com probabilidade positiva) e log está na base 2. Nesse contexto, uma propriedade da entropia que é particularmente útil em Combinatória é a chamada “maximalidade na distribuição uniforme", segundo a qual, H(X) = log |range(X)|, quando X é uma variável aleatória uniforme em range(X). Diante disso, se desejamos estimar o tamanho de um conjunto C, podemos definir uma variável aleatória X que toma valores uniformemente e com probabilidade positiva em C, de forma que a propriedade citada nos garante que |C|=2^H(X). Assim, a tarefa de estimar |C| se resume a estimar H(X). Neste trabalho, serão apresentadas propriedades úteis na estimativa da entropia, como sua subaditividade, o Lema de Shearer e a regra da cadeia para entropia condicional. Além disso, será mostrada a resolução de um problema de Combinatória usando o conceito de entropia e suas propriedades. O estudo da utilização da entropia em Combinatória teve como motivação a expectativa da aplicação deste método na contagem de colorações de Gallai (colorações de arestas em que nenhum conjunto de três arestas adjacentes entre si recebe mais do que duas cores) em grafos completos, levando em conta um resultado de János Körner e Gábor Simonyi que estabelece uma caracterização envolvendo entropia de grafos e colorações de Gallai de um certo tipo. Isto será desenvolvido em trabalhos futuros.