Motiviert durch strukturelle Eigenschaften molekularer Ähnlichkeitsnetzwerke werden die Evolution der größten Komponente eines Netzwerkes in zwei verschiedenen stochastischen Modellen, zufälligen Hypergraphen und zufälligen Schnittgraphen, untersucht. Zuerst wird bewiesen, dass die Anzahl der Knoten in der größten Komponente d-uniformer Hypergraphen einer Normalverteilung folgt. Der Beweis nutzt dabei ausschließlich probabilistische Argumente und keine enumerative Kombinatorik. Diesem grundlegenden Resultat folgen weitere Grenzwertsätze für die gemeinsame Verteilung von Knoten- und Kantenzahl sowie Sätze zur Zusammenhangswahrscheinlichkeit zufälliger Hypergraphen und zur asymptotischen Anzahl zusammenhängender Hypergraphen. Da das Hypergraphenmodell einige Eigenschaften der Realweltdaten nur unzureichend abbildet, wird anschließend die Evolution der größten Komponente in zufälligen Schnittgraphen, die Clustereigenschaften realer Netzwerke widerspiegeln, untersucht. Es wird gezeigt, dass zufällige Schnittgraphen sich von zufälligen (Hyper-)Graphen dadurch unterscheiden, dass (bei einer durchschnittlichen Nachbaranzahl von mehr als eins) weder die größte Komponente linear noch die zweitgrößte Komponente logarithmisch groß in Abhängigkeit von der Knotenzahl ist. Weiterhin wird ein Polynomialzeitalgorithmus zur Überdeckung der Kanten eines Graphen mit möglichst wenigen Cliquen (vollständigen Graphen) beschrieben und seine asymptotische Optimalität im Modell der zufälligen Schnittgraphen bewiesen. Anschließend wird die Entwicklung der chromatischen Zahl untersucht und gezeigt, dass zufällige Schnittgraphen mit hoher Wahrscheinlichkeit mittels verschiedener Greedystrategien optimal gefärbt werden können. Letztendlich zeigen Experimente auf realen Netzen eine Übereinstimmung mit den theoretischen Vorhersagen und legen eine gegenseitige Zertifizierung der Optimalität von Cliquen- und Färbungszahl durch Heuristiken nahe. / Motivated by structural properties of molecular similarity networks we study the behaviour of the component evolution in two different stochastic network models, that is random hypergraphs and random intersection graphs. We prove gaussian distribution for the number of vertices in the giant component of a random d-uniform hypergraph. We provide a proof using only probabilistic arguments, avoiding enumerative methods completely. This fundamental result is followed by further limit theorems concerning joint distributions of vertices and edges as well as the connectivity probability of random hypergraphs and the number of connected hypergraphs. Due to deficiencies of the hypergraph model in reflecting properties of the real--world data, we switch the model and study the evolution of the order of the largest component in the random intersection graph model which reflects some clustering properties of real--world networks. We show that for appropriate choice of the parameters random intersection graphs differ from random (hyper-)graphs in that neither the so-called giant component, appearing when the average number of neighbours of a vertex gets larger than one, has linear order nor is the second largest of logarithmic order in the number of vertices. Furthermore we describe a polynomial time algorithm for covering graphs with cliques, prove its asymptotic optimality in a random intersection graph model and study the evolution of the chromatic number in the model showing that, in a certain range of parameters, these random graphs can be coloured optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.

Made available in DSpace on 2015-03-04T18:50:59Z (GMT). No. of bitstreams: 1 thesis.pdf: 520664 bytes, checksum: a8423486c7ffd3a3ceff9cb2b60761ce (MD5) Previous issue date: 2008-03-14 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / The graph isomorphism problem has applications in several areas of science. This problem has not an efficient solution to its general case. In this work, we present the basic concepts of group theory, graph theory and quantum mechanics. We introduce the hidden subgroup problem and a known polynomial reduction of the graph isomorphism problem in its general case to the hidden subgroup problem on the symmetric group. We use a method that reduces the graph isomorphism problem to the group intersection problem. This method combines results from quantum computing and solvable group theory providing a efficient solution through a quantum algorithm to the graph isomorphism problem for the particular class of graphs. / O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.

Made available in DSpace on 2017-07-21T14:53:52Z (GMT). No. of bitstreams: 1 Lilian Paula Dambros.pdf: 8454108 bytes, checksum: f537a3cdf4444a7a5462e8b143ea3079 (MD5) Previous issue date: 2016-03-21 / This research entend to understand how the textbooks help to construction of social identities of race with class intersection. It has how goals analyzing four PNLD’s collections, of the year 2012 of high school and three PNLD’s collections, 2015, also high school, in order to understand how social identities of race, class-intersection, are represented these textbooks through speeches and multiliteracies. By analyzing the textbooks sought to answer the following questions: how the textbooks of English, suggested by PNLDs (2012 and 2015), build social identities of race and class? As the black racial identity and white racial identity are represented through literacies and multiliteracies resources of textbooks? The textbooks of English high school suggested by PNLDs 2012 and 2015, use the multiliteracies resources, enable reflections mentioned in Law 10,639 / 03? The theoretical contributions, which were the theoretical and methodological basis for this research, are supported in a literature review of studies that have been conducted with textbooks, like Ferreira (2012) and Barros (2013); about the literacies and multiliteracies bring to the discussion Kleiman (1995 and 2005), Kalantzis and Cope (2008) and Street (2014). To discuss the representation and I make use of identity Hall (2000), Bauman (2005) and Block (2006). This research also aims to reflect on the linguistic and educational policies such as PCN-LE (BRAZIL, 1998), OCEM-LE (2006), DCE-LE (PARANÁ, 2008), which tells the PNLD (BRAZIL, 2012 ) and the Federal Law 10.639 / 03 (BRAZIL, 2004). As for the methodology, was documentary analysis of linguistic and educational policies and written speeches and images produced in the English language textbooks, according to Moita Lopes (1996), Ferreira (2014), Herbele (2004), Wodak (2004) and Rojo (2009, 2012), taking into account the issue of multiliteracies. Also used the critical discourse analysis, according to Van Dijk (2012). After my analysis, I got the following final remarks: it is necessary that the teacher’s training be continuous, thus improving their knowledge about the existing racial prejudice in textbooks, the dominant ideologies brought through multiliteracies these and realize how much the textbooks influence the construction of identities of students. Teachers also need to encourage their students to a critical look at the differences, even if they are not being well represented by textbooks have analyzed because these are full of prejudice and ideologies that exclude black and poor, including the under representation of the characters, the representation of the less complex characters by means of stereotypes with defined spaces and subordinate manner. I hope, with this work, more high school teachers to understand the speeches conveyed to textbooks and start to reflect critically on the policies of the textbook as well as publishers and authors of such books. / A presente pesquisa pretendeu entender como os livros didáticos auxiliam na construção das identidades sociais de raça com intersecção de classe. Tendo como objetivo analisar quatro coleções do PNLD, ano de 2012 do Ensino Médio, mais três coleções do PNLD, ano de 2015, também do Ensino Médio, com o intuito de entender como as identidades sociais de raça, com intersecção de classe, são representadas nesses livros didáticos por meio dos discursos e dos multiletramentos. Ao analisar os livros didáticos busquei responder às seguintes questões: como os livros didáticos de língua inglesa, sugeridos pelos PNLDs (2012 e 2015), constroem as identidades sociais de raça e classe? Como a identidade racial negra e a identidade racial branca são representadas através dos letramentos e recursos de multiletramentos dos livros didáticos? Os livros didáticos de inglês do Ensino Médio sugeridos pelos PNLDs de 2012 e 2015, ao utilizarem os recursos de multiletramentos, possibilitam reflexões de que trata a Lei 10.639/03? Os aportes teóricos, que serviram de fundamentação teórico-metodológica para esta pesquisa, estão respaldados em uma revisão de literatura dos estudos que vêm sendo realizados com os livros didáticos, a exemplo de Ferreira (2012) e Barros (2013); a respeito dos letramentos e multiletramentos trago para a discussão Kleiman (1995 e 2005), Kalantzis e Cope (2008) e Street (2014). Para discutir a representação e identidade valho-me de Hall (2000), Bauman (2005) e Block (2006). A presente pesquisa, também pretende refletir acerca das políticas linguísticas e educacionais, tais como PCN-LE (BRASIL, 1998), OCEM-LE (2006), DCE-LE (PARANÁ, 2008), o que diz o PNLD (BRASIL, 2012) e a Lei Federal 10.639/03 (BRASIL, 2004). Quanto à metodologia, foi de análise documental das políticas linguística e educacionais e dos discursos escritos e imagens produzidas nos livros didáticos de língua inglesa, de acordo com Moita Lopes (1996), Ferreira (2014), Herbele (2004), Wodak (2004) e Rojo (2009, 2012), levando em consideração a questão dos multiletramentos. Também utilizei a análise crítica do discurso, de acordo com Van Dijk (2012). Após minha análise, cheguei as seguintes considerações finais: é necessário que a formação para professores seja contínua, melhorando, assim, seu conhecimento a respeito do preconceito racial existente nos LD, das ideologias dominantes trazidas por meio dos multiletramentos desses e percebam o quanto os LD influenciam na construção das identidades dos alunos. Os professores também precisam incentivar seus alunos para um olhar crítico sobre as diversidades, mesmo elas não sendo bem representadas pelos LD que analisei, pois esses estão repletos de preconceito e ideologias que exclui o negro e o pobre, entre elas a sub representação dos personagens, a representação menos complexas dos personagens, por meio de estereótipos, com espaços delimitados e de maneira subalterna. Espero, com este trabalho, que mais professores do Ensino Médio possam perceber os discursos veiculados aos livros didáticos e passem a refletir criticamente sobre as políticas do livro didático, assim como as editoras e os autores de tais livros.

<p>This thesis studies computational interpretations of the intuitionistic sequent<br />calculus with implicit and explicit structural rules, with focus on the systems<br />with intersection types. The contributions of the thesis are grouped into three<br />parts. In the first part intersection types are introduced into the lambda<br />Gentzen calculus. The second part presents an extension of the lambda<br />Gentzen calculus to a term calculus with resource control, i.e. with explicit<br />operators for contraction and weakening, and apropriate intersection type<br />assignment system which characterises strong normalisation in the proposed<br />calculus. In the third part both previously studied calculi are integrated into<br />one framework by introducing the notion of the resource control cube.</p> / <p>Ова дисертација се бави рачунским интерпретацијама<br />интуиционистичког секвентног рачуна са имплицитним и експлицитним<br />структурним правилима, са фокусом на типске системе са пресеком.<br />Оригинални резултати тезе су груписани у три целине. У првом делу су<br />типови са пресеком уведени у lambda Gentzen рачун. Други део<br />представља проширење lambda Gentzen рачуна на формални рачун са<br />контролом ресурса, тј. са експлицитним операторима контракције и<br />слабљења, као и одговарајући типски систем са пресеком који<br />карактерише јаку нормализацију у уведеном рачуну. У трећем делу оба<br />рачуна су интегрисана у заједнички оквир увођењем структуре resource<br />control cube.</p> / <p>Ova disertacija se bavi računskim interpretacijama<br />intuicionističkog sekventnog računa sa implicitnim i eksplicitnim<br />strukturnim pravilima, sa fokusom na tipske sisteme sa presekom.<br />Originalni rezultati teze su grupisani u tri celine. U prvom delu su<br />tipovi sa presekom uvedeni u lambda Gentzen račun. Drugi deo<br />predstavlja proširenje lambda Gentzen računa na formalni račun sa<br />kontrolom resursa, tj. sa eksplicitnim operatorima kontrakcije i<br />slabljenja, kao i odgovarajući tipski sistem sa presekom koji<br />karakteriše jaku normalizaciju u uvedenom računu. U trećem delu oba<br />računa su integrisana u zajednički okvir uvođenjem strukture resource<br />control cube.</p>

Consider distinct latin squares, L and M, of order n. Then the pair (T1, T2) where T1 = L \M and T2 = M \ L is called a latin bitrade. Furthermore T1 and T2 are referred to as latin trades, in which T2 is said to be a disjoint mate of T1 (and vice versa). Drápal (1991) showed that, under certain conditions, a partition of an equilateral triangle of side length n, where n is some integer, into smaller, integer length sided equilateral triangles gives rise to a latin trade within the latin square based on the addition table for the integers modulo n. A partial latin square P of order n is said to be completable if there exists a latin square L of order n such that P ⊆ L. If there is only one such possible latin square, L, of order n then P is said to be uniquely completable and P is called a defining set of L. Furthermore, if C is a uniquely completable partial latin square such that no proper subset of C is uniquely completable, C is said to be a critical set or a minimal defining set. These concepts, namely latin trades and defining sets in latin squares, are intimately connected by the following observation. If L is a latin square and D ⊆ L is a defining set, then D intersects all latin bitrades for which one mate is contained in L. In Part I of this thesis Dr´apal’s result is applied to investigate the structure of certain defining sets in latin squares. The results that are obtained are interesting in themselves; furthermore, the geometric approach to the problem yields additional appealing results. These geometric results are discussed in Chapters 3, 4, 5 and 6. They pertain to partitioning regions (polygons in R2 that satisfy certain obvious conditions) into equilateral, integer length sided, triangles, such that no point, in the region, is a corner of more than three distinct triangles. In Chapter 2 one of the main two theorems on defining sets is established, as is a method for using the above geometric results to prove the nonexistence of certain types of defining sets. In Part II of this thesis, intersection problems, for latin squares and Steiner triple systems, are considered. The seminal works, for problems of these types, are due to Lindner and Rosa (1975) and Fu (1980). A natural progression, from the established literature, for intersection problems between elements in a pair of latin squares or Steiner triple systems is to problems in which the intersection is composed of a number of disjoint configurations (isomorphic copies of some specified partial triple system). In this thesis solutions to two intersection problems for disjoint configurations are detailed. An m-flower, (F,F), is a partial triple system/configuration, such that: F = {{x, yi, zi} | {yi, zi} ∩ {yj , zj} = ∅, for 0 ≤ i, j ≤ m − 1, i 6= j}; and F = UX∈FX. The first such problem considered in this thesis asks for necessary and sufficient conditions for integers k and m ≥ 2 such that a pair of latin squares of order n exists that intersect precisely in k disjoint m-flowers. The necessary terminology, constructions, lemmas and proof for this result are contained in Chapters 7, 8 and 9. The second such problem considered in this thesis asks for necessary and sufficient conditions for integers k such that a pair of Steiner triple systems of order u exists that intersect precisely in k disjoint 2-flowers. This result relies on the solution to the latin square problem and an additional result from Chapter 9. The further constructions and lemmas used to prove this result are detailed in Chapter 10.

In 1976, Springer defined a correspondence making a link between the irreducible ordinary (characteristic zero) representations of a Weyl group and the geometry of the associated nilpotent variety. In this thesis, we define a modular Springer correspondence (in positive characteristic), and we show that the decomposition numbers of a Weyl group (for example the symmetric group) are particular cases of decomposition numbers for equivariant perverse sheaves on the nilpotent variety. We calculate explicitly the decomposition numbers associated to the regular and subregular classes, and to the minimal and trivial classes. We determine the correspondence explicitly in the case of the symmetric group, and show that James's row and column removal rule is a consequence of a smooth equivalence of nilpotent singularities obtained by Kraft and Procesi. The first chapter contains generalities about perverse sheaves with Z_l and F_l coefficients.

L'objectif principal de cette thèse est la description des propriétés de taille et de grande intersection des ensembles apparaissant lors de l'analyse multifractale de certains processus stochastiques. Dans ce but, nous introduisons de nouvelles classes d'ensembles à grande intersection associées à des fonctions de jauge générales et nous prouvons, à l'aide de techniques d'ubiquité, des résultats d'appartenance à ces classes pour certains ensembles limsup. Cela nous permet en particulier de décrire exhaustivement les propriétés de taille et de grande intersection des ensembles issus de la théorie classique de l'approximation diophantienne comme l'ensemble des points bien approchables par des rationnels ou l'ensemble des nombres de Liouville. Nous fournissons aussi des résultats du même type lorsque les rationnels intervenant dans l'approximation doivent vérifier certaines conditions, comme les conditions de Besicovitch. Nos techniques d'ubiquité nous permettent en outre de décrire complètement les propriétés de taille et de grande intersection des ensembles intervenant dans l'analyse multifractale des processus de Lévy et d'un modèle de séries lacunaires d'ondelettes. Nous obtenons des résultats similaires pour un nouveau modèle de séries aléatoires d'ondelettes dont les coefficients sont corrélés via une chaîne de Markov indexée par un arbre. Nous déterminons en particulier la loi du spectre de singularités de ce modèle. Pour mener cette étude, nous nous intéressons à une large classe de fractals aléatoires généralisant les constructions récursives aléatoires précédemment introduites par de nombreux auteurs.

<p>This work applies intersectionality to five Somali women self-narratives and focuses on their identities and positions in Swedish society, but also their relation to Somali society. Since people constructs in relation to the environment, this work studies the impact of environmental confirmations of their own self. Intersectionality is brought into the social work with an operational attempt, and shows how critics of power and interplay between theories and empirics can provide new knowledge. Intersectionality also demands some alterations of the social constructionists’ idea of the ego. Therefore this work outline a model of analysis that considers the critic of power. According to this work, intersectionality implies that social work is essentially about power. The women’s egos seem to be closely united different strongly. The more different identifications the women describes and the more ambivalent they are allowed to be in different milieus, the greater assets has the women in their ability to move between milieus and to pass between positions of power. But the tighter united some of their identifications are in their egos; the firmer is their assumptions of what constitute a good behaviour. And the stronger united the ego is, the space to pass through positions of power in different arenas is shrinking.</p><p>This work emphasizes the importance of making shifts of power in identification categories visible in order to localize resistance strategies among exposed individuals. This work also suggest that social work should consider the supplementary vulnerable situation that signify the position in intersection between power orders and contradictory norms, since that could lead to too simplified conclusions that create additional isolation. Being sensitive to the experience and resolution of these women’s own experiences and resolutions is therefore crucial in achieving good social work. Accordingly, lack of knowledge is an obstacle to resist discrimination and oppression. Another conclusion is that social work and social politics should aim to strengthen the ego of immigrant women in order to release their driving forces that in turn may lead to participation, not only to the Swedish society. These Somali women appear as peace endeavours, whose political voices has been marginalised both in the Somali and the Swedish context, which obstacle peace making in the Somali society.</p>

This work applies intersectionality to five Somali women self-narratives and focuses on their identities and positions in Swedish society, but also their relation to Somali society. Since people constructs in relation to the environment, this work studies the impact of environmental confirmations of their own self. Intersectionality is brought into the social work with an operational attempt, and shows how critics of power and interplay between theories and empirics can provide new knowledge. Intersectionality also demands some alterations of the social constructionists’ idea of the ego. Therefore this work outline a model of analysis that considers the critic of power. According to this work, intersectionality implies that social work is essentially about power. The women’s egos seem to be closely united different strongly. The more different identifications the women describes and the more ambivalent they are allowed to be in different milieus, the greater assets has the women in their ability to move between milieus and to pass between positions of power. But the tighter united some of their identifications are in their egos; the firmer is their assumptions of what constitute a good behaviour. And the stronger united the ego is, the space to pass through positions of power in different arenas is shrinking. This work emphasizes the importance of making shifts of power in identification categories visible in order to localize resistance strategies among exposed individuals. This work also suggest that social work should consider the supplementary vulnerable situation that signify the position in intersection between power orders and contradictory norms, since that could lead to too simplified conclusions that create additional isolation. Being sensitive to the experience and resolution of these women’s own experiences and resolutions is therefore crucial in achieving good social work. Accordingly, lack of knowledge is an obstacle to resist discrimination and oppression. Another conclusion is that social work and social politics should aim to strengthen the ego of immigrant women in order to release their driving forces that in turn may lead to participation, not only to the Swedish society. These Somali women appear as peace endeavours, whose political voices has been marginalised both in the Somali and the Swedish context, which obstacle peace making in the Somali society.

The boxicity of a graph G, denoted as box(G), is the minimum dimension d for which each vertex of G can be mapped to a d-dimensional axis-parallel box in Rd such that two boxes intersect if and only if the corresponding vertices of G are adjacent. An axis-parallel box is a generalized rectangle with sides parallel to the coordinate axes. If additionally, we restrict all sides of the rectangle to be of unit length, the new parameter so obtained is called the cubicity of the graph G, denoted by cub(G). F.S. Roberts had shown that for a graph G with n vertices, box(G) ≤ and cub(G) ≤ . A minimum vertex cover of a graph G is a minimum cardinality subset S of the vertex set of G such that each edge of G has at least one endpoint in S. We show that box(G) ≤ +1 and cub(G)≤ t+ ⌈log2(n −t)⌉−1 where t is the cardinality of a minimum vertex cover. Both these bounds are tight. For a bipartite graph G, we show that box(G) ≤ and this bound is tight. We observe that there exist graphs of very high boxicity but with very low chromatic num-ber. For example, there exist bipartite (2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then the chromatic number also has to be very high. In particular, we show that if box(G) = −s, s ≥ 02, then x(G) ≥ where X(G) is the chromatic number of G. We also discuss some known techniques for findingan upper boundon the boxicityof a graph -representing the graph as the intersection of graphs with boxicity 1 (boxicity 1 graphs are known as interval graphs) and covering the complement of the graph by co-interval graphs (a co-interval graph is the complement of an interval graph).