No description available.

No description available.

This thesis discusses graph marking game and graph colouring game. Suppose G=(V, E) is a graph. A marking game on G is played by two players, Alice and Bob, with Alice playing first. At the start of the game all vertices are unmarked. A play by either player consists of marking an unmarked vertex. The game ends when all vertices are marked. For each vertex v of G, write t(v)=j if v is marked at the jth step. Let s(v) denote the number of neighbours u of v for which t(u) < t(v), i.e., u is marked before v. The score of the game is $$s = 1+ max_{v in V} s(v).$$ Alice's goal is to minimize the score, while Bob's goal is to maximize it. The game colouring number colg(G) of G is the least s such that Alice has a strategy that results in a score at most s. Suppose r geq 1, d geq 0 are integers. In an (r, d)-relaxed colouring game of G, two players, Alice and Bob, take turns colouring the vertices of G with colours from a set X of r colours, with Alice having the first move. A colour i is legal for an uncoloured vertex x (at a certain step) if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Each player can only colour an uncoloured vertex with a legal colour. Alice's goal is to have all the vertices coloured, and Bob's goal is the opposite: to have an uncoloured vertex without legal colour. The d-relaxed game chromatic number of a graph G, denoted by $chi_g^{(d)}(G)$ is the least number r so that when playing the (r, d)-relaxed colouring game on G, Alice has a winning strategy. If d=0, then the parameter is called the game chromatic number of G and is also denoted by $chi_g(G)$. This thesis obtains upper and lower bounds for the game colouring number and relaxed game chromatic number of various classes of graphs. Let colg(PT_k) and colg(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this thesis, we prove that colg(PT_k) = 3k+2 and colg(P) geq 11. We also prove that the game colouring number colg(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then colg(H) leq colg(G). For relaxed game chromatic number of graphs, this thesis proves that if G is an outerplanar graph, then $chi_g^{(d)}(G) leq 7-t$ for $t= 2, 3, 4$, for $d geq t$, and $chi_g^{(d)}(G) leq 2$ for $d geq 6$. In particular, the maximum $4$-relaxed game chromatic number of outerplanar graphs is equal to $3$. If $G$ is a tree then $chi_ g^{(d)}(G) leq 2$ for $d geq 2$.

In this paper we explain the congruent number problem and its connection to elliptic curves. We begin with a brief history of the problem and some early attempts to understand congruent numbers. We then introduce elliptic curves and many of their basic properties, as well as explain a few key theorems in the study of elliptic curves. Following this, we prove that determining whether or not a number n is congruent is equivalent to determining whether or not the algebraic rank of a corresponding elliptic curve En is 0. We then introduce L-functions and explain the Birch and Swinnerton- Dyer (BSD) Conjecture. We then explain the machinery needed to understand an algorithm by Tim Dokchitser for evaluating L-functions at 1. We end by computing whether or not a given number n is congruent by implementing Dokchitser’s algorithm with Sage and by using Tunnel’s Theorem.

In this thesis we prove several results in analytic number theory. 1. We show that there exist 3-digit palindromic primes in base b for a set of b having density 1 and that if b is sufficiently large then there is a $3$-digit palindrome in base b having precisely two prime factors. 2. We prove various estimates for averages of sums of Kloosterman fractions over primes. The first of these improves previous results of Fouvry-Shparlinski and Baker. 3. By using the q-analogue of van der Corput's method to estimate short Kloosterman sums we study the divisor function in an arithmetic progression to modulus q. We show that the expected asymptotic formula holds for a larger range of q than was previously known, provided that q has a certain factorisation. 4. Let ‖x‖ denote the distance from x to the nearest integer. We show that for any irrational α and any ϴ< 8/23 there are infinitely many n which are the product of two primes for which ‖nalpha‖ ≤ n ^-ϴ. 5. By establishing an improved level of distribution we study almost-primes of the form f(p,n) where f is an irreducible binary form over Z. 6. We show that for an irreducible cubic f ? Z[x] and a full norm form $mathbf N$ for a number field $K/Q$, satisfying certain hypotheses, the variety $$f(t)=mathbf N(x_1,ldots,x_k) e 0$$ satisfies the Hasse principle. Our proof uses sieve methods.

A graph function $f$ is a mapping which assigns each graph $H$ a positive integer $f(H) leq |V(H)|$ such that $f(H)=f(H')$ if $H$ and $H'$ are isomorphic. Given a graph function $f$ and a graph $G$, an $f$-colouring of $G$ is a mapping $c: V(G) o mathbb{N}$ such that every subgraph $H$ of $G$ receives at least $f(H)$ colours, i.e., $|c(H)| geq f(H)$. The $f$-chromatic number, $chi(f,G)$, is the minimum number of colours used in an $f$-colouring of $G$. The $f$-chromatic number of a graph is a natural generalization of the chromatic number of a graph introduced by Nev{s}etv{r}il and Ossena de Mendez. Intuitively, we would like to colour the vertices of a graph $G$ with minimum number of colours subject to the constraint that the number of colours assigned to certain subgraphs must be large enough. The original chromatic number of a graph and many of its generalizations are of this nature. For example, the chromatic number of a graph is the least number of colours needed to colour the vertices of the graph so that any subgraph isomorphic to $K_2$ receives $2$ colours. Acyclic chromatic number of a graph is the least number of colours needed to colour the vertices of the graph so that any subgraph isomorphic to $K_2$ receives $2$ colours, and each cycle receives at least $3$ colours. This thesis studies the game version of $f$-colouring of graphs. Suppose $G$ is a graph and $X$ is a set of colours. Two players, Alice and Bob, take turns colour the vertices of $G$ with colours from the set $X$. A partial colouring of $G$ is legal (with respect to graph function $f$) if for any subgraph $H$ of $G$, the sum of the number of colours used in $H$ and the number of uncoloured vertices of $H$ is at least $f(H)$. Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices but there is no legal colour for any of the uncoloured vertices. In the former case, Alice wins the game. In the latter case, Bob wins the game. The $f$-game chromatic number of $G$, $chi_g(f, G)$, is the least number of colours that the colour set $X$ needs to contain so that Alice has a winning strategy. Observe that if $|X| = |V(G)|$, then Alice always wins. So the parameter $chi_g(f,G)$ is well-defined. We define the $f$-game chromatic index on a graph $G$, $chi'(f,G)$, to be the $f$-game chromatic number on the line graph of $G$. A natural problem concerning the $f$-game chromatic number of graphs is for which graph functions $f$, the $f$-game chromatic number of $G$ is bounded by a constant for graphs $G$ from some natural classes of graphs. In case the $f$-game chromatic number of a class ${cal K}$ of graphs is bounded by a constant, one would like to find the smallest such constant. This thesis studies the $f$-game chromatic number or index for some special classes of graphs and for some special graph functions $f$. The graph functions $f$ considered are the following graph functions: 1. The $d$-relaxed function, ${ m Rel}_d$, is defined as ${ m Rel}_d(K_{1,d+1})=2$ and ${ m Rel}_d(H)=1$ otherwise. 2. The acyclic function, ${ m Acy}$, is defined as ${ m Acy}(K_2)=2$ and ${ m Acy}(C_n)=3$ for any $n geq 3$ and ${ m Acy}(H)=1$ otherwise. 3. The $i$-path function, ${ m Path}_i$, is defined as ${ m Path}_i(K_2)=2$ and ${ m Path}_i(P_i)=3$ and ${ m Path}_i(H)=1$ otherwise, where $P_i$ is the path on $i$ vertices. The classes of graphs considered in the thesis are outerplanar graphs, forests and the line graphs of $d$-degenerate graphs. In Chapter 2, we discuss the acyclic game chromatic number of outerplanar graphs. It is proved that for any outerplanar graph $G$, $chi_g({ m Acy},G) leq 7$. On the other hand, there is an outerplanar graph $G$ for which $chi_g({ m Acy},G) = 6$. So the best upper bound for $chi_g({ m Acy},G)$ for outerplanar graphs is either $6$ or $7$. Moreover, we show that for any integer $n$, there is a series-parallel graph $G_n$ with $chi_g({ m Acy}, G_n) > n$. In Chapter 3, we discuss the ${ m Path}_i$-game chromatic number for forests. It is proved that if $i geq 8$, then for any forest $F$, $chi_g({ m Path}_i, F) leq 9$. On the other hand, if $i leq 6$, then for any integer $k$, there is a tree $T$ such that $chi_g({ m Path}_i, T) geq k$. Chapter 4 studies the $d$-relaxed game chromatic indexes of $k$-degenerated graphs. It is proved that if $d geq 2k^2 + 5k-1$ and $G$ is $k$-degenerated, then $chi'_{ m g}({ m Rel}_d,G) leq 2k + frac{(Delta(G)+k-1)(k+1)}{d-2k^2-4k+2}$. On the other hand, for any positive integer $ d leq Delta-2$, there is a tree $T$ with maximum degree $Delta$ for which $chi'_g({ m Rel}_d, T) geq frac{2Delta}{d+3}$. Moreover, we show that $chi'_g({ m Rel}_d, G) leq 2$ if $d geq 2k + 2lfloor frac{Delta(G)-k}{2} floor +1$ and $G$ is a $k$-degenerated graph.

This thesis constructs special graphs with given circular chromatic numbers or circular flow numbers. Suppose $G=(V,E)$ is a graph and $rgeq 2$ is a real number. An $r$-coloring of a graph $G$ is a mapping $f:V ightarrow [0,r)$ such that for any adjacent vertices $x,y$ of $G$, $1leq |f(x)-f(y)|leq r-1$. The circular chromatic number $chi_c(G)$ is the least $r$ for which there exists an $r$-coloring of $G$. The circular chromatic number was introduced by Vince in 1988 in cite{vince}, where the parameter is called the {em star chromatic number} and denoted by $chi^*(G)$. Vince proved that for any rational number $k/dgeq 2$ there is a graph $G$ with $chi_c(G)=k/d$. In this thesis, we are interested in the existence of special graphs with given circular chromatic numbers. A graph $H$ is called a minor of a graph $G$ if $H$ can be obtained from $G$ by deleting some vertices and edges, and contracting some edges. A graph $G$ is called $H$-minor free if $H$ is not a minor of G. The well-known Hadwiger's conjecture asserts that for any positive integer $n$, any $K_n$-minor free graph $G$ is $(n-1)$-colorable. If this conjecture is true, then for any $K_n$-minor free graph $G$, we have $chi_c(G)leq n-1$. On the other hand, for any graph $G$ with at least one edge we have $chi_c(G)geq 2$. A natural question is this: Is it true that for any rational number $2leq rleq n-1$, there exist a $K_n$-minor free graph $G$ with $chi_c(G)=r$? For $n=4$, the answer is ``no". It was proved by Hell and Zhu in cite{hz98} that if $G$ is a $K_4$-minor free graph then either $chi_c(G)=3$ or $chi_c(G)leq 8/3$. So none of the rational numbers in the interval $(8/3,3)$ is the circular chromatic number of a $K_4$-minor free graph. For $ngeq 5$, Zhu cite{survey} proved that for any rational number $rin[2,n-2]$, there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$. The question whether there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$ for each rational number $rin(n-2,n-1)$ remained open. In this thesis, we answer this question in the affirmative. For each integer $ngeq 5$, for each rational number $rin[n-2,n-1]$, we construct a $K_n$-minor free graph $G$ with $chi_c(G)=r$. This implies that for each $ngeq 5$, for each rational number $rin[2,n-1]$, there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$. In case $n=5$, the $K_5$-minor free graphs constructed in this thesis are actually planar graphs. So our result implies that for each rational number $rin[2,4]$, there exists a planar graph $G$ with $chi_c(G)=r$. This result was first proved by Moser cite{moser} and Zhu cite{3-4}. To be precise, Moser cite{moser} proved that for each rational number $rin[2,3]$, there exist a planar graph $G$ with $chi_c(G)=r$, and Zhu cite{3-4} proved that for each rational number $rin[3,4]$, there exists a planar graph $G$ with $chi_c(G)=r$. Moser's and Zhu's proofs are quite complicated. Our construction is conceptually simpler. Moreover, for $ngeq 5$, $K_n$-minor free graphs, including the planar graphs are constructed with a unified method. For $K_4$-minor free graphs, although Hell and Zhu cite{hz98} proved that there is no $K_4$-minor free graph $G$ with $chi_c(G)in (8/3,3)$. The question whether there exists a $K_4$-minor free graph $G$ with $chi_c(G)=r$ for each rational number $rin[2,8/3]$ remained open. This thesis solves this problem: For each rational number $rin[2,8/3]$, we shall construct a $K_4$-minor free $G$ with $chi_c(G)=r$. This thesis also studies the relation between the circular chromatic number and the girth of $K_4$-minor free graphs. For each integer $n$, the supremum of the circular chromatic number of $K_4$-minor free graphs of odd girth (the length of shortest odd cycle) at least $n$ is determined. It is also proved that the same bound is sharp for $K_4$-minor free graphs of girth $n$. By a classical result of ErdH{o}s, for any positive integers $l$ and $n$, there exists a graph $G$ of girth at least $l$ and of chromatic number $n$. Using probabilistic method, Zhu cite{unique} proved that for each integer $l$ and each rational number $rgeq 2$, there is a graph $G$ of girth at least $l$ such that $chi_c(G)=r$. Construction of such graphs for $rgeq 3$ was given by Nev{s}etv{r}il and Zhu cite{nz}. The question of how to construct large girth graph $G$ with $chi_c(G)=r$ for given $rin(2,3)$ remained open. In this thesis, we present a unified method that constructs, for any $rgeq 2$, a graph $G$ of girth at least $l$ with circular chromatic number $chi_c(G) =r$. Graphs $G$ with $chi_c(G)=chi(G)$ have been studied extensively in the literature. Many families of graphs $G$ are known to satisfy $chi_c(G)=chi(G)$. However it remained as an open question as how to construct arbitrarily large $chi$-critical graphs $G$ of bounded maximum degree with $chi_c(G)=chi(G)$. This thesis presents a construction of such graphs. The circular flow number $Phi_c(G)$ is the dual concept of $chi_c(G)$. Let $G$ be a graph. Replace each edge $e=xy$ by a pair of opposite arcs $a=overrightarrow{xy}$ and $a^{-1}=overrightarrow{yx}$. We obtain a symmetric directed graph. Denote by $A(G)$ the set of all arcs of $G$. A chain is a mapping $f:A(G) ightarrow I!!R$ such that for each arc $a$, $f(a^{-1})=-f(a)$. A flow is a chain such that for each subset $X$ of $V(G)$, $sum_{ain[X,ar{X}]}f(a)=0$, where $[X,ar{X}]$ is the set of all arcs from $X$ to $V-X$. An $r$-flow is a flow such that for any arc $ain A(G)$ , $1leq |f(a)| leq r-1$. The circular flow number of $G$ is $Phi_c(G)=mbox{ inf}{r: G mbox{ admits a } rmbox{-flow}}$. It was conjectured by Tutte that every graph $G$ has $Phi_c(G)leq 5$. By taking the geometrical dual of planar graphs, Moser's and Zhu's results concerning circular chromatic numbers of planar graphs imply that for each rational number $rin[2,4]$, there is a graph $G$ with $Phi_c(G)=r$. The question remained open whether for each $rin(4,5)$, there exists a graph $G$ with $Phi_c(G)=r$. In this thesis, for each rational number $rin [4,5]$, we construct a graph $G$ with $Phi_c(G)=r$.

Thesis (M. Phil.)--University of Hong Kong, 2009. / Includes bibliographical references (leaves 61-66) Also available in print.

Thesis (M. Phil.)--University of Hong Kong, 2009. / Includes bibliographical references (p. 112-117). Also available in print.

No description available.