Mathematics
http://hdl.handle.net/10211.3/10211.8_17
2024-03-28T16:02:50ZColoring Graphs and Digraphs
http://hdl.handle.net/10211.3/215842
Coloring Graphs and Digraphs
Higley, Chris
A coloring of a (directed or undirected) graph is an assignment of colors to the vertices such that the endpoints of each edge receive different colors. A star coloring of an undirected graph is a coloring such that every path on 4 vertices receives at least 3 colors. An incoloring of a directed graph is a coloring such that a path on 3 vertices in the underlying graph receives two colors only if both of its edges are oriented towards the middle vertex in the path.
There is a deep connection between incolorings of directed graphs and star colorings of undirected graphs. In this thesis we investigate how different orientations of graphs impact the number of colors required for an incoloring, and the consequences that this has on star coloring. The results we obtain for grid graphs, prisms, Möbius ladders, and outerplanar triangle-free graphs are best possible.
2020-05-07T00:00:00ZExploring PageRank Algorithms: Power Iteration & Monte Carlo Methods
http://hdl.handle.net/10211.3/215708
Exploring PageRank Algorithms: Power Iteration & Monte Carlo Methods
Vargas, Brian
A search engine is intended to crawl the world wide web and retrieve a list of sites that match the user's search terms. Listing the search results in a proper order is crucial but it is far from being a trivial task. Prior to the rise of Google, search engines were notorious for presenting irrelevant information, and in turn, were not very optimal tools. It wasn't until around 1998 that Google co-founders Lawrence Page and Sergey Brin invented the PageRank algorithm for estimating the importance of a webpage which ultimately revolutionized internet searches. The PageRank algorithm is used to estimate the importance of a webpage based on the interconnection of the web [28].
Google's superiority came in the form of arranging the more important webpages to appear early in the search results. This way, it significantly reduced the amount of time a user had to sift through search results to find the sought-after information. Although PageRank is not the only algorithm for organizing search results today, it was the first algorithm used by Google. Today there are multiple algorithms working together to prioritize search results.
The concept behind PageRank is similar to that of a democracy: each webpage can vote for the importance of other webpages by providing a link to that webpage. However, not every vote is worth the same! Because a webpage with more incoming links is more important than a webpage with less incoming links, the pages with a link from a page of high importance also holds importance.
Since PageRank is a variation of an eigenvector problem, we begin with a review of key concepts from linear algebra in Chapter 1. Using this linear algebra theory, we show that the appropriate model will yield the existence and uniqueness of the ranking of webpages. In Chapter 2 we describe the data structures necessary for implementing the algorithm on a computer. In Chapter 3 we describe a model that can be used to synthesize graphs which closely resemble the properties of the world wide web. In Chapter 4, we explore the power iteration, a deterministic numerical algorithm to solve such an eigenvector problem. In Chapter 5, we explore and compare Monte Carlo methods used to solve the eigenvector problem from a probabilistic approach.
2020-04-28T00:00:00ZAlgorithm for computing units in multicyclic
number fields.
http://hdl.handle.net/10211.3/212764
Algorithm for computing units in multicyclic
number fields.
Savage, Anthony
For finite field extensions of Q, we study a special class of subrings called
the orders of the field. Dirichlet’s Unit Theorem tells us the unit group of these
orders is finitely generated. Certain lattice based cryptosystems rely heavily on
the high difficulty of computing a generating set of the unit group. We will
present a new algorithm for computing the unit group of multicyclic extensions
of Q.
2019-08-15T00:00:00ZSurvey of Multistationarity in Reaction Network Theory
http://hdl.handle.net/10211.3/205281
Survey of Multistationarity in Reaction Network Theory
Li, Yuan
The business of Reaction Network Theory is to model and study
the dynamical properties of biochemical processes and certain biological systems
such ecological dynamics and spread of epidemics. When large number
of reactants are present, a system of ODEs, with the dynamical variables representing molecule concentrations, closely approximates the true dynamics.
Kinetics is the specification of the concentration-dependent rate at which reactions
occur. The most common is mass-action kinetics, for which the reaction
rate is proportional to the concentration of the reactants. An important
question within mass-action systems is identification of networks which have
the property of multistationarity, i.e. networks which have more than one
compatible, positive equilibrium. In this thesis, we will present some necessary
and sufficient conditions for multistationarity within some biologically
relevant networks.
2018-07-30T00:00:00Z