We define the notion of monotone operations admitted by partially ordered sets, specifically monotone near-unanimity functions and Jónsson operations. We then prove a result of McKenzie's in [8] which states that if a finite, bounded poset P admits a set of monotone Jónsson operations then it admits a set of monotone Jónsson operations for which the operations with even indices do not depend on their second variable. We next define zigzags of posets and prove various useful properties about them. Using these zigzags, we proceed carefully through Zadori's proof from [12] that a finite, bounded poset P admits a monotone near-unanimity function if and only if P admits monotone Jónsson operations.

The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture.

In this dissertation, a problem related to Hadwiger's conjecture has been studied. We first proved a conjecture of Jakobsen from 1983 which states that every simple graphs on $n$ vertices and at least (11n-35)/2 edges either has a minor isomorphic to K_8 with one edge deleted or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2} and/or K_7 by identifying cliques of size five. We then studied the extremal functions for complete minors. We proved that every simple graph on nge9 vertices and at least 7n-27 edges either has a minor, or is isomorphic to K_{2, 2, 2, 3, 3}, or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2, 2} by identifying cliques of size six. This result extends Mader's theorem on the extremal function for K_p minors, where ple7. We discussed the possibilities of extending our methods to K_{10} and K_{11} minors. We have also found the extremal function for K_7 plus a vertex minor.

This thesis consists of three chapters. Chapter 1 explains how the research problems considered in this thesis fit into the investigation of local-global principle in the diophantine geometry, as well as gives a unified sketch of the proofs of the two main results in this thesis. Chapter 2 establishes a similar conclusion to Theorem B of a paper by Poonen and Voloch in another settings. Chapter 3 relates to the object considered in the main result of Chapter 2 to an old conjecture proposed by Skolem and solves some cases of its analog. / text

For K a cubic field with only one real embedding and α, β ϵ K, we show how to construct an increasing sequence {m_n} of positive integers and a subsequence {ψ_n} such that (for some constructible constants γ₁, γ₂ > 0): max{ǁm_nαǁ,ǁm_nβǁ} < [(γ₁)/(m_n^(¹/²))] and ǁψ_nαǁ < γ₂/[ψ_n^(¹/²) log ψ_n] for all n. As a consequence, we have ψ_nǁψ_nαǁǁψ_nβǁ < [(γ₁ γ₂)/(log ψ_n)] for all n, thus giving an effective proof of Littlewood's conjecture for the pair (α, β). Our proofs are elementary and use only standard results from algebraic number theory and the theory of continued fractions.

The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture.

It was conjectured in the early 1950¡¯s that the empirical spectral distribution (ESD) of an $n \times n$ matrix whose entries are independent and identically distributed with mean zero and variance one, normalized by a factor of $\frac{1}{\sqrt{n}}$, converges to the uniform distribution over the unit disk on the complex plane, which is called the circular law. The goal of this thesis is to prove the so called Replacement Principle introduced by Tao and Vu which is a crucial step in their recent proof of the circular law in full generality. It gives a general criterion for the difference of the ESDs of two normalised random matrices $\frac{1}{\sqrt{n}}A_n$, $\frac{1}{\sqrt{n}}B_n$ to converge to 0. / Thesis (Master, Mathematics & Statistics) -- Queen's University, 2009-07-11 14:57:44.225

In 1974, H. Ruderman posed the following question: If $(2^m-2^n)|(3^m-3^n)$, then does it follow that $(2^m-2^n)|(x^m-x^n)$ for every integer $x$? This problem is still open. However, in 2011, M. R. Murty and V. K. Murty showed that there are only finitely many $(m,n)$ for which the hypothesis holds. In this thesis, we examine two generalizations of this problem. The first is replacing 2 and 3 with arbitrary integers $a$ and $b$. The second is to replace 2 and 3 with arbitrary algebraic integers from an imaginary quadratic field. In both of these cases we have shown that there are only finitely many $(m,n)$ for which the hypothesis holds. To get the second result we also generalized a result by Bugeaud, Corvaja and Zannier from the integers to imaginary quadratic fields. In the last half of the thesis we use the abc conjecture and some related conjectures to study some exponential Diophantine equations. We study the Pillai conjecture and the Erd\"{o}s-Woods conjecture and show that they are implied by the abc conjecture and that when we use an effective version, very clean bounds for the conjectures are implied. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2012-04-13 12:04:14.252

No description available.

A motivational problem for group homology is a conjecture of Quillen that states, as reformulated by Anton, that the second homology of the general linear group over R = Z[1/p; ζp], for p an odd prime, is isomorphic to the second homology of the group of units of R, where the homology calculations are over the field of order p. By considering the group extension spectral sequence applied to the short exact sequence 1 → SL2 → GL2 → GL1 → 1 we show that the calculation of the homology of SL2 gives information about this conjecture. We also present a series of algorithms that finds an upper bound on the second homology group of a finitely-presented group. In particular, given a finitely-presented group G, Hopf's formula expresses the second integral homology of G in terms of generators and relators; the algorithms exploit Hopf's formula to estimate H2(G; k), with coefficients in a finite field k. We conclude with sample calculations using the algorithms.