To see the other types of publications on this topic, follow the link: Lemmas.
Dissertations / Theses on the topic 'Lemmas'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Lemmas.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
JACHELLI, KEILLA LOPES CASTILHO. "SPERNER S LEMMAS AND APPLICATIONS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2017. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=33127@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>PROGRAMA DE MESTRADO PROFISSIONAL EM MATEMÁTICA EM REDE NACIONAL<br>Esse trabalho visa demonstrar os lemas de Sperner e aplicá-los nasdemonstrações do teorema de Monsky em Q2 e do teorema do ponto fixo deBrouwer em R2. Além disso, relatamos como esses lemas foram abordados
com alunos da educação básica tendo como ferramenta educacional jogos de tabuleiro.<br>This work aims to prove the Sperner s Lemmas and to apply them in proving the Monsky s Theorem in Q2 and the Brouwer fixed point Theorem in R2. Moreover, we report how these lemmas were addressed with students
in basic education using board games as educational tools.
2
Pfeiffer, Markus Johannes. "Adventures in applying iteration lemmas." Thesis, University of St Andrews, 2013. http://hdl.handle.net/10023/3671.
Full textAbstract:
The word problem of a finitely generated group is commonly defined to be a formal language over a finite generating set. The class of finite groups has been characterised as the class of finitely generated groups that have word problem decidable by a finite state automaton. We give a natural generalisation of the notion of word problem from finitely generated groups to finitely generated semigroups by considering relations of strings. We characterise the class of finite semigroups by the class of finitely generated semigroups whose word problem is decidable by finite state automata. We then examine the class of semigroups with word problem decidable by asynchronous two tape finite state automata. Algebraic properties of semigroups in this class are considered, towards an algebraic characterisation. We take the next natural step to further extend the classes of semigroups under consideration to semigroups that have word problem decidable by a finite collection of asynchronous automata working independently. A central tool used in the derivation of structural results are so-called iteration lemmas. We define a hierarchy of the considered classes of semigroups and connect our original results with previous research.
3
Johansson, Moa. "Automated discovery of inductive lemmas." Thesis, University of Edinburgh, 2009. http://hdl.handle.net/1842/9807.
Full textAbstract:
The discovery of unknown lemmas, case-splits and other so called eureka steps are challenging problems for automated theorem proving and have generally been assumed to require user intervention. This thesis is mainly concerned with the automated discovery of inductive lemmas. We have explored two approaches based on failure recovery and theory formation, with the aim of improving automation of firstand higher-order inductive proofs in the IsaPlanner system. We have implemented a lemma speculation critic which attempts to find a missing lemma using information from a failed proof-attempt. However, we found few proofs for which this critic was applicable and successful. We have also developed a program for inductive theory formation, which we call IsaCoSy. IsaCoSy was evaluated on different inductive theories about natural numbers, lists and binary trees, and found to successfully produce many relevant theorems and lemmas. Using a background theory produced by IsaCoSy, it was possible for IsaPlanner to automatically prove more new theorems than with lemma speculation. In addition to the lemma discovery techniques, we also implemented an automated technique for case-analysis. This allows IsaPlanner to deal with proofs involving conditionals, expressed as if- or case-statements.
4
Lovász, László Miklós. "Regularity and removal lemmas and their applications." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/112899.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2017.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 123-127).<br>In this thesis, we analyze the regularity method pioneered by Szemerédi, and also discuss one of its prevalent applications, the removal lemma. First, we prove a new lower bound on the number of parts required in a version of Szemerédi's regularity lemma, determining the order of the tower height in that version up to a constant factor. This addresses a question of Gowers. Next, we turn to algorithms. We give a fast algorithmic Frieze-Kannan (weak) regularity lemma that improves on previous running times. We use this to give a substantially faster deterministic approximation algorithm for counting subgraphs. Previously, only an exponential dependence of the running time on the error parameter was known; we improve it to a polynomial dependence. We also revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for some co-NP-complete problems. We show how to use the Frieze-Kannan regularity lemma to approximate the regularity of a pair of vertex sets. We also show how to quickly find, for each [epsilon]' > [epsilon], an [epsilon]'-regular partition with k parts if there exists an [epsilon]-regular partition with k parts. After studying algorithms, we turn to the arithmetic setting. Green proved an arithmetic regularity lemma, and used it to prove an arithmetic removal lemma. The bounds obtained, however, were tower-type, and Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. The previous best known bound was tower-type with a logarithmic tower height. We solve Green's problem, proving an essentially tight bound for Green's arithmetic triangle removal lemma in Fn/p. Finally, we give a new proof of a regularity lemma for permutations, improving the previous tower-type bound on the number of parts to an exponential bound.<br>by László Miklós Lovász.<br>Ph. D.
5
Michael, Ifeanyi Friday. "On a unified categorical setting for homological diagram lemmas." Thesis, Stellenbosch : Stellenbosch University, 2011. http://hdl.handle.net/10019.1/18085.
Full textAbstract:
Thesis (MSc)--Stellenbosch University, 2011.<br>ENGLISH ABSTRACT: Some of the diagram lemmas of Homological Algebra, classically known for
abelian categories, are not characteristic of the abelian context; this naturally
leads to investigations of those non-abelian categories in which these diagram
lemmas may hold. In this Thesis we attempt to bring together two different
directions of such investigations; in particular, we unify the five lemma from
the context of homological categories due to F. Borceux and D. Bourn, and
the five lemma from the context of modular semi-exact categories in the sense
of M. Grandis.<br>AFRIKAANSE OPSOMMING: Verskeie diagram lemmata van Homologiese Algebra is aanvanklik ontwikkel
in die konteks van abelse kategorieë, maar geld meer algemeen as dit behoorlik
geformuleer word. Dit lei op ’n natuurlike wyse na ’n ondersoek van ander kategorieë
waar hierdie lemmas ook geld. In hierdie tesis bring ons twee moontlike
rigtings van ondersoek saam. Dit maak dit vir ons moontlik om die vyf-lemma
in die konteks van homologiese kategoieë, deur F. Borceux en D. Bourn, en vyflemma
in die konteks van semi-eksakte kategorieë, in die sin van M. Grandis,
te verenig.
6
Nunes, Alexmay Soares. "As permutaÃÃes caÃticas, o problema de Lucas e a teoria dos permanentes." Universidade Federal do CearÃ, 2015. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=15598.
Full textAbstract:
In this work we cover some counting techniques used to solve some classic problems in Combinatorics. We also show a link between the so called ârencontre problemâ, the âmÃnage problemâ and the permanent of a square matrix.<br>Neste trabalho abordamos algumas tÃcnicas de contagem utilizadas para solucionar alguns problemas clÃssicos da AnÃlise CombinatÃria. Mostramos tambÃm uma relaÃÃo entre o problema das cartas mal endereÃadas, o problema de Lucas e os permanentes de uma matriz quadrada.
7
Edmundo, Mario Jorge. "O-minimal expansions of groups." Thesis, University of Oxford, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.312447.
Full text
8
Aimino, Romain. "Vitesse de mélange et théorèmes limites pour les systèmes dynamiques aléatoires et non-autonomes." Thesis, Toulon, 2014. http://www.theses.fr/2014TOUL0005/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux propriétés statistiques des systèmes dynamiques aléatoires et non-autonomes. Dans le premier chapitre, consacré aux systèmes aléatoires, nous établissons un cadre fonctionnel abstrait, couvrant une large classe de systèmes dilatants en dimension 1 et supérieure, permettant de démontrer de nombreux théorèmes limites annealed. Nous donnons aussi une condition nécessaire et suffisante pour que la version quenched du théorème de la limite centrale soit valide en dimension 1. Dans le chapitre deux, après avoir introduit la notion de système non-autonome, nous étudions un système composé d'applications en dimension 1 ayant un point fixe neutre commun, et nous montrons que celui-ci admet une vitesse de perte de mémoire polynomiale. Le chapitre trois est consacré aux inégalités de concentration. Nous établissons de telles inégalités pour des systèmes dynamiques aléatoires et non-autonomes, et nous étudions diverses applications. Dans le chapitre quatre, nous nous intéressons aux lemmes dynamiques de Borel-Cantelli pour l'induction de Rauzy-Veech-Zorich, et présentons quelques résultats liés aux statistiques de récurrence pour cette application<br>The first chapter, devoted to random systems, we establish an abstract functional framework, including a large class of expanding systems in dimension 1 and higher, under which we can prove annealed limit theorems. We also give a necessary and sufficient condition for the quenched central limit theorem to hold in dimension 1. In chapter 2, after an introduction to the notion of non-autonomous system, we study an example consisting of a family of maps of the unit interval with a common neutral fixed point, and we show that this system admits a polynomial loss of memory. The chapter 3 is devoted to concentration inequalities. We establish such inequalities for random and non-autonomous dynamical systems in dimension 1, and we study some of their applications. In chapter 4, we study dynamical Borel-Cantelli lemmas for the Rauzy-Veech-Zorich induction, and we present some results concerning statistics of recurrence for this map
9
Cobra, Thiago Taglialatela [UNESP]. "Sobre coincidências e pontos fixos de aplicações." Universidade Estadual Paulista (UNESP), 2010. http://hdl.handle.net/11449/94372.
Full textAbstract:
Made available in DSpace on 2014-06-11T19:27:10Z (GMT). No. of bitstreams: 0
Previous issue date: 2010-12-09Bitstream added on 2014-06-13T20:47:43Z : No. of bitstreams: 1
cobra_tt_me_rcla.pdf: 485593 bytes, checksum: 107d36859b5a9c932411b3a54094c4ac (MD5)<br>O principal objetivo deste trabalho é apresentar conceitos básicos sobre coincidências e pontos fixos de aplicações contínuas usando como ferramentas os Lemas Combinatórios de Sperner e grau de aplicações. Apresentamos também um cálculo do número de Lefschetz de f; g : T2 ¡! T3, onde Th denota uma superfície de genus h, através da fórmula dada por Gonçalves e Oliveira em [3]<br>The main goal of this work is present basic concepts on coincidences and fixed points of continuous maps with Sperner’s Combinatorial Lemmas, and degree maps approaches. We also present a calculation of the Lefschetz number of f; g : T2 ¡! T3, where Th denotes surface of genus h, by using the formula given by Gonçalves and Oliveira in [3]
10
Cobra, Thiago Taglialatela. "Sobre coincidências e pontos fixos de aplicações /." Rio Claro : [s.n.], 2010. http://hdl.handle.net/11449/94372.
Full textAbstract:
Orientador: Alice Kimie Miwa Libardi<br>Banca: Edson de Oliveira<br>Banca: Thiago de Melo<br>Resumo: O principal objetivo deste trabalho é apresentar conceitos básicos sobre coincidências e pontos fixos de aplicações contínuas usando como ferramentas os Lemas Combinatórios de Sperner e grau de aplicações. Apresentamos também um cálculo do número de Lefschetz de f; g : T2 ¡! T3, onde Th denota uma superfície de genus h, através da fórmula dada por Gonçalves e Oliveira em [3]<br>Abstract: The main goal of this work is present basic concepts on coincidences and fixed points of continuous maps with Sperner's Combinatorial Lemmas, and degree maps approaches. We also present a calculation of the Lefschetz number of f; g : T2 ¡! T3, where Th denotes surface of genus h, by using the formula given by Gonçalves and Oliveira in [3]<br>Mestre
11
Schacht, Mathias. "Regular partitions of hypergraphs and property testing." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2010. http://dx.doi.org/10.18452/13975.
Full textAbstract:
Die Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemerédi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphen mit derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurden Regularitätslemmata für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen und dünne Graphen verallgemeinert. Ziel der vorliegenden Arbeit ist die Weiterentwicklung der Regularitätsmethode und deren Anwendung auf Probleme der theoretischen Informatik. Im Besonderen wird gezeigt, dass vererbbare (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche solche Eigenschaften haben und solchen die „weit“ davon entfernt sind, unterscheidet.<br>About 30 years ago Szemerédi developed the regularity method for graphs, which was a key ingredient in the proof of his famous density result concerning the upper density of subsets of the integers which contain no arithmetic progression of fixed length. Roughly speaking, the regularity lemma asserts, that the vertex set of every graph can be partitioned into a constant number of classes such that almost all of the induced bipartite graphs are quasi-random, i.e., they mimic the behavior of random bipartite graphs of the same density. The regularity lemma had have many applications mainly in extremal graph theory, but also in theoretical computer science and additive number theory, and it is considered one of the central tools in modern graph theory. A few years ago the regularity method was extended to other discrete structures. In particular extensions for uniform hypergraphs and sparse graphs were obtained. The main goal of this thesis is the further development of the regularity method and its application to problems in theoretical computer science. In particular, we will show that hereditary, decidable properties of hypergraphs, that are properties closed under isomorphism and vertex removal, are testable. I.e., there exists a randomised algorithm with constant running time, which distinguishes between Hypergraphs displaying the property and those which are “far” from it.
12
Grunert, Sandro. "Itô’s Lemma." Universitätsbibliothek Chemnitz, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200900979.
Full textAbstract:
Itô’s Lemma
Ausarbeitung im Rahmen des Seminars "Finanzmathematik", SS 2009
Die Arbeiten des japanischen Mathematikers Kiyosi Itô aus den 1940er Jahren bilden heute die Grundlage der Theorie
stochastischer Integration und stochastischer Differentialgleichungen. Die Ausarbeitung beschäftigt sich mit Itô's
Kalkül, in dem zunächst das Itô-Integral bezüglich diverser Integratoren bereitgestellt wird, um sich anschließend
mit Itô's Lemma bzw. der Itô-Formel als grundlegendes Hilfsmittel stochastischer Integration zu widmen. Am Ende wird
ein kurzer Ausblick auf das Black-Scholes-Modell für zeitstetige Finanzmärkte vollzogen. Grundlage für die Ausarbeitung
ist das Buch "Risk-Neutral Valuation" von Nicholas H. Bingham und Rüdiger Kiesel.
13
Fredriksson, Henrik. "Wiener's lemma." Thesis, Linnéuniversitetet, Institutionen för matematik (MA), 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-27270.
Full textAbstract:
In this thesis we study Wiener’s lemma. The classical version of the lemma, whose realm is a Banach algebra, asserts that the pointwise inverse of a nonzero function with absolutely convergent Fourier expansion, also possesses an absolutely convergent Fourier expansion. The main purpose of this thesis is to investigate the validity inalgebras endowed with a quasi-norm or a p-norm.As a warmup, we prove the classical version of Wiener’s lemma using elemen-tary analysis. Furthermore, we establish results in Banach algebras concerning spectral theory, maximal ideals and multiplicative linear functionals and present a proof Wiener’s lemma using Banach algebra techniques. Let ν be a submultiplicative weight function satisfying the Gelfand-Raikov-Shilov condition. We show that if a nonzero function f has a ν-weighted absolutely convergent Fourier series in a p-normed algebra A. Then 1/f also has a ν-weightedabsolutely convergent Fourier series in A.
14
Person, Yury. "Quasi-random hypergraphs and extremal problems for hypergraphs." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2010. http://dx.doi.org/10.18452/16238.
Full textAbstract:
In dieser Arbeit wird zuerst das Theorem von Chung, Graham und Wilson über quasi-zufällige Graphen zur sogenannten schwachen Quasi-Zufälligkeit für k-uniforme Hypergraphen verallgemeinert und somit eine Reihe äquivalenter Eigenschaften bestimmt. Basierend auf diesen Resultaten werden nichtbipartite Graphen gefunden, welche die Quasi-Zufälligkeit für Graphen ``forcieren''''. Zuvor waren nur bipartite Graphen mit dieser Eigenschaft bekannt. Desweiteren ist ein konzeptionell einfacher Algorithmus zum Verifizieren nicht erfüllbarer zufälliger k-SAT Formeln angegeben. Dann richtet sich der Fokus auf Anwendungen verschiedener Regularitätslemmata für Hypergraphen. Zuerst wird die Menge aller bezeichneten 3-uniformen Hypergraphen auf n Knoten, die keine Kopie des Hypergraphen der Fano Ebene enthalten, studiert. Es wird gezeigt, dass fast jedes Element aus dieser Menge ein bipartiter Hypergraph ist. Dies führt zu einem Algorithmus, der in polynomiell erwarteter Zeit einen zufälligen Fano-freien (und somit einen zufälligen bipartiten 3-uniformen) Hypergraphen richtig färbt. Schließlich wird die folgende extremale Funktion studiert. Es sind r Farben gegeben sowie ein k-uniformer Hypergraph F. Auf wie viele verschiedene Arten kann man die Kanten eines k-uniformen Hypergraphen H färben, so dass keine monochromatische Kopie von F entsteht? Welche Hypergraphen H maximieren die Anzahl erlaubter Kantenfärbungen? Hier wird ein strukturelles Resultat für eine natürliche Klasse von Hypergraphen bewiesen. Es wird für viele Hypergraphen F, deren extremaler Hypergraph bekannt ist, gezeigt, dass im Falle von zwei oder drei Farben die extremalen Hypergraphen die oben beschriebene Funktion maximieren, während für vier oder mehr Farben andere Hypergraphen mehr Kantenfärbungen zulassen.<br>This thesis presents first one possible generalization of the result of Chung, Graham and Wilson to k-uniform hypergraphs, and studies the so-called weak quasi-randomness. As applications we obtain a simple strong refutation algorithm for random sparse k-SAT formulas and we identify first non-bipartite forcing pairs for quasi-random graphs. Our focus then shifts from the study of quasi-random objects to applications of different versions of the hypergraph regularity lemmas; all these versions assert decompositions of hypergraphs into constantly many quasi-random parts, where the meaning of ``quasi-random'''' takes different contexts in different situations. We study the family of hypergraphs not containing the hypergraph of the Fano plane as a subhypergraph, and show that almost all members of this family are bipartite. As a consequence an algorithm for coloring bipartite 3-uniform hypergraphs with average polynomial running time is given. Then the following combinatorial extremal problem is considered. Suppose one is given r colors and a fixed hypergraph F. The question is: In at most how many ways can one color the hyperedges of a hypergraph H on n vertices such that no monochromatic copy of F is created? What are the extremal hypergraphs for this function? Here a structural result for a natural family of hypergraphs F is proven. For some special classes of hypergraphs we show that their extremal hypergraphs (for large n) maximize the number of edge colorings for 2 and 3 colors, while for at least 4 colors other hypergraphs are optimal.
15
Shlapunov, A., and Nikolai Tarkhanov. "Formal Poincaré lemma." Universität Potsdam, 2007. http://opus.kobv.de/ubp/volltexte/2009/3023/.
Full textAbstract:
We show how the multiple application of the formal Cauchy-Kovalevskaya theorem leads to the main result of the formal theory of overdetermined systems of partial differential equations. Namely, any sufficiently regular system Au = f with smooth coefficients on an open set U ⊂ Rn admits a solution in smooth sections of a bundle of formal power series, provided that f satisfies a compatibility condition in U.
16
Zorin, Evgeniy. "Lemmes de zéros et relations fonctionnelles." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2009. http://tel.archives-ouvertes.fr/tel-00558073.
Full textAbstract:
La thèse est consacrée aux estimations de multiplicité. Ce type de résultats est utilisé en théorie de la transcendance. A partir des travaux de A. B. Shidlovskii, W.D.Brownawell et D.W.Masser il sont régulièrement utilisés dans les preuves de transcendance et surtout d'indépendance algébrique. Par exemple, la démonstration du lemme de multiplicité est un élément très important de la preuve par Yu. Nesterenko du résultat sur l'indépendance algébrique des valeurs des fonctions de Ramanujan. Un autre résultat de ce type est une preuve par K.Nishioka d'une conjecture de K.Mahler. Ce lemme de multiplicité a permis de démontrer beaucoup de résultats concernant la transcendance des séries liées aux suites récurrentes et des suites engendrées par des automates finis. Le but de ce mémoire est l'étude approfondie, dans un cadre général, des lemmes de multiplicité conduisant à des améliorations de résultats d'indépendance algébrique connus. Le théorème principal de ce travail réduit la preuve des estimations de multiplicité à l'étude des idéaux stables sous une transformation algébrique. En particulier, ce théorème permet d'améliorer un peu le résultat de Yu.Nesterenko concernant les solutions de système d'équations différentielles. Dans le même temps ce théorème donne, sous une condition concernant des variétés stables, l'estimation avec l'exposant le meilleur possible dans le cas de solutions d'équations fonctionnelles. Ce dernier résultat conduit à l'étude des variétés irréductibles stables sous une transformation rationnelle, ceci semble d'être un sujet intéressant en soi.
17
Zorin, Evgeniy. "Lemmes de zéros et relations fonctionnelles." Paris 6, 2010. http://www.theses.fr/2010PA066350.
Full textAbstract:
La thèse est consacrée aux estimations de multiplicité. Ce type de résultats est utilisé en théorie de la transcendance. A partir des travaux de A. B. Shidlovskii, W. D. Brownawell et D. W. Masser il sont régulièrement utilisés dans les preuves de transcendance et surtout d'indépendance algébrique. Par exemple, la démonstration du lemme de multiplicité est un élément très important de la preuve par Yu. Nesterenko du résultat sur l'indépendance algébrique des valeurs des fonctions de Ramanujan. Un autre résultat de ce type est une preuve par K. Nishioka d'une conjecture de K. Mahler. Ce lemme de multiplicité a permis de démontrer beaucoup de résultats concernant la transcendance des séries liées aux suites récurrentes et des suites engendrées par des automates finis. Le but de ce mémoire est l'étude approfondie, dans un cadre général, des lemmes de multiplicité conduisant à des améliorations de résultats d'indépendance algébrique connus. Le théorème principal de ce travail réduit la preuve des estimations de multiplicité à l'étude des idéaux stables sous une transformation algébrique. En particulier, ce théorème permet d'améliorer un peu le résultat de Yu. Nesterenko concernant les solutions de système d'équations différentielles. Dans le même temps ce théorème donne, sous une condition concernant des variétés stables, l'estimation avec l'exposant le meilleur possible dans le cas de solutions d'équations fonctionnelles. Ce dernier résultat conduit à l'étude des variétés irréductibles stables sous une transformation rationnelle, ceci semble d'être un sujet intéressant en soi.
18
Hyde, Andrea. "Intersective polynomials and Hensel's Lemma." Thesis, University of British Columbia, 2014. http://hdl.handle.net/2429/46574.
Full textAbstract:
An intersective polynomial is a polynomial with integer coefficients that has no rational roots, but has a root modulo every integer greater than 1. These polynomials have been difficult to find using traditional methods. In this thesis, we employ elementary methods, namely Hensel’s Lemma and the Chinese remainder theorem, to allow us to create three new infinite families of intersective polynomials.
In order to create a candidate intersective polynomial, we employ methods from Galois theory. We multiply together carefully chosen polynomials that define subfields of a splitting field to create our candidate. We chose the subfields by first finding the n-cover, a collection of n proper subgroups, of the Galois group and identifying the corresponding subfields. We multiply the minimal polynomials of the subfields of the chosen splitting fields together to create the candidate intersective polynomial.
From our method of creating candidates we can see that intersective polynomials have at least two irreducible factors. In order to prove that these polynomials have a root modulo every integer greater than 1, we examine each factor modulo certain prime numbers and determine which sets of primes admit solutions for each factor. We then use Hensel’s Lemma to lift those solutions to infinitely high powers of the particular primes. Finally, we combine the solutions modulo prime powers by using the Chinese remainder theorem to show that the polynomial has solutions modulo every integer greater than 1.
Through the method outlined above, we have created three infinite families of intersective polynomials: (x³ − n)(x² + 3) when the prime factors of n are of the form 3k + 1 and n is congruent to 1 mod 9; (x² − a)(x² − b)(x² − a₁b₁) when at least one of a, b, a₁b₁ is congruent to 1 modulo 8 and one of the Legendre Symbols (a/p), (b/p), (a₁b₁/p) has the value +1; and (x^q −n)(x^(q-¹) +x^q-²+...+ x + 1) when the prime factors of n are kq + 1 and n is congruent to 1 modulo q² for an odd prime q.
In the last chapter, we treat some special cases of intersective polynomials which will be considered in detail in future work.
19
Hedman, Jonas. "2-Categories and Yoneda lemma." Thesis, Uppsala universitet, Algebra och geometri, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-312810.
Full text
20
Strasser, Helmut. "On a Lemma of Schachermayr." SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 1997. http://epub.wu.ac.at/1794/1/document.pdf.
Full textAbstract:
In this paper we prove a topological lemma on real valued random variables which implies the basic ingredients for the proof of the Fundamental Theorem of Asset Pricing in the two period case. In particular, previous results of Stricker and of Schachermayer are special cases of our result. Our proof is considerably shorter and more transparent than previous proofs of related special cases.<br>Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
21
Seppälä, L. (Louna). "Siegel’s lemma and Minkowski’s theorems." Master's thesis, University of Oulu, 2015. http://urn.fi/URN:NBN:fi:oulu-201512012187.
Full textAbstract:
The subject of the work is geometry of numbers, which uses geometric arguments in n-dimensional euclidean space to prove arithmetic results. Siegel’s and Minkowski’s existential theorems are studied: When dealing with a group of linear equations where the number of unknowns exceeds the number of equations, Siegel’s lemma confirms the existence of a non-trivial solution whose size is bounded by a certain positive function depending on the coefficients of the linear forms and the number of unknowns. Minkowski’s theorems in turn concern convex bodies and lattices in n-dimensional euclidean space: when a convex body satisfies a specific condition with respect to the lattice, it is bound to intersect the lattice in a non-zero point. A selection of Diophantine inequalities is presented in order to illustrate the remarkable usefulness of this fact. Finally, Bombieri-Vaaler version of Siegel’s lemma is applied with the aim of improving (in rational case) a result of Ernvall-Hytönen, Leppälä and Matala-aho on Hermite-Padé type approximations (An explicit Baker type lower bound for linear forms, Lemma 4.1). The main sources, in addition to the above-mentioned article, are A geometric face of Diophantine analysis by Matala-aho (lecture notes), Lectures on Transcendental numbers by Mahler (Springer-Verlag, 1976) and Diophantine approximation by Evertse (lecture notes)<br>Työn aiheena on lukujen geometria, jossa todistetaan aritmeettisia tuloksia käyttäen apuna geometriaa n-ulotteisessa euklidisessa avaruudessa. Aluksi perehdytään Siegelin ja Minkowskin olemassaolotuloksiin: Kun lineaarisessa yhtälöryhmässä tuntemattomien määrä ylittää yhtälöiden määrän, Siegelin lemma varmistaa nollasta poikkeavan ratkaisun olemassaolon, jonka kokoa rajoittaa tietty yhtälöryhmän kertoimista ja tuntemattomien määrästä riippuva positiivinen funktio. Minkowskin lauseet vuorostaan liittyvät konvekseihin kappaleisiin n-ulotteisessa euklidisessa avaruudessa: kun konveksi kappale toteuttaa tietyn ehdon hilan suhteen, sen sisältä löytyy aina nollasta poikkeava hilapiste. Tämän tuloksen merkittävyyttä havainnollistaa valikoima Diofantoksen epäyhtälöitä. Lopuksi sovelletaan Bombierin ja Vaalerin versiota Siegelin lemmasta tavoitteena parantaa (rationaalitapauksessa) Ernvall-Hytösen, Leppälän ja Matala-ahon tulosta liittyen Hermite-Padé-tyypin approksimaatioihin (An explicit Baker type lower bound for linear forms, Lemma 4.1). Päälähteinä on edellä mainitun artikkelin lisäksi käytetty Matala-ahon luentomonistetta A geometric face of Diophantine analysis, Mahlerin kirjaa Lectures on Transcendental numbers (Springer-Verlag, 1976) sekä Evertsen luentomonistetta Diophantine approximation
22
Jörder, Clemens [Verfasser], and Stefan [Akademischer Betreuer] Kebekus. "On the Poincaré Lemma for reflexive differential forms = Über das Poincaré-Lemma für reflexive Differentialformen." Freiburg : Universität, 2014. http://d-nb.info/1123479313/34.
Full text
23
Azhari, Abdelhak. "Methodes analytiques pour les lemmes de zeros." Paris 6, 1988. http://www.theses.fr/1988PA066033.
Full textAbstract:
L'etude analytique et effective des hypersurfaces algebriques, fondee sur les recents theoremes d'existence sur les fibres vectoriels holomorphes, aboutit a une extension aux situations multi-homogenes des minorations des plus petits degres de ces hypersurfaces (lemmes de multiplicites. Elle permet d'autre part, d'analyser et clarifier la principale conjecture de chudnovsky
24
Azhari, Abdelhak. "Méthodes analytiques pour les lemmes de zéros." Grenoble 2 : ANRT, 1988. http://catalogue.bnf.fr/ark:/12148/cb37611442v.
Full text
25
Cavalcanti, Gil R. "New aspects if the ddc-lemma." Thesis, University of Oxford, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.409710.
Full text
26
DINIZ, Diego Araújo. "Tópicos de Dinâmica Hiperbólica." Universidade Federal do Maranhão, 2017. http://tedebc.ufma.br:8080/jspui/handle/tede/1663.
Full textAbstract:
Submitted by Daniella Santos (daniella.santos@ufma.br) on 2017-06-22T12:57:55Z
No. of bitstreams: 1
Diego Araújo.pdf: 749439 bytes, checksum: e6b630a6b28df216e5e6fc70dbeead61 (MD5)<br>Made available in DSpace on 2017-06-22T12:57:55Z (GMT). No. of bitstreams: 1
Diego Araújo.pdf: 749439 bytes, checksum: e6b630a6b28df216e5e6fc70dbeead61 (MD5)
Previous issue date: 2017-05-02<br>The main goal of this work is to discuss some topics about hyperbolic dynamical systems. We collect results and definitions that are dispersed, or even in works of generalized context. Thus, we propose a tour that begins with the definition of orbit, passes through classical results like Hartman-Grobman Theorem and shadowing lemma, and ends with the Omega stability theorem.<br>O objetivo deste trabalho é dissertar sobre alguns tópicos dos sistemas dinâmicos hiberbólicos. Nós coletamos resultados e definicões que em sua maioria encontram-se dispersos, ou ainda, em obras de contexto generalizado. Assim, nos propomos a fazer uma caminhada que começa com a definicão de órbita, passa por resultados clássicos como o Teorema de Hartman-Grobman e o Lema de Sombreamento, e termina com o teorema da Omega estabilidade.
27
Vena, Cros Lluís. "The Removal Lemma: algebraic versions and applications." Doctoral thesis, Universitat Politècnica de Catalunya, 2012. http://hdl.handle.net/10803/132098.
Full textAbstract:
This thesis presents some contributions in additive combinatorics and arithmetic Ramsey theory. More specifically, it deals with the interaction between combinatorics, number theory and additive combinatorics. This area saw a great improvement with the Szemerédi Regularity Lemma and some of the results that followed. The Regularity Lemma and its consequences have become a widely used tool in graph theory, combinatorics and number theory. Furthermore, its language and point of view has deeply changed the face of additive number theory, a fact universally acknowledged by the Abel award given to Szemerédi in 2012. One of the main reasons for the prize has been Szemerédi's theorem, a result regarding the existence of arbitrarily long arithmetic progressions in dense sets of the integers, the proof of which uses the Regularity Lemma in a key step.
One of the earlier consequences of the Regularity Lemma was the Removal Lemma for graphs that was used by Ruzsa and Szemerédi to show Roth theorem, regarding the existence of 3-term arithmetic progressions in dense sets of the integers, in a combinatorial way. The Removal Lemma states that in any graph K with few copies of a subgraph, say a triangle, we can remove few edges from K so that the result contains no copy of the subgraph. This has become a key tool in the applications of the so-called Regularity Method, which has extensive literature in combinatorics, graph theory, number theory and computer science. In 2005 Green introduced a regularity lemma for Abelian groups as well as an algebraic removal lemma. The removal lemma for groups states that, for a given finite Abelian group G, if there are o(|G|^3) solution to x+y+z+t=0 with the variables taking values in S, a subset of G, then we can remove o(|G|) elements from S to make the set S solution-free.
The main contributions of this work corresponds to extensions of the removal lemma for groups to either more general contexts, like non-necessary Abelian finite groups, or to linear systems of equations for finite Abelian groups. The main goal is to give a comprehensive and more general framework for many results in additive number theory like Szemerédi Theorem.
In particular, we show that the removal lemma for groups by Green can be extended to non-necessary Abelian finite groups. Moreover, we prove a removal lemma for linear systems on finite fields: for every e>0 there exists a d>0 such that if A is a (k x m) linear system of equations with coefficients in a finite field F and the number of solutions to Ax=b, where each variable takes values from a subset Si in F is less than d times |F| raised to m-k, then by removing less than e|F| elements in each Si we can make the resulting sets solution-free, thus solving a conjecture by Green to that respect. Even more, if A is an integer linear system, G is a finite Abelian group, and the determinantal of A and |G| are coprime, then a similar statement holds. Let us mention that the last result allows us to characterize those linear systems where any set S with size proportional to G has a nontrivial solution in S, provided |G| is large enough. This extends the validity of Szmerédi's theorem to finite Abelian groups.
These extensions of the removal lemma have been used in arithmetic Ramsey theory to obtain counting results for the number of monochromatic solutions of linear systems. The main result from a work by Frankl, Graham and Rödl in '88 states that the number of monochromatic solutions of regular systems in integer intervals is in fact a positive proportion of the total number of solutions. We give analogous results for solutions in Abelian groups with bounded exponent, for which the main tool in the torsion-free case cannot be applied. Density versions of these counting results are also obtained, in this case with a full characterization.
28
Hellström, Lars. "The Diamond Lemma for Power Series Algebras." Doctoral thesis, Umeå University, Mathematics and Mathematical Statistics, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-92.
Full textAbstract:
<p>The main result in this thesis is the generalisation of Bergman's diamond lemma for ring theory to power series rings. This generalisation makes it possible to treat problems in which there arise infinite descending chains. Several results in the literature are shown to be special cases of this diamond lemma and examples are given of interesting problems which could not previously be treated. One of these examples provides a general construction of a normed skew field in which a custom commutation relation holds.</p><p>There is also a general result on the structure of totally ordered semigroups, demonstrating that all semigroups with an archimedean element has a (up to a scaling factor) unique order-preserving homomorphism to the real numbers. This helps analyse the concept of filtered structure. It is shown that whereas filtered structures can be used to induce pretty much any zero-dimensional linear topology, a real-valued norm suffices for the definition of those topologies that have a reasonable relation to the multiplication operation.</p><p>The thesis also contains elementary results on degree (as of polynomials) functions, norms on algebras (in particular ultranorms), (Birkhoff) orthogonality in modules, and construction of semigroup partial orders from ditto quasiorders.</p>
29
Ge, Wenfeng. "Gröbner Bases Theory and The Diamond Lemma." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/2951.
Full textAbstract:
Commutative Gröbner bases theory is well known and widely used. In this thesis, we will discuss thoroughly its generalization to noncommutative polynomial ring <em>k</em><<em>X</em>> which is also an associative free algebra. We introduce some results on monomial orders due to John Lawrence and the author. We show that a noncommutative monomial order is a well order while a one-sided noncommutative monomial order may not be. Then we discuss the generalization of polynomial reductions, S-polynomials and the characterizations of noncommutative Gröbner bases. Some results due to Mora are also discussed, such as the generalized Buchberger's algorithm and the solvability of ideal membership problem for homogeneous ideals. At last, we introduce Newman's diamond lemma and Bergman's diamond lemma and show their relations with Gröbner bases theory.
30
Brits, Jeanetta Hendrina. "Outomatiese Setswana lemma-identifisering / Jeanetta Hendrina Brits." Thesis, North-West University, 2006. http://hdl.handle.net/10394/1160.
Full textAbstract:
Within the context of natural language processing, a lemmatiser is one of the
most important core technology modules that has to be developed for a particular
language. A lemmatiser reduces words in a corpus to the corresponding lemmas
of the words in the lexicon.
A lemma is defined as the meaningful base form from which other more complex
forms (i.e. variants) are derived. Before a lemmatiser can be developed for a
specific language, the concept "lemma" as it applies to that specific language
should first be defined clearly. This study concludes that, in Setswana, only
stems (and not roots) can act independently as words; therefore, only stems
should be accepted as lemmas in the context of automatic lemmatisation for
Setswana.
Five of the seven parts of speech in Setswana could be viewed as closed
classes, which means that these classes are not extended by means of regular
morphological processes. The two other parts of speech (nouns and verbs) require
the implementation of alternation rules to determine the lemma. Such alternation
rules were formalised in this study, for the purpose of development of a
Setswana lemmatiser. The existing Setswana grammars were used as basis for
these rules. Therewith the precision of the formalisation of these existing grammars
to lemmatise Setswana words could be determined.
The software developed by Van Noord (2002), FSA 6, is one of the best-known
applications available for the development of finite state automata and transducers.
Regular expressions based on the formalised morphological rules were
used in FSA 6 to create finite state transducers. The code subsequently generated
by FSA 6 was implemented in the lemmatiser.
The metric that applies to the evaluation of the lemmatiser is precision. On a test
corpus of 1 000 words, the lemmatiser obtained 70,92%. In another evaluation
on 500 complex nouns and 500 complex verbs separately, the lemmatiser obtained
70,96% and 70,52% respectively. Expressed in numbers the precision on
500 complex and simplex nouns was 78,45% and on complex and simplex verbs
79,59%. The quantitative achievement only gives an indication of the relative
precision of the grammars. Nevertheless, it did offer analysed data with which
the grammars were evaluated qualitatively. The study concludes with an overview
of how these results might be improved in the future.<br>Thesis (M.A. (African Languages))--North-West University, Potchefstroom Campus, 2006.
31
Turgeon, Maxime. "A relative fundamental lemma for U (4)." Thesis, McGill University, 2014. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=121414.
Full textAbstract:
In (HLR86), Harder et al. presented a proof of the Tate conjecture, an important conjecture in the field of arithmetic geometry, for the non-CM part of the cohomology of Hilbert modular surfaces. In this thesis, we present a general strategy for a study of the Tate conjecture for some unitary Shimura varieties. As in the work cited above, we do this by studying the notion of distinction. Distinction on a unitary group is related to distinction on a general linear group through a comparison of relative trace formulas. In the latter setting, work of Jacquet and his collaborators has led to simple criteria in terms of base change and L-functions for the existence of distinguished representations of GL(N). The main result of this thesis is then a proof of a special case of a relative fundamental lemma, the first ingredient of the comparison, when the unitary group is of rank 4.<br>Dans leur article (HLR86), Harder et al. présente une preuve de la conjecture de Tate, une importante conjecture en géométrie arithmétique, pour la partie sans CM de la cohomologie des surfaces modulaires de Hilbert. Cette thèse propose une stratégie générale pour l'étude de la conjecture de Tate pour certaines variétés de Shimura unitaires. Comme dans le travail cité ci-haut, la méthode proposée passe par l'étude de la notion de distinction. La distinction sur un groupe unitaire est reliée à la distinction sur un groupe général linéaire par le biais d'une comparaisonde formules des traces relatives. Dans ce dernier contexte, le travail de Jacquet et ses collaborateurs donne des critères simples, en termes de changement de base et de fonctions L, pour l'existence de représentations distinguées sur GL(N). Le résultat principal de cette thèse est donc une preuve d'un cas spécial d'un lemme fondamental relatif, premier ingrédient d'une comparaison, lorsque le groupe unitaire est de rang 4.
32
Haeupler, Bernhard. "Deterministic algorithms for the Lovász Local Lemma." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/60165.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.<br>Includes bibliographical references (p. 34-36).<br>The Lovász Local Lemma [6] (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d < 2k/e other clauses then such the formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser [17]. Subsequently Moser and Tardos [18] gave a randomized algorithm to construct the structures guaranteed by the LLL in a very general algorithmic framework. We address the main problem left open by Moser and Tardos of derandomizing these algorithms efficiently. Specifically, for a k-CNF formula with m clauses and d < 2k/(l+)/e for some c E (0, 1), we give an algorithm that finds a satisfying assignment in time O(m2(1+1/E)). This improves upon the deterministic algorithms of Moser and of Moser- Tardos with running times mn (k2) and mD(k 1/c) which are superpolynomial for k = w(1) and upon other previous algorithms which work only for d </= 2k/ 16 /e. Our algorithm works efficiently for the asymmetric version of LLL under the algorithmic framework of Moser and Tardos [18] and is also parallelizable, i.e., has polylogarithmic running time using polynomially many processors.<br>by Bernhard Haeupler.<br>S.M.
33
Rosas, Rudy. "A lemma on limits of analytic sets." Pontificia Universidad Católica del Perú, 2014. http://repositorio.pucp.edu.pe/index/handle/123456789/95130.
Full text
34
Cogliati, Joshua Joseph. "Visualizing the pumping lemma for regular languages." Thesis, Montana State University, 2004. http://etd.lib.montana.edu/etd/2004/cogliati/CogliatiJ0805.pdf.
Full text
35
Peterson, Elisha. "Combinatorial Proofs of Generalizations of Sperner's Lemma." Scholarship @ Claremont, 2000. https://scholarship.claremont.edu/hmc_theses/124.
Full textAbstract:
In this thesis, we provide constructive proofs of serveral generalizations of Sperner's Lemma, a combinatorial result which is equivalent to the Brouwer Fixed Point Theorem. This lemma makes a statement about the number of a certain type of simplices in the triangulation of a simplex with a special labeling. We prove generalizations for polytopes with simplicial facets, for arbitrary 3-polytopes, and for polygons. We introduce a labeled graph which we call a nerve graph to prove these results. We also suggest a possible non-constructive proof for a polytopal generalization.
36
Sondjaja, Mutiara. "Sperner's Lemma Implies Kakutani's Fixed Point Theorem." Scholarship @ Claremont, 2008. https://scholarship.claremont.edu/hmc_theses/214.
Full textAbstract:
Kakutani’s fixed point theorem has many applications in economics and game theory. One of its most well known applications is in John Nash’s paper [8], where the theorem is used to prove the existence of an equilibrium strategy in n-person games. Sperner’s lemma, on the other hand, is a combinatorial result concerning the labelling of the vertices of simplices and their triangulations. It is known that Sperner’s lemma is equivalent to a result called Brouwer’s fixed point theorem, of which Kakutani’s theorem is a generalization. A natural question that arises is whether we can prove Kakutani’s fixed point theorem directly using Sperner’s lemma without going through Brouwer’s theorem. The objective of this thesis to understand Kakutani’s theorem, Sperner’s lemma, and how they are related. In particular, I explore ways in which Sperner’s lemma can be used to prove Kakutani’s theorem and related results.
37
Bond, Brittany M. "Networks or lemons?" Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/118007.
Full textAbstract:
Thesis: S.M. in Management Research, Massachusetts Institute of Technology, Sloan School of Management, 2018.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 22-24).<br>Past research has argued that hiring personnel use employment as a signal of worker quality. If firms tend to keep high ability workers, then those who are not employed will tend to be "lemons," labor market leftovers who are of uncertain quality. To the extent that employers rely on employment as a signal, then well-qualified, but out-of-work job seekers will be stigmatized simply by being out of work. "Networking" is commonly prescribed as a means for job seekers to overcome the negative signals of being out of work. But for networking to work, someone must be willing to provide a connection for the unemployed person. This begs two important questions: 1) will potential referrers also view unemployment as a negative signal? and, 2) does the willingness to help depend on the strength of the network tie? We design a survey vignette experiment to study how potential referrers react to the signal of unemployment, and how their decisions to refer job candidates depend on whether the potential referral is a friend vs. stranger. We find that referrers generally do react negatively to unemployed job seekers. However, despite the risk to their reputation, friends are more likely to refer the unemployed, and do so without distancing themselves from the unemployed candidate. This suggests that networking can indeed solve the lemons problem confronting unemployed job seekers.<br>by Brittany M. Bond.<br>S.M. in Management Research
38
Stagni, Henrique. "Teste de propriedades em torneios." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21072015-112930/.
Full textAbstract:
Teste de propriedades em grafos consiste no estudo de algoritmos aleatórios sublineares que determinam se um grafo $G$ de entrada com $n$ vértices satisfaz uma dada propriedade ou se é necessário adicionar ou remover mais do que $\\epsilon{n \\choose 2}$ arestas para fazer $G$ satisfazê-la, para algum parâmetro $\\epsilon$ de erro fixo. Uma propriedade de grafos $P$ é dita testável se, para todo $\\epsilon > 0$, existe um tal algoritmo para $P$ cujo tempo de execução é independente de $n$. Um dos resultados de maior importância nesta área, provado por Alon e Shapira, afirma que toda propriedade hereditária de grafos é testável. Neste trabalho, apresentamos resultados análogos para torneios --- grafos completos nos quais são dadas orientações para cada aresta.<br>Graph property testing is the study of randomized sublinear algorithms which decide if an input graph $G$ with $n$ vertices satisfies a given property or if it is necessary to add or remove more than $\\epsilon{n \\choose 2}$ edges to make $G$ satisfy it, for some fixed error parameter $\\epsilon$ . A graph property $P$ is called testable if, for every $\\epsilon > 0$, there is such an algorithm for $P$ whose run time is independent of $n$. One of the most important results in this area is due to Alon and Shapira, who showed that every hereditary graph property is testable. In this work, we show analogous results for tournaments --- complete graphs in which every edge is given an orientation.
39
Terenzi, Gloria. "Lemma di Schwarz e la sua interpretazione geometrica." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/13543/.
Full textAbstract:
Il tema centrale di questa tesi, suddivisa in tre capitoli, è il Lemma di Schwarz e la sua applicazione nella geometria iperbolica. Il lemma di Schwarz, che prende il nome da Hermann Amandus Shchwarz, descrive una proprietà delle funzioni olomorfe. Nel primo capitolo enuncio il Lemma di Schwarz e la sua versione infinitesimale. Descrivo le mappe conformi del dominio per poi applicare il lemma di Pick che è una forma particolare del lemma di Schwarz.Nel secondo capitolo introduco brevemente la geometria euclidea con i cinque postulati di Euclide, per poi passare a descrivere la geometria iperbolica. Introduco la definizione di forma fondamentale (o forma metrica) di una superficie. Nel terzo capitolo affronto la geometria iperbolica nel disco. Quindi data una forma metrica ho definito distanza iperbolica e lunghezza iperbolica per poi arrivare a dimostrare tramite una reinterpretazione del lemma di Schwarz l'invarianza delle mappe olomorfe.
40
Hägglund, Jonas. "Szémeredi's regularity lemma and its applications in combinatorics." Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-51333.
Full textAbstract:
Szemerédi’s regularity lemma is a deep result in graph theory with applications in many different areas of mathematics. The lemma says that any graph can be approximated by the union of a bounded num- ber of random-like bipartite graphs and this can be used to extract the underlying structure of the graph. Recently it has been shown that there exists polynomial time algorithms that can make this ap- proximation. This survey gives a proof of the regularity lemma, shows some applications and discusses some algorithmic aspects.
41
Van, Vleck Erik S. "Random and numerical aspects of the shadowing lemma." Thesis, Georgia Institute of Technology, 1991. http://hdl.handle.net/1853/29357.
Full text
42
Song, Fei. "Practical and theoretical applications of the Regularity Lemma." Digital WPI, 2013. https://digitalcommons.wpi.edu/etd-dissertations/144.
Full textAbstract:
The Regularity Lemma of Szemeredi is a fundamental tool in extremal graph theory with a wide range of applications in theoretical computer science. Partly as a recognition of his work on the Regularity Lemma, Endre Szemeredi has won the Abel Prize in 2012 for his outstanding achievement. In this thesis we present both practical and theoretical applications of the Regularity Lemma. The practical applications are concerning the important problem of data clustering, the theoretical applications are concerning the monochromatic vertex partition problem. In spite of its numerous applications to establish theoretical results, the Regularity Lemma has a drawback that it requires the graphs under consideration to be astronomically large, thus limiting its practical utility. As stated by Gowers, it has been ``well beyond the realms of any practical applications', the existing applications have been theoretical, mathematical. In the first part of the thesis, we propose to change this and we propose some modifications to the constructive versions of the Regularity Lemma. While this affects the generality of the result, it also makes it more useful for much smaller graphs. We call this result the practical regularity partitioning algorithm and the resulting clustering technique Regularity Clustering. This is the first integrated attempt in order to make the Regularity Lemma applicable in practice. We present results on applying regularity clustering on a number of benchmark data-sets and compare the results with k-means clustering and spectral clustering. Finally we demonstrate its application in Educational Data Mining to improve the student performance prediction. In the second part of the thesis, we study the monochromatic vertex partition problem. To begin we briefly review some related topics and several proof techniques that are central to our results, including the greedy and absorbing procedures. We also review some of the current best results before presenting ours, where the Regularity Lemma has played a critical role. Before concluding we discuss some future research directions that appear particularly promising based on our work.
43
Gomes, Bernardo Paschoarelli Veiga. "Sobre o closing lemma de classe C^r." Universidade de São Paulo, 2006. http://www.teses.usp.br/teses/disponiveis/55/55135/tde-02022007-133405/.
Full textAbstract:
Neste trabalho reunimos alguns resultados afirmativos relacionados ao closing lemma de classe C^r em variedades bidimensionais compactas.<br>In this work we present some partial results corcerning closing lemma for smooth flows on compact bidimensional manifolds.
44
Betto, Maria Fernanda Petri. "Dynamic markets for lemons." reponame:Repositório Institucional do FGV, 2017. http://hdl.handle.net/10438/18328.
Full textAbstract:
Submitted by Maria Fernanda Petri Betto (betto.maria@gmail.com) on 2017-06-12T12:51:35Z
No. of bitstreams: 1
v2 (2).pdf: 374191 bytes, checksum: e2354b420b3a4a3b8d297fd77a276555 (MD5)<br>Rejected by Suzinei Teles Garcia Garcia (suzinei.garcia@fgv.br), reason: Maria Fernanda,
Por favor, seguir as normas, letras, capa, contra-capa, folha de assinaturas, em caixa alta o agradecimento, abstract e resumo, descer mais seu nome.
Por gentileza, verifique um modelo de dissertação/tese dos colegas (Ex.:Mateus Dias, Ilaria, etc.)
Letras - somente Arial / Times New Roman
Att.
Suzi 3799-7876 on 2017-06-12T13:23:14Z (GMT)<br>Submitted by Maria Fernanda Petri Betto (betto.maria@gmail.com) on 2017-06-12T14:19:45Z
No. of bitstreams: 1
v3.pdf: 303914 bytes, checksum: bbaf7272fd9e4d7a65e64f402afe810c (MD5)<br>Approved for entry into archive by Suzinei Teles Garcia Garcia (suzinei.garcia@fgv.br) on 2017-06-12T14:41:49Z (GMT) No. of bitstreams: 1
v3.pdf: 303914 bytes, checksum: bbaf7272fd9e4d7a65e64f402afe810c (MD5)<br>Made available in DSpace on 2017-06-12T15:15:06Z (GMT). No. of bitstreams: 1
v3.pdf: 303914 bytes, checksum: bbaf7272fd9e4d7a65e64f402afe810c (MD5)
Previous issue date: 2017-05-12<br>This paper investigates the role of signaling in a dynamic, decentralized market for lemons. I derive general properties of equilibria, and in particular of fully separating equilibria. The most efficient separating equilibrium allows for the trade of every type in every period, a feature that remains even when all agents are infinitely patient – unlike the market freezing result obtained by Moreno and Wooders (2016) in a similar context but without the possibility for signaling through prices.<br>Este trabalho investiga o papel da sinalização em um mercado dinâmico de limões. Nós derivamos propriedades gerais dos equilíbrios, e em particular dos equilíbrios totalmente separantes. O equilíbrio separante mais eficiente permite que trocas ocorram em todos os períodos para tos os tipos, uma característica que permanece mesmo quado os agentes são infinitamente pacientes – ao contrário do resultado de congelamento de mercados obtido por Moreno e Wooders (2016) num contexto similiar, porém sem a possibilidade de sinalização via preços.
45
Villemot, Pierre. "Lemmes de zéros et distribution des valeurs des fonctions méromorphes." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM059/document.
Full textAbstract:
Cette thèse porte sur des propriétés arithmétiques des fonctions méromorphes et transcendantes d'une variable. Dans le chapitre 3, nous définissons des mesures de transcendance pour les fonctions holomorphes et méromorphes sur un domaine régulier de C puis nous majorons ces mesures en fonction de la distribution des petites valeurs de la fonction étudiée.Grâce aux théories de Nevanlinna et d'Ahlfors, nous étudions dans le chapitre 4 la distribution des petites valeurs de certaines classes de fonctions méromorphes sur D ou C afin d'obtenir pour celles-ci des majorations explicites de leurs mesures de transcendance. L'application principale de ce travail est l'obtention de nouveaux lemmes de zéros polynomiaux pour de grandes familles de fonctions méromorphes et en particulier pour les fonctions de Weierstrass et les fonctions fuchsiennes. Dans le chapitre 5, nous montrons que ces lemmes de zéros polynomiaux conduisent à des bornes logarithmiques du nombre de points algébriques de degré et hauteur bornée contenus dans les graphes des fonctions étudiées<br>This PhD thesis is about some arithmetic properties of meromorphic functions of one variable.In chapter 3, we define the transcendental measures for holomorphic and meromorphic functions on a regular domain of C, then we obtain upper bounds of these measures in terms of the distribution of small values of the function.Thanks to the Nevanlinna and Ahlfors theories, we study in chapter 4 the distribution of small values of some classes of meromorphic functions on D or C in order to obtain explicit upper bounds of transcendental measures.The main application of this work is the demonstration of new polynomial zero estimates for large classes of meromorphic functions, in particular for Weierstrass functions and fuchsian functions.In chapter 5, we prove that polynomial zero estimates lead to logarithmic bounds of the number of algebraic points of bounded degree and height contained in the graph of the function
46
Bacca, Salvatore. "Il lemma di Schwarz e la distanza di Kobayashi." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/13823/.
Full textAbstract:
Questa tesi è un approccio elementare alla teoria geometrica delle funzioni, campo che ebbe inizio con i lavori di Poincarè sulla geometria del disco. Affronteremo dapprima il Lemma di Schwarz ed alcune sue generalizzazioni che metteranno in correlazione il risultato analitico di tale asserto con il suo aspetto geometrico-differenziale. Introdurremo poi una distanza invariante su varietà complesse, la distanza di Kobayashi, e tramite questa dimostreremo i teoremi di Picard riguardanti il range dell'immagine di funzioni olomorfe sul piano complesso o su un dominio avente una singolarità isolata.
47
Lloyd, Simon Trevor. "Cr closing lemma results for flows on the torus." Thesis, University of Warwick, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.443968.
Full text
48
Jannel, Romaric. "La philosophie de Yamauchi Tokuryū (1890-1982) : genèse et desseins d’une pensée d’inspiration bouddhique au XXe siècle." Thesis, Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLP038.
Full textAbstract:
Cette thèse constitue la première étude jamais réalisée sur la philosophie de Yamauchi Tokuryū (1890-1982). La démarche de ce philosophe japonais est remarquable en ce qu’il chercha à proposer un dépassement englobant de ce qu’il nomme, d’une part, la « logique du logos » – qui figurait déjà chez Aristote et se structure autour des principes d’identité, de contradiction et du tiers exclu – et, d’autre part, la « logique du lemme » – méthode d’appréhension intuitionnelle des étants qui, née en Inde, serait d’inspiration essentiellement bouddhique. Notre propos est construit autour de l’analyse du tétralemme, de la manière dont Yamauchi le transforma et des problèmes philosophiques auxquels, par sa démarche, il essaya d’apporter une réponse originale<br>This work constitutes the first study ever concerning this philosophy of Yamauchi Tokuryū (1890-1982). The approach adopted by the Japanese philosopher is remarkable inasmuch as he aimed at presenting an encompassing overcoming of, on the one hand, what he calls the “logic of logos” – which was already present in Aristotle’s work and was structured around the laws of identity, non-contradiction and excluded middle – and, on the other hand, the “logic of lemma” – a method that allows to intuitionally grasp beings, which was born in India and was mainly inspired by Buddhism. Our study is constructed around the analysis of the tetralemma, the way Yamauchi changed its structure, as well as the philosophical problems to which he tried to provide innovative solutions
49
Pires, Benito Frazão. "Estabilidade assintótica e estrutural de campos vetoriais." Universidade de São Paulo, 2006. http://www.teses.usp.br/teses/disponiveis/55/55135/tde-02022007-093739/.
Full textAbstract:
O objetivo deste trabalho é provar um Closing Lema Parcial para variedades bidimensionais compactas, orientáveis ou não--orientáveis. Para enunciá--lo, considere um campo vetorial \\linebreak $X\\in\\mathfrak^r(M)$, $r\\ge 2$, de classe $C^r$ em uma variedade bidimensional compacta $M$, e seja $\\Sigma$ um segmento transversal a $X$ passando por um ponto recorrente não--trivial $p$ de $X$. Seja $P:\\Sigma\\to\\Sigma$ a correspondente transformação de primeiro retorno. O primeiro resultado deste trabalho consiste em mostrar que se $P$ tem a propriedade de que para todo $n\\ge N$ e $x\\in{m dom}\\,(P^n)$, $\\vert DP^n(x)\\vert<\\lambda$, onde $N\\in\\N$ e $0<\\lambda<1$, então existe um campo vetorial $Y$ arbitrariamente próximo de $X$ na topologia $C^r$ tendo uma trajetória periódica passando por $p$. O segundo resultado consiste em apresentar condições, sobre os expoentes de Lyapunov de $P$, para que $\\vert DP^n\\vert<\\lambda$ para todo $n\\ge N$. Nesta tese, também incluímos um resultado sobre a estabilidade assintótica no infinito de campos planares diferenciáveis, mas não necessariamente de classe $C^1$.<br>The aim of this work is to provide a Partial $C^r$ Closing Lemma for compact surfaces, orientable or non--orientable. To state it, let $X\\in\\mathfrak^r(M)$, $r\\ge 2$, be a $C^r$ vector field on a compact surface $M$ and let $\\Sigma$ be a transverse segment to $X$ passing through a non--trivial recurrent point $p$ of $X$. Let $P:\\Sigma\\to\\Sigma$ be the corresponding first return map. The first result of this work consists in showing that if $P^n$ has the property that for all $n\\ge N$ and $x\\in{m dom}\\,(P^n)$, $\\vert DP^n(x)\\vert<\\lambda$, where $N\\in\\N$ e $0<\\lambda<1$, then there exists a vector field $Y$ arbitrarily close to $X$ in the $C^r$ topology such that $p$ is a periodic point of $Y$. The second result consists in presenting sufficient conditions, upon the Lyapunov exponents of $P$, so that $\\vert DP^n\\vert<\\lambda$ for all $n\\ge N$. In this thesis, we also include a result concerning the asymptotic stability at infinity of planar differentiable vector fields, not necessarily of class $C^1$.
50
Tonon, Gustavo. "Avaliação de lagoas de lemnas para o polimento de esgoto doméstico." reponame:Repositório Institucional da UFSC, 2016. https://repositorio.ufsc.br/xmlui/handle/123456789/171996.
Full textAbstract:
Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Ambiental, Florianópolis, 2016.<br>Made available in DSpace on 2016-12-27T03:10:22Z (GMT). No. of bitstreams: 1
342309.pdf: 3166093 bytes, checksum: 6edb8a6d809a38896e02a1909b518896 (MD5)
Previous issue date: 2016<br>As lagoas de lemnas têm sido utilizadas com sucesso para o polimento de efluentes nos últimos anos, destacando a grande capacidade de remoção de nutrientes, e a produção de biomassa passível de valorização. O presente estudo objetivou avaliar esta tecnologia no tratamento de esgoto doméstico, investigar a produção de gás metano em testes laboratoriais com esta macrófita e avaliar a emissão e absorção de gases de efeito estufa (GEE) nas lagoas. Nesse último contexto da pesquisa foram avaliadas as emissões e fixação de CO2 bem como as emissões de CH4. Para isso, utilizou-se um experimento em escala piloto, composto por duas lagoas de lemnas em série (10,8m2 e TDH de 17 dias cada) para o tratamento de esgoto doméstico. O sistema foi operado com uma vazão de 200L.dia-1 e monitorado através análises de parâmetros físico-químicos (OD, pH, série nitrogenada, série de sólidos, PT, PO4-3, DQO, DBO, COT e turbidez). A análise dos GEE foi realizada com uma câmara de fluxo por equipamentos de medição in loco. Também, a taxa de crescimento e a composição da biomassa de macrófitas foram estudadas para fins de balanço de massa e valorização. Para avaliar o potencial de produção de biogás pela biomassa das lemnas geradas em excesso, um ensaio de potencial de produção de biometano (BMP) foi conduzido em escala laboratorial, comparando-se a biomassa fresca e a seca. Como resultados, observou-se eficiência em termos de concentração de nutrientes NT = 92,5% e PT = 91,2%, assim como para matéria orgânica DBO = 84,1% e DQO = 71,7%. A taxa de crescimento superficial das lemnas na primeira lagoa foi de 3,9 g.m-2.dia-1 e na segunda lagoa foi de 2,5 g.m-2.dia-1. Pela estimativa da fixação de CO2 para as lagoas avaliadas, chegou-se a uma taxa média de 24,9 g.m-2.d-1, aproximadamente 5 vezes mais elevada do que a taxa de emissão. A digestão anaeróbia de lemna seca apresentou elevada produção específica de gás (SGP) e produção específica de metano (SMP) (0,32 Nm³ CH4/kgSV e 0,19 Nm³CH4/kgSV, respectivamente). De maneira geral, as lagoas avaliadas operadas sob cargas superficiais médias de 6,5 kgNH3.ha-1.dia-1 e 13,58 kg DQO.ha-1.dia-1, se mostraram como uma tecnologia eficaz integrando tratamento de efluentes, baixas emissões de GEE e produção de biomassa passível de valorização.<br><br>Abstract : The duckweed ponds have been successfully used for polishing of effluents in recent years, highlighting the large capacity of removing nutrients and biomass amenable to recovery. Thus, this study aimed to evaluate this technology in domestic wastewater treatment, investigate the methane production with this macrophye and evaluate CO2 emission and fixation. For this, an experiment was conducted in a pilot scale, consists of two duckweed ponds in series (10,8 m2 and 17 days of HRT each) for domestic sewage treatment. The system was operated with a flow of 200L.d-1 and monitored through physical-chemical analysis (dissolved oxygen, pH, nitrogen series, solid series, total phosphorus, chemical oxygen demand, biochemical oxygen demand, dissolved organic carbon and turbidity). The GHG analysis was performed on-site with a flux chamber and portable equipment. Also, the growth rate and biomass composition were studied for mass balance purposes and recovery. To evaluate the biogas production potential for duckweed biomass generated in excess, a biomethane potential test (BMP) was conducted in laboratory scale by comparing the fresh and dry biomass. As a results we observed an important nutrient removal efficiency TN = 92.5% and TP = 91.2%, organic matter as well as BOD =84.1%, and COD = 71.7%. The relative growth rate was L1 = 3.9 g.m-2.dia-1 and L2 = 2.5 g.m-2.dia-1. CO2 fixation was reached at an average rate of 24.9 g.m-2.d-1 about 5 times higher than the emission rate. CH4 emissions were not detected. Anaerobic digestion of dry biomass was the process that had higher specific gas production (SGP) and specific methane production (SMP) (0.32 Nm³ CH4 / KgVS and 0.19 Nm³CH4 / KgVS, respectively). In general, ponds showed good results in nutrients removal, and shown as an effective wastewater treatment technology integrates , low emissions of greenhouse gases and biomass amenable to recovery .