Suppose $G$ is a graph and $e=ab$ is an edge of $G$. For a positive integer $k$, the $G$-necklace of length $k$ (with respect to edge $e$), denoted by $N_k(G)$, is the graph constructed as follows: Take the vertex disjoint union of $k$ copies of $G$, say $Q_1 cup Q_2 cup cdots cup Q_k$, where each $Q_i$ is a copy of $G$, with $e_i=a_ib_i$ be the copy of $e=a b$ in $Q_i$. Add a vertex $u$, delete the edges $e_i$ for $i=1, 2, cdots, k$ and add edges: $ua_1, b_1a_2, b_2a_3, cdots, b_{k-1}a_k, b_ku$. This thesis determines the circular chromatic indexes of $G$-necklaces for $G = K_{2n}$ and $G= K_{m, m}$.(¨£¹q¤l½×¤å²Ä¤»­¶)

Circular words, also known as necklaces, are combinatorial objects closely related to linear words. A brief history of circular words is given, from their early conception to present results. We introduce the concept of a level word, that being a word containing a equal or roughly equal amount of each letter. We characterize exactly the lengths for which level square free circular words on three letters exist. This is accomplished through a modification of Shur’s construction of square-free circular words. A word on two letters is called a Frankel-Simpson word if the only squares it contains are 00, 11, and 0101. Using the result mentioned above and several computer searches, we characterize exactly the lengths for which circular Frankel-Simpson words exist, and give an example or construction for each. / Graduate

1 Abstract (in English): This dissertation compares depictions of Roman jewellery and brooches on monuments with archaeological finds. These monuments are mainly of funerary character and they come primarily from Noricum, Pannonia, Germania, in lesser amount also from Gallia and some other areas. Jewellery is also related to local variants of provincial clothing. A typology of Roman jewellery is given and subsequently I try to find analogies to these jewellery types among the depictions. The typology mentioned here doesn't represent a complete list of jewellery types and variants. It focuses on the most common variants and variants which are relevant to the depictions of jewellery. By comparison of the archaeological finds to the depictions it is possible to obtain more accurate image of the appearance of clothing in different provincial areas and also of some specific traditions related to jewellery. The majority of depicted jewellery was identified with archeaological finds of jewellery, yet some cases stay unclear.

Metallosupramolecular chemistry involves the construction of nanoscale molecular assemblies by reacting metal atoms with bridging organic ligands. The metal atoms act as a type of molecular ‘glue’ binding together the organic ligands in specific orientations. Thus, appropriate combinations of metal ions and ligands lead to the controlled self-assembly of interesting one-, two- and three-dimensional molecular aggregates. This thesis details the preparation of a range of novel flexible bridging heterocyclic ligands using conventional organic synthesis, and then explores their reactions with a variety of transition metal precursors. By varying the nature of the organic ligand and the transition metal precursor, new and exciting supramolecular topologies and architectures can be formed. A total of forty-eight ligands were synthesised in this work, forty-seven of which are new compounds. The majority of the ligands synthesised were based around commercially available bisphenol cores. All forty-eight of the ligands had nitrogen heterocyclic groups as coordinating units. The ligands discussed in this thesis can be divided into three main sections. The first involves the synthesis and coordination chemistry of two-armed ligands based around the Bisphenol A, Bisphenol Z and Bisphenol AP cores. The second section describes the synthesis and coordination chemistry of the larger Bisphenol P and Bisphenol M based two-armed bridging ligands. The third section describes the synthesis and coordination chemistry of various multi-substituted ligands, including tripodal ligands based around a trisphenol core, four-armed ligands and six-armed ligands. The two-armed bisphenol based ligands proved very successful as synthons in metallosupramolecular chemistry and produced many products with a variety of different metal atoms. The complexes characterised included discrete dimeric products, coordination polymers and a number of helicates, including a dinuclear quadruply-stranded helicate. Multi-armed ligands are topical, because they have multiple coordination sites that are capable of binding and bridging multiple metal atoms. Such coordination can lead to the construction of cage-like species and complicated networks. A series of three-armed ligands based around a trisphenol core were synthesised with the intention to use these to form such species on coordination with appropriate metal salts. Indeed, one of the products of self-assembly was an interesting M₃L₂ cage. Various other multi-armed ligands were also investigated. The ligands and complexes in this thesis were characterised by a variety of structural techniques, such as ¹H NMR, ¹³C NMR, mass spectrometry, elemental analysis and X-ray crystallography when crystals were obtained. The crystal structures of twenty-seven ligands and forty-three complexes are described.

This dissertation explores an analogue of the prime number theorem for polynomials over finite fields as well as its connection to the necklace factorization algorithm T-transform and the string complexity measure T-complexity. Specifically, a precise asymptotic expansion for the prime polynomial counting function is derived. The approximation given is more accurate than previous results in the literature while requiring very little computational effort. In this context asymptotic series expansions for Lerch transcendent, Eulerian polynomials, truncated polylogarithm, and polylogarithms of negative integer order are also provided. The expansion formulas developed are general and have applications in numerous areas other than the enumeration of prime polynomials. A bijection between the equivalence classes of aperiodic necklaces and monic prime polynomials is utilized to derive an asymptotic bound on the maximal T-complexity value of a string. Furthermore, the statistical behaviour of uniform random sequences that are factored via the T-transform are investigated, and an accurate probabilistic model for short necklace factors is presented. Finally, a T-complexity based conditional string complexity measure is proposed and used to define the normalized T-complexity distance that measures similarity between strings. The T-complexity distance is proven to not be a metric. However, the measure can be computed in linear time and space making it a suitable choice for large data sets. / Graduate / 0544 0984 0405 / nrebenich@gmail.com

Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers. The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words. These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order. Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1).