Rings, Group Rings, and Their Graphs

We associate some graphs to a ring R and we investigate the interplay between the ring-theoretic properties of R and the graph-theoretic properties of the graphs associated to R. Let Z(R) be the set of zero-divisors of R. We define an undirected graph ᴦ(R) with nonzero zero-divisors as vertices and distinct vertices x and y are adjacent if xy=0 or yx=0. We investigate the Isomorphism Problem for zero-divisor graphs of group rings RG. Let Sk denote the sphere with k handles, where k is a non-negative 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 annihilating-ideal 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 annihilating-ideal graphs have finite genus. Finally, we extend the definition of the annihilating-ideal graph to non-commutative rings.

Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles

The conjecture claiming that every planar graph is acyclic 5-choosable[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, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, 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 i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.

Edge-choosability of Planar Graphs

According 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 7-cycles with ∆(G)≠5,6 , or without adjacent 4-cycles with ∆(G)≠5, or with no 3-cycles adjacent to 5-cycles, then G is edge-(∆ + 1)-choosable.

Subliminal Exposure to Empathy Primes: A New Method to Reduce Intergroup Bias?

An abundant literature has demonstrated the benefits of empathy for intergroup relations (e.g., Batson, Chang, Orr, & Rowland, 2002). In addition, empathy has been identified as the mechanism by which various successful prejudice-reduction procedures impact attitudes and behaviour (e.g., Costello & Hodson, 2010). However, standard explicit techniques used in empathy-prejudice research have a number of potential limitations (e.g., resistance; McGregor, 1993). The present project explored an alternative technique, subliminally priming (i.e., outside of awareness) empathy-relevant terms (Study 1), or empathy itself (Study 2). Study 1 compared the effects of exposure to subliminal empathy-relevant primes (e.g., compassion) versus no priming and priming the opposite of empathy (e.g., indifference) on prejudice (i.e., negative attitudes), discrimination (i.e., resource allocation), and helping behaviour (i.e., willingness to empower, directly assist, or expect group change) towards immigrants. Relative to priming the opposite of empathy, participants exposed to primes of empathy-relevant constructs expressed less prejudice and were more willingness to empower immigrants. In addition, the effects were not moderated by individual differences in prejudice-relevant variables (i.e., Disgust Sensitivity, Intergroup Disgust-Sensitivity, Intergroup Anxiety, Social Dominance Orientation, Right-wing Authoritarianism). Study 2 considered a different target category (i.e., Blacks) and attempted to strengthen the effects found by comparing the impact of subliminal empathy primes (relative to no prime or subliminal primes of empathy paired with Blacks) on explicit prejudice towards marginalized groups and Blacks, willingness to help marginalized groups and Blacks, as well as implicit prejudice towards Blacks. In addition, Study 2 considered potential mechanisms for the predicted effects; specifically, general empathy, affective empathy towards Blacks, cognitive empathy towards Blacks, positive mood, and negative mood. Unfortunately, using subliminal empathy primes “backfired”, such that exposure to subliminal empathy primes (relative to no prime) heightened prejudice towards marginalized groups and Blacks, and led to stronger expectations that marginalized groups and Blacks improve their own situation. However, exposure to subliminal primes pairing empathy with Blacks (relative to subliminal empathy primes alone) resulted in less prejudice towards marginalized groups and more willingness to directly assist Blacks, as expected. Interestingly, exposure to subliminal primes of empathy paired with Blacks (vs. empathy alone) resulted in more pro-White bias on the implicit prejudice measure. Study 2 did not find that the potential mediators measured explained the effects found. Overall, the results of the present project do not provide strong support for the use of subliminal empathy primes for improving intergroup relations. In fact, the results of Study 2 suggest that the use of subliminal empathy primes may even backfire. The implications for intergroup research on empathy and priming procedures generally are discussed.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations

Ordered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering- Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other state-of-the-art DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

Backbone Colouring of Graphs

Consider an undirected graph G and a subgraph of G, H. A q-backbone k-colouring 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 k-colouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone k-colouring of (G,T) is at most 4 if G is a connected C4-free planar graph or non-bipartite C5-free planar graph or Cj-free, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2-backbone k-colouring 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)| ≥ k-2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In 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 Merriam-Webster 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.

Dynamics in large scale networks

In 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ási-Albert random graph. We establish some bounds on the number of motifs in this graph.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

Fair Production and Allocation of an Excludable Nonrival Good

We study fairness in economies with one private good and one partially excludable nonrival good. A social ordering function determines for each profile of preferences an ordering of all conceivable allocations. We propose the following Free Lunch Aversion condition: if the private good contributions of two agents consuming the same quantity of the nonrival good have opposite signs, reducing that gap improves social welfare. This condition, combined with the more standard requirements of Unanimous Indifference and Responsiveness, delivers a form of welfare egalitarianism in which an agent's welfare at an allocation is measured by the quantity of the nonrival good that, consumed at no cost, would leave her indifferent to the bundle she is assigned.

Consistent Rationalizability

Consistency of a binary relation requires any preference cycle to involve indifference only. As shown by Suzumura (1976b), consistency is necessary and sufficient for the existence of an ordering extension of a relation. Because of this important role of consistency, it is of interest to examine the rationalizability of choice functions by means of consistent relations. We describe the logical relationships between the different notions of rationalizability obtained if reflexivity or completeness are added to consistency, both for greatest-element rationalizability and for maximal-element rationalizability. All but one notion of consistent rationalizability are characterized for general domains, and all of them are characterized for domains that contain all two-element subsets of the universal set.

Les obligations du franchiseur : étude du droit civil et du guide d'Unidroit sur les accords internationaux de franchise principale

"Mémoire présenté à la Faculté des études supérieures en vue de l'obtention du grade de Maîtrise en droit (LL.M.)". Ce mémoire a été accepté à l'unanimité et classé parmi les 15% des mémoires de la discipline.

The placebo effect: international patent law and the protection of traditional plant medicine

Une préoccupation essentielle traverse cette thèse: l'indifférence systémique de la Loi internationale sur la propriété intellectuelle a l'égard des savoirs traditionnels autochtones. De manière générale, un écart semble d'ailleurs croissant entre l'importance des accords internationaux sur les questions d'intérêt commercial et ceux de nature sociale. Les savoirs traditionnels autochtones sur les plantes médicinales sont particulièrement désavantagés dans ce système dichotomique puisqu'ils sont non seulement à l'origine d'énormes profits commerciaux mais se trouvent aussi au cœur de multiples croyances propres à ces sociétés. L'Accord sur les aspects des droits de propriété intellectuelle qui touchent au commerce (ADPIC) de l'Organisation mondiale du commerce (OMC) a cristallisé le souci de la législation internationale à l'égard d'une protection efficace des intérêts commerciaux. Deux années auparavant, la Convention sur la diversité biologique (CDB) était signée, traduisant une préoccupation à l'égard du développement durable, et elle devenait le premier accord international à tenir compte des savoirs traditionnels autochtones. On considère souvent que ces deux accords permettent l'équilibre du développement commercial et durable, requis par l'économie internationale. Après plus ample examen, on a plutôt l'impression que l'idée d'une CDB défendant, avec succès et efficacité, la nécessité du développement durable et des savoirs traditionnels autochtones contre les pressions opposées de l'ADPIC et de l'OMC est, au mieux, simpliste. La thèse explore également la fonction de la Loi sur les brevets dans la création d’industries, notamment pharmaceutique, et la manière dont ces industries influencent la législation nationale et en particulier internationale. De même, elle traite du rôle que jouent les brevets dans l'affaiblissement et la dépossession des peuples autochtones dotés de savoirs traditionnels sur les plantes médicinales, conduisant à une situation ou ces savoirs sont marginalisés ainsi que leurs détenteurs. La thèse aborde les failles institutionnelles du système juridique international qui permet une telle situation et indique l'urgente nécessité d'examiner attentivement les inégalités économiques et sociales au Nord comme au Sud, et non seulement entre eux. Finalement, la thèse suggère que la législation internationale gagnerait à s'inspirer des diverses traditions juridiques présentes à travers le monde et, dans ce cas particulier, peut être les détenteurs des connaissances traditionnelles concernant les plantes médicinales seront mieux servi par le droit des obligations.

Le Banquet de Platon : l'apologie d'Alcibiade ou les paradoxes d'Éros

Ce mémoire cherche à évaluer la culpabilité de Socrate face à l’échec et à la corruption d’Alcibiade, telle que la question se pose dans le Banquet de Platon. Il comprend quatre chapitres. Le premier démontre que le cadre dramatique lui-même fait occuper une place centrale à la vie et au déclin d’Alcibiade et au problème de la responsabilité de Socrate face aux accusations de corruption de la jeunesse qui ont pesé sur lui. Le deuxième chapitre interprète le discours d’Alcibiade comme une tentative de disculpation qui repose sur une critique acerbe du comportement de Socrate. Il se serait détourné de Socrate et de ses enseignements en raison de son ironie, de son arrogance et de son indifférence – de son hybris. Le troisième chapitre étudie le discours de Socrate sur l’accession à la beauté intelligible. Il expose la nature particulière de son éros, qui repose sur l’ironie et l’inversion des rôles comme moyens d’exhorter à la philosophie. Le quatrième chapitre pose la question de l’efficacité de ce type de pédagogie et de la responsabilité du philosophe vis-à-vis de ses disciples. L’étude conclut que l’amour et l’ironie de Socrate sont essentiellement des moyens d’inviter l’autre à se remettre lui-même en question et à prendre soin de son âme. Socrate n’est donc pas coupable d’avoir corrompu Alcibiade. La faute est entièrement celle du jeune homme. Il s’est montré incapable, par égocentrisme et fierté excessive, de réagir correctement à l’énigme posée par le comportement érotique de Socrate.