Vandomme, Elise[Université de Liège > Département de mathématique > Mathématiques discrètes >]

7-Apr-2017

No

No

International

Combinatorics on Words and Tilings Workshop

from 2017-04-03 to 2017-04-07

Srecko Brlek, Wavier Provençal

Montréal

Canada

[en] covering codes ; coding theory ; infinite grid

[en] Covering problems are traditional issues in mathematics. For instance, a natural covering problem in the n-dimensional euclidean space is to ask for the minimal number of identical spheres needed to cover a large volume. The same issues can be considered in graphs. The corresponding covering problem is to determine the minimal number of r-balls that can be placed in such a way that every vertex of the graph is contained in at least one of them. In this talk, we consider coverings that satisfy special multiplicity conditions, called (r,a,b)-covering codes. These codes generalizes the notion of perfect codes in graphs that correspond to tilings of the graph with r-balls. We focus our attention on the multidimensional infinite grid and discuss the periodicity of (r,a,b)-codes in this case. Finally, for the dimension 2, we determine the possible values of the constant a and b.