Patterns, Pattern Avoidance and Graphs on Words
No Thumbnail Available
Date
2019
Authors
Singh, Mrityunjay
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this thesis, we look at various notions of patterns and pattern avoidance in words. The three themes we have looked at are pattern avoidance on two dimensional words, pattern based word representability of graph and quasiperiodicity patterns and their allied properties in Tribonacci words. A mapping f from Z times Z to Σ is called a two dimensional word. For each discrete line of a two dimensional word, we can get a one dimensional word by concatenating letters present at the lattice points of the line. If each of these one dimensional words are square free then we say that two dimensional word is square free. We prove that there are no two dimensional square free words on 8 letters. For a given word w, Gw stands for alternating letter graph corresponding to w. Formally, Gw = (Vw,Ew) where Vw is the set of letters in w and (a,b) ∈ Ew if the letters a and b are alternating in w. We say that a word w represents a graph G if Gw = G. We give a linear time algorithm to check if a two uniform word w represents G. We study the problem of counting the number of two uniform representants of the cycle graph and show that the number of two uniform representants of the cycle graph on n vertices is 4n. We looked at the notion of uniform permutation representability of graphs and found graphs which are (k,p)-representable for some particular k and p. A word is quasiperiodic if a finite length factor covers each of its indices. The Tribonacci words are a family of words generated using the Tribonacci-Rauzy morphisms. We find various parameters related to the quasiperiodicity of the Tribonacci words.
Description
Supervisor: Benny George Kenkireth
Keywords
COMPUTER SCIENCE AND ENGINEERING