References of "Vandomme, Elise"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailConstant 2-labellings and an application to (r,a,b)-covering codes
Vandomme, Elise ULg; Gravier, Sylvain

in Discussiones Mathematicae Graph Theory (in press)

We introduce the concept of constant 2-labelling of a vertex-weighted graph and show how it can be used to obtain perfect weighted coverings. Roughly speaking, a constant 2-labelling of a vertex-weighted ... [more ▼]

We introduce the concept of constant 2-labelling of a vertex-weighted graph and show how it can be used to obtain perfect weighted coverings. Roughly speaking, a constant 2-labelling of a vertex-weighted graph is a black and white colouring of its vertex set which preserves the sum of the weights of black vertices under some automorphisms. We study constant 2-labellings on four types of vertex-weighted cycles. Our results on cycles allow us to determine (r, a, b)-codes in Z^2 whenever |a−b|>4, r>1 and we give the precise values of a and b. This is a refinement of Axenovich’s theorem proved in 2003. [less ▲]

Detailed reference viewed: 17 (2 ULg)
Full Text
See detailHow to count leaves in the trees from Tetris?
Vandomme, Elise ULg

Conference (2017, May 13)

In the world derived from the game Tetris, what is a tree? How many leaves can such a tree can have? What happens if instead, we consider the world derived from the game Minecraft? Can we generalise this ... [more ▼]

In the world derived from the game Tetris, what is a tree? How many leaves can such a tree can have? What happens if instead, we consider the world derived from the game Minecraft? Can we generalise this problem in other worlds? Does there exist an efficient algorithm to determine the maximal number of leaves a tree can have? These are the questions we will answer in this talk, using the point of view of graph theory. To determine the complexity of the problem, we will use some dynamical programming. [less ▲]

Detailed reference viewed: 15 (4 ULg)
Full Text
See detailOn a conjecture about regularity and l-abelian complexity
Vandomme, Elise ULg

Conference (2017, April 25)

A natural generalization of automatic sequences over an infinite alphabet is given by the notion of k-regular sequences, introduced by Allouche and Shallit in 1992. The k-regularity of a sequence provides ... [more ▼]

A natural generalization of automatic sequences over an infinite alphabet is given by the notion of k-regular sequences, introduced by Allouche and Shallit in 1992. The k-regularity of a sequence provides us with structural information about how the different terms are related to each other. We show that a sequence satisfying a certain symmetry property is 2-regular. We apply this theorem to develop a general approach for studying the l-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue–Morse word have 2-abelian complexity sequences that are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that can be used to obtain additional regularity results. This supports the conjecture that the l-abelian complexity of a $k$-automatic sequence is a k-regular sequence. [less ▲]

Detailed reference viewed: 10 (2 ULg)
See detailMathématiques en Action; Interview à la radio CHOQ de l'Université du Québec à Montréal
Vandomme, Elise ULg

Speech/Talk (2017)

Les mathématiques nous paraissent bien souvent abstraites et elles ne vont certainement pas aider à trouver vos oeufs de Pâques... Avec Elise Vandomme, nous explorons les théories mathématiques qui ... [more ▼]

Les mathématiques nous paraissent bien souvent abstraites et elles ne vont certainement pas aider à trouver vos oeufs de Pâques... Avec Elise Vandomme, nous explorons les théories mathématiques qui permettent de placer nos antennes de communication ou... des détecteurs d'oeufs de Pâques ! [less ▲]

Detailed reference viewed: 11 (1 ULg)
Full Text
See detailCovering codes
Vandomme, Elise ULg

Conference (2017, April 07)

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 15 (2 ULg)
See detailSous-arbres induits pleinement feuillus : résultats de complexité
Vandomme, Elise ULg

Conference (2017, January 23)

Dans les 30 dernières années, les polyominos ont été l'objet de nombreuses investigations. Un problème central, qui est pourtant toujours ouvert, est de déterminer le nombre de polyominos à n cellules ... [more ▼]

Dans les 30 dernières années, les polyominos ont été l'objet de nombreuses investigations. Un problème central, qui est pourtant toujours ouvert, est de déterminer le nombre de polyominos à n cellules carrées. Une approche possible de ce problème est d'utiliser une description combinatoire. Derrière chaque polyomino se cache un graphe dont les sommets correspondent aux cellules, tel que deux sommets sont adjacents si les cellules ont un côté en commun. Dans ce contexte, on peut étudier les polyominos dont le graphe est acyclique, appelés polyominos-arbres. En 2016, Blondin-Massé et al. ont déterminé le nombre maximal de feuilles que peut posséder un polyomino-arbre à n cellules. Dans cet exposé, nous généralisons ce problème aux graphes en général et nous montrons que le problème est NP-complet. Cependant, le problème devient polynomial lorsqu'on se restreint aux arbres et aux graphes de largeur arborescente constante. [less ▲]

Detailed reference viewed: 13 (2 ULg)
Full Text
See detailSous-arbres induits pleinement feuillus
Vandomme, Elise ULg

Scientific conference (2017, January 19)

In the last 60 years, polyominoes have been the object of many investigations. A central problem, that is still open, is to determine the number of polyominoes with n square cells. An approach to solve ... [more ▼]

In the last 60 years, polyominoes have been the object of many investigations. A central problem, that is still open, is to determine the number of polyominoes with n square cells. An approach to solve the problem is to use a combinatorial description of polyominoes and to try to describe particular families of polyominoes. Behind each polyomino there is a graph whose vertices are the cells, such that two vertices are adjacent if their cells share a common edge. In this framework, one can study the polyominoes with an acyclic graph, called tree-like polyominoes. In 2016, Blondin-Massé et al. determined the maximal number that can have a tree-like polyomino with n cells. In this talk, we generalize this problem to graphs in general and we show this problem is NP-complete. However, the problem becomes polynomial when we restrict ourselves to trees or to graphs with a constant tree-width. [less ▲]

Detailed reference viewed: 16 (2 ULg)
Full Text
See detailMathémagie - L'art de la divination
Vandomme, Elise ULg

Speech/Talk (2016)

Cet exposé est basé sur la suite des exposés Mathémagie (I, II, III) de Michel Rigo. Nous présentons ici 10 tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien ... [more ▼]

Cet exposé est basé sur la suite des exposés Mathémagie (I, II, III) de Michel Rigo. Nous présentons ici 10 tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien : des tours de cartes, des tours de divination et le célèbre tour du ``barman aveugle avec des gants de boxe''. Contrairement au magicien qui ne dévoile jamais ses secrets, ici, nous expliquons que ces tours reposent sur diverses propriétés et constructions mathématiques, comme la théorie des graphes ou la combinatoire des mots. [less ▲]

Detailed reference viewed: 35 (2 ULg)
Full Text
Peer Reviewed
See detailIdentifying codes in vertex-transitive graphs and strongly regular graphs
Gravier, Sylvain; Parreau, Aline; Rottey, Sara et al

in Electronic Journal of Combinatorics (2015), 22(4), 46

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and 2ln(|V|)+1 where V ... [more ▼]

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and 2ln(|V|)+1 where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order |V|^α with α∈{14,13,25}. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs. [less ▲]

Detailed reference viewed: 62 (18 ULg)
Full Text
See detailUse of the wavelet theory as a tool to investigate the l-abelian complexity of a sequence
Kleyntssens, Thomas ULg; Nicolay, Samuel ULg; Vandomme, Elise ULg et al

Poster (2015, September 23)

The concept of k-automatic sequences is at the intersection of number theory and formal language theory. It has been generalized by the notion of k-regularity that allows to study sequences with values in ... [more ▼]

The concept of k-automatic sequences is at the intersection of number theory and formal language theory. It has been generalized by the notion of k-regularity that allows to study sequences with values in a (possibly infinite) ring. This concept provides us with structural information about how the different terms of the sequence are related to each other. They are many different notions related to the measure of complexity of an infinite sequence w. A classical approach is its factor complexity. In an abelian context, the analogue to the factor complexity is the abelian complexity where the number of distinct factors of length n is counted up to abelian equivalence. The notion of abelian complexity was extended to that of l-abelian complexity. In this talk, I propose to use tools from the wavelet theory to analyze the l-abelian complexity. For the numerical simulations, I apply the wavelet leaders method that allows to study the pointwise regularity of signals. [less ▲]

Detailed reference viewed: 31 (11 ULg)
Full Text
See detailContributions to combinatorics on words in an abelian context and covering problems in graphs
Vandomme, Elise ULg

Doctoral thesis (2015)

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 333 (67 ULg)
Full Text
Peer Reviewed
See detailA New Approach to the 2-Regularity of the ℓ-Abelian Complexity of 2-Automatic Sequences
Parreau, Aline; Rigo, Michel ULg; Rowland, Eric ULg et al

in The Electronic Journal of Combinatorics (2015), 22(1), 127

We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem ... [more ▼]

We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem to develop a general approach for studying the l-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue--Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular. [less ▲]

Detailed reference viewed: 62 (17 ULg)
Full Text
Peer Reviewed
See detailA new approach to the 2-regularity of the ℓ-abelian complexity of 2-automatic sequences (extended abstract)
Parreau, Aline; Rigo, Michel ULg; Rowland, Eric ULg et al

Conference (2014, September)

We show that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit. We apply this theorem to develop a general approach for studying the ℓ-abelian complexity ... [more ▼]

We show that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit. We apply this theorem to develop a general approach for studying the ℓ-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue–Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular. [less ▲]

Detailed reference viewed: 29 (7 ULg)
Full Text
Peer Reviewed
See detailIdentifying codes in vertex-transitive graphs
Gravier, Sylvain; Parreau, Aline ULg; Rottey, Sara et al

Conference (2014, July)

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the optimal integer and fractional solutions is between 1 and 2 log(|V|) where V is the ... [more ▼]

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the optimal integer and fractional solutions is between 1 and 2 log(|V|) where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order |V|^a with a in {1/4, 1/3, 2/5}. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs. [less ▲]

Detailed reference viewed: 28 (8 ULg)
Full Text
Peer Reviewed
See detailA conjecture on the 2-abelian complexity of the Thue-Morse word
Rigo, Michel ULg; Parreau, Aline ULg; Vandomme, Elise ULg

Conference (2014, January 20)

The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k ... [more ▼]

The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k-abelian complexity is a generalization of the abelian complexity, corresponding to the case where k=1. Formally, two words u and v of the same length are k-abelian equivalent if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The aim of this talk is to study the 2-abelian complexity a(n) of the Thue-Morse word. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a work of Madill and Rampersad (2012) where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will present some arguments supporting our conjecture. They are based on functions counting some subword of length 2 occuring in prefixes of the Thue-Morse word. [less ▲]

Detailed reference viewed: 76 (21 ULg)
Full Text
See detailLinear formulation of identifying cdes in graphs
Vandomme, Elise ULg; Gravier, Sylvain; Parreau, Aline ULg

Poster (2013, September 09)

Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 and can be applied to locate fire in a building using sensors. Buildings are modelled by graphs with rooms as vertices. The ... [more ▼]

Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 and can be applied to locate fire in a building using sensors. Buildings are modelled by graphs with rooms as vertices. The placement of sensors in the rooms corresponds to choosing a subset of vertices. Finding a sensor-placement such that the location of a fire in one room can be precisely determined is equivalent to constructing an identifying code in the graph. These are dominating sets of vertices for which the closed neighbourhood of each vertex (i.e., the vertex and its neighbours) has a unique intersection with the set. The problem of finding an identifying code has been widely studied. Yet its formulation as an integer linear problem hasn't been much considered. Let G be a graph with vertex set V, to an identifying code $C\subseteq V$ of $G$ correspond weights x_u (x_u is 1 if u belongs to C, otherwise x_u is 0) satisfying the following : for all vertices u,v * the sum of the x_w for w in the closed neighbourhood of u is at least 1 * the sum of the x_w for w in the symmetric difference of the closed neighbourhoods of u and v is at least 1. Of course, it is interesting to find an identifying code with the smallest possible cardinality. But in general this is a NP-hard problem. A way to obtain bounds on the minimal cardinality is to consider the associated linear problem where the weights x_u are fractional. In the case of vertex-transitive graphs, the minimal cardinality for the fractional case can only take two values which depend on the number of vertices, the degree of the graph and the smallest symmetric difference between any two closed neighbourhoods. We show that for an infinite family of graphs the bound is tight and for another another the bound is far too be reached. [less ▲]

Detailed reference viewed: 58 (23 ULg)
Full Text
Peer Reviewed
See detailSome properties of abelian return words
Rigo, Michel ULg; Salimov, Pavel ULg; Vandomme, Elise ULg

in Journal of Integer Sequences (2013), 16

We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in ... [more ▼]

We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null 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 2-automatic Thue--Morse word. We also investigate the relationship existing between abelian complexity and finiteness of the set of abelian returns to all prefixes. We end this paper by considering the notion of abelian derived sequence. It turns out that, for the Thue--Morse word, the set of abelian derived sequences is infinite. [less ▲]

Detailed reference viewed: 165 (42 ULg)
Full Text
See detail2-abelian complexity of the Thue-Morse sequence
Rigo, Michel ULg; Vandomme, Elise ULg

Scientific conference (2012, December 14)

Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of ... [more ▼]

Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. It is trivially abelian periodic and its (1)-abelian complexity takes only two values. The aim of this talk is to explain how to compute the 2-abelian complexity a(n) of the Thue-Morse word, showing in particular that it is unbounded. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a recent work of Madill and Rampersad where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will also explain why the usual logical framework introduced by Büchi and popularized by Bruyère (indeed, automatic sequences can be characterized in an extension of the Presburger arithmetic) and the recent work of Charlier et al. about "automatic theorem-proving" of properties of automatic sequences cannot be applied to these questions related to abelian complexity. [less ▲]

Detailed reference viewed: 186 (43 ULg)
See detailComplexité k-abélienne du mot de Thue-Morse
Vandomme, Elise ULg

Conference (2012, December)

Soit k un entier. Deux mots u et v de même longueur sont équivalents k-abéliennement s'ils ont le même préfixe (resp. suffixe) de longueur k-1 et si, pour tous les mots x de longueur k, les nombres d ... [more ▼]

Soit k un entier. Deux mots u et v de même longueur sont équivalents k-abéliennement s'ils ont le même préfixe (resp. suffixe) de longueur k-1 et si, pour tous les mots x de longueur k, les nombres d'occurrences de x dans et dans v coïncident. Cette notion a suscité récemment beaucoup d'intérêt (consulter par exemple les travaux de Karhumäki et al.) La complexité k-abélienne d'un mot infini w associe à un entier n le nombre de classes d'équivalence k-abélienne partitionnant l'ensemble des facteurs de longueur n de w. Le mot de Thue-Morse est une suite 2-automatique célèbre et très étudiée. Il est triviallement abéliennement périodique et sa complexité (1-)abélienne ne prend que deux valeurs. Le but de cet exposé est de calculer la complexité 2-abélienne du mot de Thue-Morse à l'aide de matrices. En particulier, nous montrerons que cette complexité n'est pas bornée. De plus, nous conjecturons que cette complexité est 2-regulière au sens d'Allouche et Shallit. [less ▲]

Detailed reference viewed: 12 (2 ULg)
Full Text
Peer Reviewed
See detailConstant 2-labelling of weighted cycles
Gravier, Sylvain; Vandomme, Elise ULg

Conference (2012, November)

We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2 ... [more ▼]

We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2-coloring (black and white) of its vertex set which preserves the sum of the weight of black vertices under some automorphisms. In this manuscript, we study this problem on weighted complete graphs and on weighted cycles. Our results on cycles allow us to determine (r,a,b)-codes in Z^2 whenever |a-b|>4 and r>1. [less ▲]

Detailed reference viewed: 32 (6 ULg)