Collected results on semigroups, graphs and codes

Abstract

In this thesis we present a compendium of _ve works where discrete mathematics play a key role. The _rst three works describe di_erent developments and applications of the semigroup theory while the other two have more independent topics. First we present a result on semigroups and code e_ciency, where we introduce our results on the so-called Geil-Matsumoto bound and Lewittes' bound for algebraic geometry codes. Following that, we work on semigroup ideals and their relation with the Feng-Rao numbers; those numbers, in turn, are used to describe the Hamming weights which are used in a broad spectrum of applications, i.e. the wire-tap channel of type II or in the t-resilient functions used in cryptography. The third work presented describes the non-homogeneous patterns for semigroups, explains three di_erent scenarios where these patterns arise and gives some results on their admissibility. The last two works are not as related as the _rst three but still use discrete mathematics. One of them is a work on the applications of coding theory to _ngerprinting, where we give results on the traitor tracing problem and we bound the number of colluders in a colluder set trying to hack a _ngerprinting mark made with a Reed-Solomon code. And _nally in the last work we present our results on scientometrics and graphs, modeling the scienti_c community as a cocitation graph, where nodes represent authors and two nodes are connected if there is a paper citing both authors simultaneously. We use it to present three new indices to evaluate an author's impact in the community.