Georgia Southern University
Combinatorial Optimization of Subsequence Patterns in Words
Abstract
dc:description.abstractPacking patterns in words concerns finding a word with the maximum number of a prescribed pattern. The majority of the work done thus far is on packing patterns into permutations. In 2002, Albert, Atkinson, Handley, Holton and Stromquist showed that there always exists a layered permutation containing the maximum number of a layered pattern among all permutations of length n. Consequently, the packing density for all but two (up to equivalence) permutation patterns up to length 4 can be obtained. In this thesis we consider the analogous question for colored patterns and permutations. By introducing the concept of colored blocks we characterize the optimal permutations with the maximum number of a given colored pattern when it contains at most three colored blocks. As examples, we apply this characterization to find the optimal permutations of various colored patterns and subsequently obtain their corresponding packing densities.
Degree
thesis:*- Name thesis:degree_name
- Master of Science in Mathematics (M.S.)
- Level thesis:degree_level
- Thesis (open access)
- Discipline thesis:degree_discipline
- Department of Mathematical Sciences
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Just, Matthew R
- Contributors dc:contributor
-
- Colton Magnant
- Andrew Sills
- Daniel Gray
Subjects
dc:subject × 5Rights
- Licence dc:rights.license
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.georgiasouthern.edu/etd/1464