A knot is an embedding of S1 in three-dimensional space. Generally, it can be thought of as a knotted piece of string with the ends glued together. When we project a knot into the plane, we can create a knot diagram in which we specify which portion of the string lies on top at each place that the string crosses itself. To perform a crossing change on a knot, one can imagine cutting one portion of the string at a crossing, allowing another portion of the string to pass through, and then gluing the cleaved ends back together. We define the distance between two knots, K1 and K2, to be the minimum number of crossing changes one must perform on either K1 or K2 to obtain the other knot. Circular DNA can become knotted during biological processes such as recombination and replication. We can model knotted DNA with a mathematical knot. Type II topoisomerases are the enzymes tasked with keeping DNA unknotted, and they act on double-stranded circular DNA by breaking the backbone of the DNA, allowing another segment of DNA to pass through, and then re-sealing the break. Thus, performing a crossing change on a knot models the action of this protein. Specifically, studying knots of distance one can help us better understand how the action of a type II topisomerase on double-stranded circular DNA can alter DNA topology. We create a knot distance graph by letting the set of vertices be rational knots with up to and including thirteen crossings and by placing an edge between two vertices if the two knots corresponding to those vertices are of distance one. A neighborhood of a vertex, v, in a graph is the set of vertices with which v is adjacent via an edge. Using graph theoretical and topological tools, we examine graphs of knot distances and define a mapping between distance one neighborhoods. Additionally, this idea can also be examined and visualized as performing Dehn surgery on the double branched cover of a knot.

Combinatorial games are intriguing and have a tendency to engross students and lead them into a serious study of mathematics. The engaging nature of games is the basis for this thesis. Two combinatorial games along with some educational tools were developed in the pursuit of the solution of these games. The game of Nim is at least centuries old, possibly originating in China, but noted in the 16th century in European countries. It consists of several stacks of tokens, and two players alternate taking one or more tokens from one of the stacks, and the player who cannot make a move loses. The formal and intense study of Nim culminated in the celebrated Sprague-Grundy Theorem, which is now one of the centerpieces in the theory of impartial combinatorial games. We study a variation on Nim, played on a graph. Graph Nim, for which the theory of Sprague-Grundy does not provide a clear strategy, was originally developed at the University of Colorado Denver. Graph Nim was first played on graphs of three vertices. The winning strategy, and losing position, of three vertex Graph Nim has been discovered, but we will expand the game to four vertices and develop the winning strategies for four vertex Graph Nim. Graph Theory is a markedly visual field of mathematics. It is extremely useful for graph theorists and students to visualize the graphs they are studying. There exists software to visualize and analyze graphs, such as SAGE, but it is often extremely difficult to learn how use such programs. The tools in GeoGebra make pretty graphs, but there is no automated way to make a graph or analyze a graph that has been built. Fortunately GeoGebra allows the use of JavaScript in the creation of buttons which allow us to build useful Graph Theory tools in GeoGebra. We will discuss two applets we have created that can be used to help students learn some of the basics of Graph Theory. The game of thrones is a two-player impartial combinatorial game played on an oriented complete graph (or tournament) named after the popular fantasy book and TV series. The game of thrones relies on a special type of vertex called a king. A king is a vertex, k, in a tournament, T, which for all x in T either k beats x or there exists a vertex y such that k beats y and y beats x. Players take turns removing vertices from a given tournament until there is only one king left in the resulting tournament. The winning player is the one which makes the final move. We develop a winning position and classify those tournaments that are optimal for the first or second-moving player.

A transitive decomposition of a graph is a partition of the arc set such that there exists a group of automorphisms of the graph which preserves and acts transitively on the partition. This turns out to be a very broad idea, with several striking connections with other areas of mathematics. In this thesis we first develop some general theory of transitive decompositions, and in particular we illustrate some of the more interesting connections with certain combinatorial and geometric structures. We then give complete, or nearly complete, structural characterisations of certain classes of transitive decompositions preserved by a group with a rank 3 action on vertices (such a group has exactly two orbits on ordered pairs of distinct vertices). The main classes of rank 3 groups we study (namely those which are imprimitive, or primitive of grid type) are derived in some way from 2-transitive groups (that is, groups which are transitive on ordered pairs of distinct vertices), and the results we achieve make use of the classification by Sibley in 2004 of transitive decompositions preserved by a 2-transitive group.

Thesis (Ph. D.)--University of Rhode Island, 2005. / Typescript. Includes bibliographical references (leaf 36).

In view of the fact that a same complex phenomenon can be approached by different conceptual frameworks, it is natural to inquire on the possibility to find connections between different types of quantities, such as topological, dynamical, statistical or thermodynamical, characterizing the same system. The present work is built on the idea that this line of approach can provide interesting insights on possible universal principles governing complex phenomena. In Chapter I we introduce concepts and tools of dynamical systems and thermodynamics as applied in macroscopic scale description as well as, for a later use, a number of selected representative models. In Chapter II we briefly present the elements of the theory of Markov processes describing a large class of stochastic process and also introduce some important concepts on the probabilistic description of deterministic systems. This chapter ends with a thermodynamic formulation accounting for the evolution of the entropy under the effect of stochastic fluctuations. In Chapter III, after introducing the main concepts and recent advances in network theory, we provide a connection between dynamical systems and network theory, which shows how universal structural properties of evolving networks can arise from deterministic dynamics. More specifically, we show explicitly the relation between the connectivity patterns of these networks and the indicators of the underlying dynamics, such as the local Lyapunov exponents. Our analysis is applied to representative models of chaotic maps, chaotic flows and is finally extended to stochastic processes. In Chapter IV we address the inverse problem, namely, processes whose dynamics is determined, in part, by the structure of the network in which they are embedded. In particular, we focus on systems of particles diffusing on a lattice and reacting instantaneously upon encountering each other. We study the role of the topology, the degree of synchronicity of motion and the reaction mechanism on the efficiency of the process. This lead us to identify a common generic mechanism responsible for the behavior of the efficiency, as a function of the control parameters. Finally, in Chapter V we study the connection between the topology and the thermodynamic properties of reaction networks, with focus on the entropy production and the system’s efficiency at nonequilibrium steady states. We also explore the connection between dynamic and thermodynamic properties of nonlinear feedbacks, as well as the response properties of reaction networks against both deterministic and stochastic external perturbations. We address networks of varying topologies, from regular lattices to complex structures./Le présent travail s’inscrit dans le domaine de recherche sur les systèmes complexes. Différentes approches, basées des systèmes dynamiques, de la thermodynamique des systèmes hors d’équilibre, de la physique statistique et, plus récemment, de la théorie des réseaux, sont combinés afin d’explorer des liens entre différentes types de grandeurs qui caractérisent certaines classes de comportements complexes. Dans le Chapitre I nous introduisons les principaux concepts et outils de systèmes dynamiques et de thermodynamique. Dans le Chapitre II nous présentons premièrement des éléments de la théorie de processus de Markov, ainsi que les concepts à la base de la description probabiliste des systèmes déterministes. Nous finissons le chapitre en proposant une formulation thermodynamique qui décrit l’évolution de l’entropie hors d’équilibre, soumis à l’influence de fluctuations stochastiques. Dans le Chapitre III nous introduisons les concepts de base en théorie des réseaux, ainsi qu’un résumé générale des progrès récents dans le domaine. Nous établissons ensuite une connexion entre la théorie des systèmes dynamiques et la théorie de réseaux. Celle-ci permet d’approfondir la compréhension des mécanismes responsables de l’émergence des propriétés structurelles dans des réseaux crées par des lois dynamiques déterministes. En particulier, nous mettons en évidence la relation entre des motifs de connectivité de ce type de réseaux et des indicateurs de la dynamique sous-jacente, tel que des exposant de Lyapounov locaux. Notre analyse est illustrée par des applications et des flots chaotiques et étendue à des processus stochastiques. Dans le Chapitre IV nous étudions le problème complémentaire, à savoir, celui de processus dont la dynamique est déterminée, en partie, par la structure du réseau dans lequel elle se déroule. Plus précisément, nous nous concentrons sur le cas de systèmes de particules réactives, diffusent au travers d’un réseau et réagissant instantanément lorsqu’un rencontre se produit entre elles. Nous étudions le rôle de la topologie, du degré de synchronicité des mouvements et aussi celui du mécanisme de réaction sur l’efficacité du processus. Dans les différents modèles étudiés, nous identifions un mécanisme générique commun, responsable du comportement de l’efficacité comme fonction des paramètres de contrôle. Enfin, dans le Chapitre V nous abordons la connexion entre la topologie et les propriétés thermodynamiques des réseaux de réactions, en analysant le comportement local et global de la production d’entropie et l’efficacité du système dans des état stationnaires de non-équilibre. Nous explorons aussi la connexion entre la dynamique et les propriétés de boucles de rétroaction non linéaires, ainsi que les propriétés de réponse des réseaux de réaction à des perturbations stochastiques et déterministes externes. Nous considérons le cas de réseaux à caractère régulier aussi bien que celui de réseaux complexes.

<p>This thesis is a study on the confluence of algebraic structures and graph theory. Its aim is to consider groupoids from factorisations of complete graphs. We are especially interested in the cases where the factors are isomorphic. We analyse the loops obtained from homogeneous factorisations and ask if homogeneity is reflected in the kind of loops that are obtained. In particular, we are interested to see if we obtain either groups or quasi-associative Cayley sets from these loops. November 2008.</p>

Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general paradigm is established which improves a number of previous results while resolving several open conjectures. In addition, the proofs are almost entirely self-contained. In what follows, let S be a fixed surface, G be a graph embedded in S and L a list assignment such that, for every vertex v of G, L(v) has size at least five. First, the thesis provides an independent proof of a theorem of DeVos, Kawarabayashi and Mohar that says if G has large edge-width, then G is 5-list-colorable. Moreover, the bound on the edge-width is improved from exponential to logarithmic in the Euler genus of S, which is best possible up to a multiplicative constant. Second, the thesis proves that there exist only finitely many 6-list-critical graphs embeddable in S, solving a conjecture of Thomassen from 1994. Indeed, it is shown that the number of vertices in a 6-list-critical graph is at most linear in genus, which is best possible up to a multiplicative constant. As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable in S. Furthermore, we prove that the number of L-colorings of an L-colorable graph embedded in S is exponential in the number of vertices of G, with a constant depending only on the Euler genus g of S. This resolves yet another conjecture of Thomassen from 2007. The thesis also proves that if X is a subset of the vertices of G that are pairwise distance Omega(log g) apart and the edge-width of G is Omega(log g), then any L-coloring of X extends to an L-coloring of G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. For regular coloring, this was proved by Albertson and Hutchinson. Other related generalizations are examined.

A novel framework based on cluster co-occurrence and graph theory for structure discovery is applied to audio to find new types of audio objects which enable the compression of an input signal. These new objects differ from those found in current object coding schemes as their shape is not restricted by any a priori psychoacoustic knowledge. The framework is novel from an application perspective, as it marks the first time that graph theory is applied to audio, and with regards to theoretical developments, as it involves new extensions to the areas of unsupervised learning algorithms and frequent subgraph mining methods. Tests are performed using a corpus of audio files spanning a wide range of sounds. Results show that the framework discovers new types of audio objects which yield average respective overall and relative compression gains of 15.90% and 23.53% while maintaining a very good average audio quality with imperceptible changes.

The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by Bollobás in 1984 in connection to k-connected subgraphs of random graphs. Subsequently, k-cores and their properties have been extensively investigated in random graphs and hypergraphs, with the determination of the threshold for the emergence of a giant k-core, due to Pittel, Spencer and Wormald, as one of the most prominent results. In this thesis, we obtain an asymptotic formula for the number of 2-connected graphs, as well as 2-edge-connected graphs, with given number of vertices and edges in the sparse range by exploiting properties of random 2-cores. Our results essentially cover the whole range for which asymptotic formulae were not described before. This is joint work with G. Kemkes and N. Wormald. By defining and analysing a core-type structure for uniform hypergraphs, we obtain an asymptotic formula for the number of connected 3-uniform hypergraphs with given number of vertices and edges in a sparse range. This is joint work with N. Wormald. We also examine robustness aspects of k-cores of random graphs. More specifically, we investigate the effect that the deletion of a random edge has in the k-core as follows: we delete a random edge from the k-core, obtain the k-core of the resulting graph, and compare its order with the original k-core. For this investigation we obtain results for the giant k-core for Erdős-Rényi random graphs as well as for random graphs with minimum degree at least k and given number of vertices and edges.

This thesis investigates three areas of the theory of graph homomorphisms: cores of graphs, the homomorphism order, and quantum homomorphisms. A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that, for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets which each induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions. Next we examine the restriction of the homomorphism order of graphs to line graphs. Our main focus is in comparing this restriction to the whole order. The primary tool we use in our investigation is that, as a consequence of Vizing's theorem, this partial order can be partitioned into intervals which can then be studied independently. We denote the line graph of X by L(X). We show that for all n ≥ 2, for any line graph Y strictly greater than the complete graph Kₙ, there exists a line graph X sitting strictly between Kₙ and Y. In contrast, we prove that there does not exist any connected line graph which sits strictly between L(Kₙ) and Kₙ, for n odd. We refer to this property as being ``n-maximal", and we show that any such line graph must be a core and the line graph of a regular graph of degree n. Finally, we introduce quantum homomorphisms as a generalization of, and framework for, quantum colorings. Using quantum homomorphisms, we are able to define several other quantum parameters in addition to the previously defined quantum chromatic number. We also define two other parameters, projective rank and projective packing number, which satisfy a reciprocal relationship similar to that of fractional chromatic number and independence number, and are closely related to quantum homomorphisms. Using the projective packing number, we show that there exists a quantum homomorphism from X to Y if and only if the quantum independence number of a certain product graph achieves |V(X)|. This parallels a well known classical result, and allows us to construct examples of graphs whose independence and quantum independence numbers differ. Most importantly, we show that if there exists a quantum homomorphism from a graph X to a graph Y, then ϑ̄(X) ≤ ϑ̄(Y), where ϑ̄ denotes the Lovász theta function of the complement. We prove similar monotonicity results for projective rank and the projective packing number of the complement, as well as for two variants of ϑ̄. These immediately imply that all of these parameters lie between the quantum clique and quantum chromatic numbers, in particular yielding a quantum analog of the well known ``sandwich theorem". We also briefly investigate the quantum homomorphism order of graphs.