En aquesta tesi s'estudien diferents problemes en el camp de la combinatòria i la teoria de grafs, utilitzant el mètode probabilístic. Aquesta tècnica, introduïda per Erdős , ha esdevingut una eina molt potent per tal de donar proves existencials per certs problemes en diferents camps de les matemàtiques on altres mètodes no ho han aconseguit. Un dels seus principals objectius és l'estudi del comportament de les variables aleatòries. El cas en que aquestes variables compten el nombre d'esdeveniments dolents que tenen lloc en una estructura combinatòria és de particular interès. La idea del Paradigma de Poisson és estimar la probabilitat que tots aquests esdeveniments dolents no succeeixin a la vegada, quan les dependències entre ells són febles o escasses. En tal cas, aquesta probabilitat s'hauria de comportar de forma similar al cas on tots els esdeveniments són independents. El Lema Local de Lovász o la Desigualtat de Suen són exemples d'aquesta idea. L'objectiu de la tesi és estudiar aquestes tècniques ja sigui proveint-ne noves versions, refinant-ne les existents per casos particulars o donant-ne noves aplicacions. A continuació s'enumeren les principals contribucions de la tesi. La primera part d'aquesta tesi estén un resultat d' Erdős i Spencer sobre transversals llatins. Els autors proven que qualsevol matriu d'enters on cap nombre apareix massa vegades, admet un transversal on tots els nombres són diferents. Això equival a estudiar els aparellaments multicolors en aresta-coloracions de grafs complets bipartits. Sota les mateixes hipòtesis que, es donen resultats sobre el nombre d'aquests aparellaments. Les tècniques que s'utilitzen estan basades en l'estratègia desenvolupada per Lu i Székely. En la segona part d'aquesta tesi s'estudien els codis identificadors. Un codi identificador és un conjunt de vèrtexs tal que tots els vèrtexs del graf tenen un veïnatge diferent en el codi. Aquí s'estableixen cotes en la mida d'un codi identificador mínim en funció dels graus i es resol parcialment una conjectura de Foucaud et al.. En un altre capítol, es mostra que qualsevol graf suficientment dens conté un subgraf que admet un codi identificador òptim. En alguns casos, provar l'existència d'un cert objecte és trivial. Tot i així, es poden utilitzar les mateixes tècniques per obtenir resultats d'enumeració. L'estudi de patrons en permutacions n'és un bon exemple. A la tercera part de la tesi es desenvolupa una nova tècnica per tal d'estimar el nombre de permutacions d'una certa llargada que eviten còpies consecutives d'un patró donat. En particular, es donen cotes inferiors i superiors per a aquest nombre. Una de les conseqüències és la prova de la conjectura CMP enunciada per Elizalde i Noy així com nous resultats en el comportament de la majoria dels patrons. En l'última part de la tesi s'estudia la Conjectura Lonely Runner, enunciada independentment per Wills i Cusick i que té múltiples aplicacions en diferents camps de les matemàtiques. Aquesta coneguda conjectura diu que per qualsevol conjunt de corredors que corren al llarg d'un cercle unitari, hi ha un moment on tots els corredors estan suficientment lluny de l'origen. Aquí, es millora un resultat de Chen ampliant la distància de tots els corredors a l'origen. També s'estén el teorema del corredor invisible de Czerwiński i Grytczuk . / In this thesis we study different problems in combinatorics and in graph theory by means of the probabilistic method. This method, introduced by Erdös, has become an extremely powerful tool to provide existential proofs for certain problems in different mathematical branches where other methods had failed utterly. One of its main concerns is to study the behavior of random variables. In particular, one common situation arises when these random variables count the number of bad events that occur in a combinatorial structure. The idea of the Poisson Paradigm is to estimate the probability of these bad events not happening at the same time when the dependencies among them are weak or rare. If this is the case, this probability should behave similarly as in the case where all the events are mutually independent. This idea gets reflected in several well-known tools, such as the Lovász Local Lemma or Suen inequality. The goal of this thesis is to study these techniques by setting new versions or refining the existing ones for particular cases, as well as providing new applications of them for different problems in combinatorics and graph theory. Next, we enumerate the main contributions of this thesis. The first part of this thesis extends a result of Erdös and Spencer on latin transversals [1]. They showed that an integer matrix such that no number appears many times, admits a latin transversal. This is equivalent to study rainbow matchings of edge-colored complete bipartite graphs. Under the same hypothesis of, we provide enumerating results on such rainbow matchings. The second part of the thesis deals with identifying codes, a set of vertices such that all vertices in the graph have distinct neighborhood within the code. We provide bounds on the size of a minimal identifying code in terms of the degree parameters and partially answer a question of Foucaud et al. On a different chapter of the thesis, we show that any dense enough graph has a very large spanning subgraph that admits a small identifying code. In some cases, proving the existence of a certain object is trivial. However, the same techniques allow us to obtain enumerative results. The study of permutation patterns is a good example of that. In the third part of the thesis we devise a new approach in order to estimate how many permutations of given length avoid a consecutive copy of a given pattern. In particular, we provide upper and lower bounds for them. One of the consequences derived from our approach is a proof of the CMP conjecture, stated by Elizalde and Noy as well as some new results on the behavior of most of the patterns. In the last part of this thesis, we focus on the Lonely Runner Conjecture, posed independently by Wills and Cusick and that has multiple applications in different mathematical fields. This well-known conjecture states that for any set of runners running along the unit circle with constant different speeds and starting at the same point, there is a moment where all of them are far enough from the origin. We improve the result of Chen on the gap of loneliness by studying the time when two runners are close to the origin. We also show an invisible runner type result, extending a result of Czerwinski and Grytczuk.

La tesi consta de dues parts. En la primera s'estenen els resultats i tècniques de Fabbri et al. 2005 per estudiar la dinàmica combinatòria, el <<forcing>> i l'entropia topològica de certes aplicacions triangulars al cilindre forçades quasiperiòdicament. Aquesta teoria dóna com a corol.lari una demostració més estructurada del Teorema de Sharkovski per aquest cas, demostrat inicialment a Fabbri et al., 2005. Quant a l'entropia es defineix la noció de ferradura en aquest context i es prova, com en el cas de l'interval, que si una d'aquestes funcions té una s-ferradura llavors la seva entropía topològica és més gran o igual a log s. D'això se'n dedueixen fites inferior de l'entropia en funció dels períodes de les orbites periòdiques. Això representa una extensió dels resultats anàlegs a l'interval a aquest context. En el context anterior sorgeix de manera natural la següent pregunta: El Teorema de Sharkovsky es compleix restringit a corbes en lloc de bandes generals? L'objectiu de la segona part de la memòria és el de respondre a aquesta pregunta de forma negativa mitjançant un contraexample: Es construeix una funció que té una òrbita periòdica de període 2 de corbes (que són, de fet, els cercles superiors i inferiors del cilindre) i sense cap corba invariant (solament té una pseudocorba invariant). En particular, això demostra que hi ha aplicacions triangulars al cilindre forçades quasiperiòdicament sense corbes invariants. Aquest és el primer resultat analític d'aquesta naturalesa que apareix a la literatura malgrat l'existencia d'evidències numèriques prèvies en aquest sentit. Els resultats obtinguts són solament una primera fase en la comprensió analítica/topològica de la dinàmica d'aquestes aplicacions, el que obra una via de treball futura. / The thesis consists of two parts. In the first we aim at extending the results and techniques from Fabbri et al. 2005 to study the Combinatorial Dynamics, the <<forcing>> and the topological Entropy of certain quasiperiodically forced skew-product on the cylinder. This theory gives a structured demonstration from the Sharkovski Theorem as a corollary, proved initially in Fabbri et al., 2005. About entropy defines the notion of horseshoe in this context and shwow, as in the interval case, if one of these functions has a s-horseshoe then its topological entropy is greater than or equal to log s. It follows lower entropy based on periodic orbits periods. This represents an similar extension to the results a l'interval in this context. In the above context arises naturally the following question: Sharkovsky theorem holds restricted curves instead of bands general? The aim of the second part of the report is to answer this question negatively by a contraexample: It constructs a function that has two curves as periodic orbit of period 2 (which are, in fact, the upper and lower circles cylinder) with no invariant curve (only has an invariant pseudo-curve). In particular, this shows that there are quasiperiodically forced skew-product on the cylinder without invariant curves. This is the first analytical result of this kind appearing in the literature despite the existence of previous numerical evidence in this regard. The results are only the first stage in understanding analytic/topological dynamics of these applications, which work via a future job.

The objective of this thesis is to study cages, constructions and properties of such families of graphs. For this, the study of graphs without short cycles plays a fundamental role in order to develop some knowledge on their structure, so we can later deal with the problems on cages. Cages were introduced by Tutte in 1947. In 1963, Erdös and Sachs proved that (k, g) -cages exist for any given values of k and g. Since then, large amount of research in cages has been devoted to their construction. In this work we study structural properties such as the connectivity, diameter, and degree regularity of graphs without short cycles. In some sense, connectivity is a measure of the reliability of a network. Two graphs with the same edge-connectivity, may be considered to have different reliabilities, as a more refined index than the edge-connectivity, edge-superconnectivity is proposed together with some other parameters called restricted connectivities. By relaxing the conditions that are imposed for the graphs to be cages, we can achieve more refined connectivity properties on these families and also we have an approach to structural properties of the family of graphs with more restrictions (i.e., the cages). Our aim, by studying such structural properties of cages is to get a deeper insight into their structure so we can attack the problem of their construction. By way of example, we studied a condition on the diameter in relation to the girth pair of a graph, and as a corollary we obtained a result guaranteeing restricted connectivity of a special family of graphs arising from geometry, such as polarity graphs. Also, we obtained a result proving the edge superconnectivity of semiregular cages. Based on these studies it was possible to develop the study of cages. Therefore obtaining a relevant result with respect to the connectivity of cages, that is, cages are k/2-connected. And also arising from the previous work on girth pairs we obtained constructions for girth pair cages that proves a bound conjectured by Harary and Kovács, relating the order of girth pair cages with the one for cages. Concerning the degree and the diameter, there is the concept of a Moore graph, it was introduced by Hoffman and Singleton after Edward F. Moore, who posed the question of describing and classifying these graphs. As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage. The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth (bipartite Moore graphs) as well as odd girth, and again these graphs are cages. Thus, Moore graphs give a lower bound for the order of cages, but they are known to exist only for very specific values of k, therefore it is interesting to study how far a cage is from this bound, this value is called the excess of a cage. We studied the excess of graphs and give a contribution, in the sense of the work of Biggs and Ito, relating the bipartition of girth 6 cages with their orders. Entire families of cages can be obtained from finite geometries, for example, the graphs of incidence of projective planes of order q a prime power, are (q+1, 6)-cages. Also by using other incidence structures such as the generalized quadrangles or generalized hexagons, it can be obtained families of cages of girths 8 and 12. In this thesis, we present a construction of an entire family of girth 7 cages that arises from some combinatorial properties of the incidence graphs of generalized quadrangles of order (q,q).

Orientador: Marcelo Carbone Carneiro / Banca: Adrian Oscar Dongo Montoya / Banca: Fernando Becker / Resumo: Esta dissertação discute a importância da experiência na formação da noção espacial, apresentando primeiramente este tema através dos filósofos Descartes, Hume e Kant, para depois elucidar esta questão por intermédio da investigação epistemológica proposta por Piaget. Com esses referenciais buscamos apresentar uma contribuição à Educação e particularmente ao Ensino de Ciências à medida que verificamos uma visão racionalista, uma empirista, uma apriorista e por último uma construtivista, a qual referendamos esta última como a mais adequada, à medida que reconhece o conhecimento como uma construção, que respeita os estágios de desenvolvimento cognitivo dos sujeitos e que ainda busca melhores métodos que possibilitem uma melhor aprendizagem e um maior domínio e construção de conhecimentos científicos / Abstract: This essay discusses the important of experience in the spatial notion formation, presenting firstly this discussion through the following philosophers: Descartes, Hume and Kant, to then, clarify this question through the epistemological investigation proposed by Piaget. On this basis, we aimed at presenting a contribution to Education and, particularly, to Science Teaching as we present a rationalistic, empirical, aprioristic and finally a constructivist view, being the last one considered the most adequate, once it recognizes knowledge as a construtction, respects the individual's cognitive development stages and, also searches for more appropriate methods that enable better learning, besides a greater domain and construction of scientific knowledge / Mestre

Orientador: Antonio José Accioly / Mestre

L'objectiu d'aquesta tesi és aprofondir en l'estudi d'una certa família de dígrafs, els dígrafs de prefix-cicle, donant nous detalls sobre la seva estructura, noves maneres d'enfocar el seu estudi, i dissenyant bons esquemes de comunicació. Es completa d'aquesta forma l'estudi iniciat per altres autors i s'en refoça el seu interès com a bon model de xarxa d'interconnexió.

Neste trabalho fazemos um breve estudo de Álgebras de Operadores, mais especificamente Álgebras-C* e Álgebras de von Neumann. O objetivo é expor alguns resultados que seriam os análogos não-comutativos de teoremas em Teoria da Medida e Teoria Rrgódica. Inicialmente, enunciamos alguns resultados de Análise Funcional e Teoria Espectral, muitos destes sendo demonstrados, com ênfase especial aos que dizem respeito µas álgebras. Com isso, dispomos das ferramentas necessárias para falarmos de alguns tópicos da então chamada Teoria da Integração Não-Comutativa. Uma desigualdade tipo Jensen é provada e, com o teorema de Radon-Nikodym para funcionais normais positivos, construimos uma esperança condicional, provando que esta possui as mesmas propriedades da esperança condicional da Teoria das Probabilidades. Dada a Esperança Condicional, objeto este que faz parte do cenário atual de pesquisa na área de Álgebra de Operadores e que está relacionado com resultados fundamentais tal como o Índice de Jones, passamos à definição da Entropia de Connes-Stormer. Finalizamos o trabalho analisando esta entropia, que é a versão para as álgebras de von Neumann da entropia Kolmogorov-Sinai em Teoria Ergódica. Provamos algumas pro- priedades que são análogas às do conceito clássico de entropia e indicamos uma aplicação da mesma. O texto não possui resultados originais, trata-se apenas de uma releitura de artigos usando versões mais recentes de alguns teoremas.

Neste trabalho apresentamos um teorema que explicita condições necessárias e suficientes para que um polinômio f(X) 2 Q[X] seja solúvel por radicais reais, juntamente com algumas aplicações do mesmo. Além disso, mostramos que em Q[X] sempre e possível encontrar o grupo de Galois de qualquer polinômio f(X) 2 Q[X]. / In this text we present a Theorem which gives necessary and suficient conditions for a polynomial f(X) with rational coe cients to be soluble by real radicals, as well as some applications of this result. We also show that it is always possible to explicit the Galois group of any polynomial f(X) 2 Q[X].

A Teoria de Códigos lida com um problema crítico do processo de comunicação: o controle eficiente do ruído em um canal de comunicação. Este trabalho tem por objetivo descrever algumas relações entre as necessidades da Teoria de Códigos e sua a modelagem matemática, utilizando-se, para isso, conceitos de álgebra e geometria sobre corpos finitos. Apresentaremos motivações para diferentes códigos, dando Ênfase a aspectos geométricoprojetivos do código Hamming e conceitos geométrico-algébricos subjacentes aos de Reed-Solomon e Goppa. / The Coding Theory deals with a critical communication problem: the eficient noise control. This work aims to describe some relationships between the needs of the Coding Theory and its Mathematical Models throught concepts of algebra and geometry over finite fields. We present some motivation for different codes, searching for projective geometric aspects of Hamming codes and algebraic geometric aspects of Reed-Solomon and Goppa codes.

Submitted by Estagiário SPT BMHS (spt@fgv.br) on 2011-11-08T10:08:46Z No. of bitstreams: 1 000091045.pdf: 9326873 bytes, checksum: 74d077bdafddf4e4499eb0eee8790891 (MD5) / Approved for entry into archive by Estagiário SPT BMHS (spt@fgv.br) on 2011-11-08T10:09:05Z (GMT) No. of bitstreams: 1 000091045.pdf: 9326873 bytes, checksum: 74d077bdafddf4e4499eb0eee8790891 (MD5) / Approved for entry into archive by Estagiário SPT BMHS (spt@fgv.br) on 2011-11-08T10:09:31Z (GMT) No. of bitstreams: 1 000091045.pdf: 9326873 bytes, checksum: 74d077bdafddf4e4499eb0eee8790891 (MD5) / Made available in DSpace on 2011-11-08T10:09:45Z (GMT). No. of bitstreams: 1 000091045.pdf: 9326873 bytes, checksum: 74d077bdafddf4e4499eb0eee8790891 (MD5) Previous issue date: 1999 / This paper aims at bringing a new prospect to the administrative knowledge, by pointing out the parcial and instrumental nature developed by organizational theories. Aiming at introducing the understanding about values in the scope of administration, one attempts to do that through the individuaIs' perspective, emphasizing their points of view. In this essay, administration is conceived as a non-neuter social science that has reproduced the values of the system in the organizational environment. In so far as theoretical administrative framework was developed, organizational theories were becoming increasingly complex, subjecting individuaIs to productive demands. On that perspective, adminstration was departing as far its main reason of existence, man, as significative issues ofthis millenium ending. Indeed, administration would have became tecnique, conducting its efforts to satisfy organizational needs, considering man a mere productive agent. This study uses the CriticaI Theory, a proposal of comprehension of society, by carring forward its statements to the organizational scenary, to bring home and to show up the values professed by administrative theories and the characterization of man that each one has developed. Carl Gustav Jung's teachings and his definition corcerning personal and colective unconscious are used to explane why administration has not taken into account another values, that not those that has became hegemonic by the system action, in conscious universe. Next, one attended to set and to associate to the ideas beforehand developed concerning values and organizational theories, the uni verse in which the fieldwork was gotten over, the Brazilian Armed Forces. Eventually, the fieldwork served as a reinforcement for the ideas that beforehand were presented: that organizational theories have privileged another values, that not those of individuaIs, that there is another way to understand reality, more substantive and that, although administration had exert, at least on speech, for answaring individual's basic needs, in organizational context, in fact, has not been successful. The new prospect that this paper aims at presenting refers to the understanding that there are another values, that not those that have been privileged by organizations, that must be taken into account by administrative knowledge. One seeks both to alert administrative theoretical body as regards the social rule which commits administration and to suggest that administration departs instrumentality and comes up substantivity, that is a world vision always possible and so many times disregarded by administration and other self-called social sciences. / o presente estudo procura trazer ao saber administrativo uma nova perspectiva, ao evidenciar a natureza parcial e instrumental das teorias organizacionais até então desenvolvidas. Ao buscar introduzir a percepção dos valores no estudo da administração, procura-se fazê-lo sob a ótica dos indivíduos, enfatizando-se o seu ponto de vista. Neste ensaio, a administração é concebida como ciência social não neutra, que tem reproduzido, no ambiente organizacional, os valores do sistema. Na medida em que os diversos arcabouços teóricos se desenvolveram, variadas e cada vez mais complexas foram as formas por intermédio das quais as teorias organizacionais procuraram submeter os indivíduos às necessidades produtivas. Teria a administração se distanciado, tanto de sua razão de ser, o indivíduo, como das grandes discussões desse final de milênio. Ter-se-ia tornado técnica, direcionando-se para o atendimento das demandas organizacionais, entendendo o homem como mero agente produtivo. Para a compreensão dessa feição das teorias organizacionais, o presente estudo lança mão da Teoria Crítica, que é uma proposta de visão do meio social, transpondo seus pressupostos para o domínio organizacional, no intuito de evidenciar os valores das diversas teorias e a caracterização do homem que cada uma delas promoveu. Na busca do entendimento das dificuldades existentes para que outros valores sejam percebidos pela administração, já que no universo consciente os valores do sistema tornaram-se hegemônicos, recorre-se aos ensinamentos de Carl Gustav Jung e suas definições de inconsciente pessoal e coletivo. Em seguida, tratou-se de contextualizar e associar às idéias previamente desenvolvidas sobre valores e teorias organizacionais o universo no qual desenvolveuse a pesquisa de campo, as Forças Armadas Brasileiras. Por fim, a pesquisa de campo desenvolvida constituiu reforço do que, até então, tinha-se procurado deixar evidente: que as teorias organizacionais têm privilegiado outros valores, que não os do indivíduo, que existe outra forma de se ver a realidade, mais substantiva e que, embora a administração tenha-se esforçado, pelo menos ao nível do discurso, para atender às demandas básicas do indivíduo no contexto organizacional, não obteve êxito. A nova perspectiva de que trata o presente estudo refere-se ao entendimento de que existem outros valores, que não os organizacionais, que precisam ser percebidos pelo saber administrativo. Procura-se alertar o corpo teórico quanto ao papel social que incumbe à administração e propõe-se que ela se afaste da instrumentalidade e se aproxime da substantividade, visão de mundo sempre possível e tantas vezes negligenciada por ela e por outras ciências auto-denominadas sociais.