Reference : Contributions to combinatorics on words in an abelian context and covering problems i...
Dissertations and theses : Doctoral thesis
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/176364
Contributions to combinatorics on words in an abelian context and covering problems in graphs
English
[fr] Contributions à la combinatoire des mots dans un contexte abélien et problèmes de couverture dans les graphes
Vandomme, Elise mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
7-Jan-2015
Université de Liège, ​Liège, ​​Belgique
Université de Grenoble, ​Grenoble, ​​France
Docteur de l'Université de Grenoble - Docteur en Sciences de l'Université de Liège
x, 194 + 52
Rigo, Michel mailto
Gravier, Sylvain mailto
Lecomte, Pierre mailto
Berthé, Valérie mailto
Cara, Philippe mailto
Duchêne, Eric mailto
Sopena, Eric mailto
[en] combinatorics on words ; l-abelian equivalence ; regularity ; abelian return words ; Sturmian words ; graph theory ; identifying codes ; vertex-transitive graphs ; generalized quadrangles ; covering codes ; infinite grid ; codes identifiants ; graphes sommet-transitifs ; quadrangles généralisés ; codes couvrants ; grille infinie
[fr] combinatoire des mots ; équivalence l-abélienne ; régularité ; mot de retour abélien ; mots sturmiens ; théorie des graphes
[en] This thesis dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter.

In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results.

The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue--Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set.

In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^a with a in {1/4,1/3,2/5}.

The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich.
[fr] Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre.

En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité.

Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble.

En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^a avec a dans {1/4,1/3,2/5}.

Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'Axenovich.
http://hdl.handle.net/2268/176364
Joint PhD

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
these_vandomme_2015.pdfAuthor postprint3.79 MBView/Open

Additional material(s):

File Commentary Size Access
Open access
these_defense_vandomme.pdfBeamer2.48 MBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.