Browsing M.Sc. Mathematics and Statistics by Publication date
Now showing items 118 of 18

Zerosum problems in finite cyclic groupsThe purpose of this thesis is to investigate some open problems in the area of combinatorial number theory referred to as zerosum theory. A zerosequence in a finite cyclic group G is said to have the basic property if it is equivalent under group automorphism to one which has sum precisely IGI when this sum is viewed as an integer. This thesis investigates two major problems, the first of which is referred to as the basic pair problem. This problem seeks to determine conditions for which every zerosequence of a given length in a finite abelian group has the basic property. We resolve an open problem regarding basic pairs in cyclic groups by demonstrating that every sequence of length four in Zp has the basic property, and we conjecture on the complete solution of this problem. The second problem is a 1988 conjecture of Kleitman and Lemke, part of which claims that every sequence of length n in Zn has a subsequence with the basic property. If one considers the special case where n is an odd integer we believe this conjecture to hold true. We verify this is the case for all prime integers less than 40, and all odd integers less than 26. In addition, we resolve the KleitmanLemke conjecture for general n in the negative. That is, we demonstrate a sequence in any finite abelian group isomorphic to Z2p (for p ~ 11 a prime) containing no subsequence with the basic property. These results, as well as the results found along the way, contribute to many other problems in zerosum theory.

The von Neumann Minimax Theorem and its relatives and a study of externality in online auctionsThis work consists of a theoretical part and an experimental one. The first part provides a simple treatment of the celebrated von Neumann minimax theorem as formulated by Nikaid6 and Sion. It also discusses its relationships with fundamental theorems of convex analysis. The second part is about externality in sponsored search auctions. It shows that in these auctions, advertisers have externality effects on each other which influence their bidding behavior. It proposes Hal R.Varian model and shows how adding externality to this model will affect its properties. In order to have a better understanding of the interaction among advertisers in online auctions, it studies the structure of the Google advertisements networ.k and shows that it is a smallworld scalefree network.

Response curves of deterministic and probabilistic cellular automata in one and two dimensionsOne of the most important problems in the theory of cellular automata (CA) is determining the proportion of cells in a specific state after a given number of time iterations. We approach this problem using patterns in preimage sets  that is, the set of blocks which iterate to the desired output. This allows us to construct a response curve  a relationship between the proportion of cells in state 1 after niterations as a function of the initial proportion. We derive response curve formulae for many twodimensional deterministic CA rules with Lneighbourhood. For all remaining rules, we find experimental response curves. We also use preimage sets to classify surjective rules. In the last part of the thesis, we consider a special class of onedimensional probabilistic CA rules. We find response surface formula for these rules and experimental response surfaces for all remaining rules.

Square Root Finding In GraphsAbstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NPcompleteness is proven for square of graphs with girth at most four. The girthparameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NPcomplete. This result is providing the complete dichotomy theorem for square root finding problem.

Rings, Group Rings, and Their GraphsWe associate some graphs to a ring R and we investigate the interplay between the ringtheoretic properties of R and the graphtheoretic properties of the graphs associated to R. Let Z(R) be the set of zerodivisors of R. We define an undirected graph ᴦ(R) with nonzero zerodivisors as vertices and distinct vertices x and y are adjacent if xy=0 or yx=0. We investigate the Isomorphism Problem for zerodivisor graphs of group rings RG. Let Sk denote the sphere with k handles, where k is a nonnegative integer, that is, Sk is an oriented surface of genus k. The genus of a graph is the minimal integer n such that the graph can be embedded in Sn. The annihilatingideal graph of R is defined as the graph AG(R) with the set of ideals with nonzero annihilators as vertex such that two distinct vertices I and J are adjacent if IJ=(0). We characterize Artinian rings whose annihilatingideal graphs have finite genus. Finally, we extend the definition of the annihilatingideal graph to noncommutative rings.

Acyclic 5Choosability of Planar Graphs Without Adjacent Short CyclesThe conjecture claiming that every planar graph is acyclic 5choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169176], have shown that a planar graph is acyclically 5choosable if it does not contain an icycle adjacent to a jcycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an icycle adjacent to a jcycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5choosable.

Edgechoosability of Planar GraphsAccording to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge(∆ + 1)choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without 7cycles with ∆(G)≠5,6 , or without adjacent 4cycles with ∆(G)≠5, or with no 3cycles adjacent to 5cycles, then G is edge(∆ + 1)choosable.

A gametheoretic network formation modelWe study the dynamics of a gametheoretic network formation model that yields largescale smallworld networks. So far, mostly stochastic frameworks have been utilized to explain the emergence of these networks. On the other hand, it is natural to seek for gametheoretic network formation models in which links are formed due to strategic behaviors of individuals, rather than based on probabilities. Inspired by EvenDar and Kearns (2007), we consider a more realistic model in which the cost of establishing each link is dynamically determined during the course of the game. Moreover, players are allowed to put transfer payments on the formation of links. Also, they must pay a maintenance cost to sustain their direct links during the game. We show that there is a small diameter of at most 4 in the general set of equilibrium networks in our model. Unlike earlier model, not only the existence of equilibrium networks is guaranteed in our model, but also these networks coincide with the outcomes of pairwise Nash equilibrium in network formation. Furthermore, we provide a network formation simulation that generates smallworld networks. We also analyze the impact of locating players in a hierarchical structure by constructing a strategic model, where a complete bary tree is the seed network.

Prime Rational Functions and Integral PolynomialsLet f(x) be a complex rational function. In this work, we study conditions under which f(x) cannot be written as the composition of two rational functions which are not units under the operation of function composition. In this case, we say that f(x) is prime. We give suﬃcient conditions for complex rational functions to be prime in terms of their degrees and their critical values, and we derive some conditions for the case of complex polynomials. We consider also the divisibility of integral polynomials, and we present a generalization of a theorem of Nieto. We show that if f(x) and g(x) are integral polynomials such that the content of g divides the content of f and g(n) divides f(n) for an integer n whose absolute value is larger than a certain bound, then g(x) divides f(x) in Z[x]. In addition, given an integral polynomial f(x), we provide a method to determine if f is irreducible over Z, and if not, ﬁnd one of its divisors in Z[x].

Optimal and Robust Designs of Stepstress Accelerated Life Testing Experiments for Proportional Hazards ModelsAccelerated life testing (ALT) is widely used to obtain reliability information about a product within a limited time frame. The Cox s proportional hazards (PH) model is often utilized for reliability prediction. My master thesis research focuses on designing accelerated life testing experiments for reliability estimation. We consider multiple stepstress ALT plans with censoring. The optimal stress levels and times of changing the stress levels are investigated. We discuss the optimal designs under three optimality criteria. They are D, A and Qoptimal designs. We note that the classical designs are optimal only if the model assumed is correct. Due to the nature of prediction made from ALT experimental data, attained under the stress levels higher than the normal condition, extrapolation is encountered. In such case, the assumed model cannot be tested. Therefore, for possible imprecision in the assumed PH model, the method of construction for robust designs is also explored.

Backbone Colouring of GraphsConsider an undirected graph G and a subgraph of G, H. A qbackbone kcolouring of (G,H) is a mapping f: V(G) {1, 2, ..., k} such that G is properly coloured and for each edge of H, the colours of its endpoints differ by at least q. The minimum number k for which there is a backbone kcolouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone kcolouring of (G,T) is at most 4 if G is a connected C4free planar graph or nonbipartite C5free planar graph or Cjfree, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2backbone kcolouring of any connected planar graphs without adjacent triangles is at most 4 by using a discharging method. In the second part of this thesis we further improve these results by proving that for any graph G with χ(G) ≥ 4, BBC(G,T) = χ(G). In fact, we prove the stronger result that a backbone tree T in G exists, such that ∀ uv ∈ T, f(u)f(v)=2 or f(u)f(v) ≥ k2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.

Dynamics in large scale networksIn this thesis we study the properties of two large dynamic networks, the competition network of advertisers on the Google and Bing search engines and the dynamic network of friend relationships among avatars in the massively multiplayer online game (MMOG) Planetside 2. We are particularly interested in removal patterns in these networks. Our main finding is that in both of these networks the nodes which are most commonly removed are minor near isolated nodes. We also investigate the process of merging of two large networks using data captured during the merger of servers of Planetside 2. We found that the original network structures do not really merge but rather they get gradually replaced by newcomers not associated with the original structures. In the final part of the thesis we investigate the concept of motifs in the BarabásiAlbert random graph. We establish some bounds on the number of motifs in this graph.

Upper Bounds for the Number of solutions for the Diophantine Equation $y^2=px(Ax^2C), C \in {2, \pm 1, \pm 4}$A Diophantine equation is an equation of more than one variable where we are looking for strictly integer solutions. The purpose of this paper is to give a new upper bounds for the number of positive solutions for the Diophantine equation $y^2 = px(Ax^2 − C), C \in {2, ±1, ±4}. Where p is an odd prime and A is an integer greater than 1. The case where C = −2 is already complete, which we go over in detail here. We look through examples of Diophantine equations starting with linear Diophantine equations. We then look at Pell’s equation, $x^2 − Dy^2 = C$ where D and C are natural numbers. We show the continued fraction algorithm and how to use it to solve Pell’s equation. We will look at proofs and lemmas surrounding particular cases of the Diophantine equation $y^2 = px(Ax^2 − C)$. Then focus on finding the upper bounds of the equation. Then we conclude by showing the new upper bounds of the Diophantine equation $y^2 = px(Ax^2 − C), C \in {2, ±1, ±4}.

Diophantine Triples and Linear Forms in LogarithmsThis is the thesis for my master's degree in mathematics which I undertook with Dr. Omar Kihel. Over the last couple of years I have studied number theory with the aim being to develop a broader understanding of the theory of Diophantine equations and their (at times) elusive solutions. I begin my thesis by establishing some of the preliminary results while touching on their place within the history of number theory. This section finishes with an account of Alan Baker's work on linear forms in logarithms and some of its applications, after which the two theorems on Diophantine triples that this paper will aim to prove are stated. In the second section, I list a series of definitions and results of which the reader must be aware, but which I could not fit into the first section due to its historical slant. Following this, I prove a lemma on Pellian equations which generalizes the first lemma of [1]. This requires that a mistake from the proof of that lemma be fixed. Since this lemma was used in [2], this section serves to buttress that result as well. In the next two sections, I prove the two main theorems using results on linear forms in logarithms of algebraic numbers, extending the main result in [2] to $D(9)$ and $D(64)$ triples. The thesis ends with a few words on potential generalization and improvement of the main results, as well as other potential avenues of inquiry, and draws attention to some potential difficulties. The main results closely follow a paper cowritten with my brother, Benjamin EarpLynch.

Linear Forms in Logarithms and Fibonacci NumbersThe main work included in these pages is from a paper cowritten by myself and my brother, Simon EarpLynch, under the supervision of Omar Kihel, pertaining to Diophantine triples of Fibonacci numbers. To go along with this will be introductory material not included in said paper which establishes the mathematical concepts therein and offers some historical perspective and motivation. The initial aim of the paper was to explore the possibility of a generalization of the main result in [2] on D(4)Diophantine triples of Fibonacci numbers. The paper managed to extend the ideas in [2] to results for D(9)Diophantine triples and D(64)Diophantine triples. A generalization of Lemma 1 of [1] was also found, a lemma on Diophantine triples and Pellian equations which is key in establishing the main result in [2]. This paper includes this result and its proof, which involves a correction of the proof of Lemma 1 of [1]. This result may prove useful in the extension of the results in the paper, and potentially others as well. I will begin by introducing Diophantine equations, leading to Diophantine triples, followed by a section on the necessary preliminaries on Fibonacci num bers, which concludes with the statements of our main results. Following this, I establish the primary machinery used in the proof of the main result, linear forms in logarithms. I then move to the generalization of the aforementioned Lemma 1 of [1], before finally commencing the proof of the main results.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic GraphsIn this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from MerriamWebster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

Community Detection in MultiLayer NetworksIn the scope of the current thesis we review and analyse networks that are formed by nodes with several attributes. We suppose that different layers of communities are embedded in such networks, besides each of the layers is connected with nodes' attributes. For example, examine one of a variety of online social networks: an user participates in a plurality of different groups/communities – schoolfellows, colleagues, clients, etc. We introduce a detection algorithm for the abovementioned communities. Normally the result of the detection is the community supplemented just by the most dominant attribute, disregarding others. We propose an algorithm that bypasses dominant communities and detects communities which are formed by other nodes' attributes. We also review formation models of the attributed networks and present a Human Communication Network (HCN) model. We introduce a High School Texting Network (HSTN) and examine our methods for that network.

Towards a New Algorithm for Event Recommendation SystemWe develop a recommendation algorithm for a local entertainment and ticket provider company. The recommender system predicts the score of items, i.e. event, for each user. The special feature of these events, which makes them very different from similar settings, is that they are perishable: each event has a relatively short and specific lifespan. Therefore there is no explicit feedback available for a future event. Moreover, there is a very short description provided for each event and thus the keywords play a more than usual important role in categorizing each event. We provide a hybrid algorithm that utilizes contentbased and collaborative filtering recommendations. We also present an axiomatic analysis of our model. These axioms are mostly derived from social choice theory.