Physical Sciences and Mathematics Commons^™

Trees, Partitions, And Other Combinatorial Structures, Heather Christina Smith

Theses and Dissertations

This dissertation contains work on three main topics.

Chapters 1 through 4 provide complexity results for the single cut-or-join model for genome rearrangement. Genomes will be represented by binary strings. Let S be a finite collection of binary strings, each of the same length. Define M to be the collection of medians – binary strings μ which minimize Sigma v belongs to S H(μ,v) where H is the Hamming distance. For any non-negative function f(x), define Z(f(x), S) to be (Sigma μ belongs to M) (Pi v belongs to S)f(H(μ,v)). We study the complexity of calculating Z(f(x), S), with respect …

Toward The Combinatorial Limit Theory Of Free Words, Danny Rorabaugh

Theses and Dissertations

Free words are elements of a free monoid, generated over an alphabet via the binary operation of concatenation. Casually speaking, a free word is a finite string of letters. Henceforth, we simply refer to them as words. Motivated by recent advances in the combinatorial limit theory of graphs–notably those involving flag algebras, graph homomorphisms, and graphons–we investigate the extremal and asymptotic theory of pattern containment and avoidance in words.

Word V is a factor of word W provided V occurs as consecutive letters within W. W is an instance of V provided there exists a nonerasing monoid homomorphsism phi with …

Modeling And Computations Of Cellular Dynamics Using Complex-Fluid Models, Jia Zhao

Theses and Dissertations

Cells are fundamental units in all living organisms as all living organisms are made up of cells of different varieties. The study of cells is therefore an essential part of research in life science. Cells can be classified into two basic types: prokaryotic cells and eukaryotic cells. One typical organisms of prokaryotes is bacterium. And eukaryotes mainly consist of animal cells. In this thesis, we focus on developing predictive models mathematically to study bacteria colonies and animal cell mitotic dynamics.

Instead of living alone, bacteria usually survive in a biofilm, which is a microorganism where bacteria stick together by extracellular …

Avoiding Doubled Words In Strings Of Symbols, Michael Lane

Theses and Dissertations

A word on the n-letter alphabet is a finite length string of symbols formed from a set of n letters. A word is doubled if every letter that appears in the word appears at least twice. A word w avoids a word u if there is no non-erasing homomorphism h (a map that respects concatenation) such that h (u) is a subword of w. Finally, a word w is n-avoidable if there is an infinite list of words on the n-letter alphabet that avoid w. In 1906, Thue showed that the simplest doubled word, namely xx, is 3-avoidable. In 1984, …

Commutator Studies In Pursuit Of Finite Basis Results, Nathan E. Faulkner

Theses and Dissertations

Several new results of a general algebraic scope are developed in an effort to build tools for use in finite basis proofs. Many recent finite basis theorems have involved assumption of a finite residual bound, with the broadest result concerning varieties with a difference term (Kearnes, Szendrei, and Willard (2013+)). However, in varieties with a difference term, the finite residual bound hypothesis is known to strongly limit the degree of nilpotence observable in a variety, while, on the other hand, there is another, older series of results in which nilpotence plays a key role (beginning with those of Lyndon (1952) …

The Packing Chromatic Number Of Random D-Regular Graphs, Ann Wells Clifton

Theses and Dissertations

Let G = (V (G),E(G)) be a simple graph of order n and let i be a positive integer. X_i superset V (G) is called an i-packing if vertices in X_i are pairwise distance more than i apart. A packing coloring of G is a partition X = {X₁,X₂,X₃, . . . ,X_k} of V (G) such that each color class X_i is an i-packing. The minimum order k of a packing coloring is called the packing chromatic number of G, denoted by X_p(G). Let G_{n,d …}