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. / 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.

Orientador: Jose Carlos de Souza Kiihl / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-22T06:14:00Z (GMT). No. of bitstreams: 1 Goncalves_AlexandreCasassola_M.pdf: 692699 bytes, checksum: 1b9c1637640944dd47077382ccdbf867 (MD5) Previous issue date: 1997 / Resumo: Não informado. / Abstract: Not informed. / Mestrado / Mestre em Matemática

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. / 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.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

Submitted by William Michon Jr (wmichon@fgvmail.br) on 2016-01-12T00:42:38Z No. of bitstreams: 1 TeseWilliam.pdf: 1615824 bytes, checksum: 897cfc6ac3606eb91d728cc52748cb1e (MD5) / Approved for entry into archive by BRUNA BARROS (bruna.barros@fgv.br) on 2016-01-13T13:19:57Z (GMT) No. of bitstreams: 1 TeseWilliam.pdf: 1615824 bytes, checksum: 897cfc6ac3606eb91d728cc52748cb1e (MD5) / Approved for entry into archive by Maria Almeida (maria.socorro@fgv.br) on 2016-02-11T17:50:48Z (GMT) No. of bitstreams: 1 TeseWilliam.pdf: 1615824 bytes, checksum: 897cfc6ac3606eb91d728cc52748cb1e (MD5) / Made available in DSpace on 2016-02-11T17:51:06Z (GMT). No. of bitstreams: 1 TeseWilliam.pdf: 1615824 bytes, checksum: 897cfc6ac3606eb91d728cc52748cb1e (MD5) Previous issue date: 2015-07-13 / Esta tese é composta de três artigos. No primeiro artigo, ``Risk Taking in Tournaments', é considerado um torneio dinâmico no qual jogadores escolhem como alocar seu tempo em atividades que envolvem risco. No segundo artigo, ``Unitização de Jazidas de Petróleo: Uma Aplicação do Modelo de Green e Porter' é analisado a factibilidade de se haver um acordo de cooperação em um ambiente de common-pool com incerteza nos custos das empresas. No terceiro artigo, ``Oilfield Unitization Under Dual Fiscal Regime: The Regulator Role over the Bargaining', por sua vez, é estudado a unitização quando existem dois regimes fiscais distintos, como os jogadores se beneficiam disso e o papel do regulador no regime de partilha.

Orientador: Caio Jose Colleti Negreiros / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-08T09:41:20Z (GMT). No. of bitstreams: 1 Bressan_JoaoPaulo_M.pdf: 1270495 bytes, checksum: 690edfeed4929635ff181ad3063aaadb (MD5) Previous issue date: 2007 / Resumo: O objetivo deste trabalho é estudar a relação existente entre holomorfia e harmonicidade de aplicações f : M 2 (IF; J; ds2? ), onde M 2 é uma superfície de Riemann compacta, orientável e IF é a variedade bandeira maximal. Para isto, apresentamos parte da teoria geral de aplicações harmônicas e holomorfas, necessária para demonstrar o teorema de Lichnerowicz. Uma de suas conseqüências é uma ferramenta importante neste estudo, pois fornece o seguinte critério: se f é J-holomorfa e ds2? é (1,2)-simplética, então f é harmônica. Portanto, também estamos interessados em descrever as métricas (1,2)-simpléticas nas variedades bandeira. Primeiramente, no caso geométrico, estudamos a variedade bandeira complexa maximal de subespaços encaixados IF(n). Posteriormente, este estudo é generalizado para outras variedades bandeiras maximais IF, definidas através de álgebras de Lie semi-simples complexas. Ainda, demonstramos o teorema de Burstall-Salamon, que fornece propriedades da estrutura quase complexa invariante J através de um torneio ?J associado. Finalmente, exibimos as equações de Cauchy-Riemann e de Euler-Lagrange para estas aplicações, e apresentamos exemplos de famílias de funções equi-harmônicas / Abstract: The goal of this work is to study the relationship bettwen holomorphicity and harmonicity of maps f: M 2 (IF; J; ds2? ), where M 2 is a compact, orientable Riemann surface and IF is the full-flag manifold. With this pourpose, we present part of the general holomorphic/harmonic maps theory, which is necessary to prove the Lichnerowicz theorem.It states like consequence a criterion, which is an important tool in this study: if f is J-holomorphic and ds2? é (1,2)-symplectic, then f is harmonic. Therefore, we are interested in to describe (1,2)-symplectc metrics on the flag manifold.Firstly, in the geometrical case, we study the complex full-flag manifold IF(n). Later, we generalize this study to other full-flag manifolds IF, which is defined through complex semisimple Lie algebras. Also, we prove the Burstall-Salamon theorem, which gives some properties of the almost complex structure J through an associated tournament ?J. Finally, we show-up the Cauchy-Riemann equations and the Euler-Lagrange equations to this maps, and present examples of families of equi-harmonic maps / Mestrado / Mestre em Matemática

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of its edge density. The theory of flag algebras, however, can be used to study the asymptotic density of several combinatorial objects. In this dissertation, we present two original results obtained in the theory of tournaments through application of flag algebra proof techniques. The first result concerns minimization of the asymptotic density of transitive tournaments in a sequence of tournaments, which we prove to occur if and only if the sequence is quasi-random. As a byproduct, we also obtain new quasi-random characterizations and several other flag algebra elements whose density is minimized if and only if the sequence is quasi-random. The second result concerns a class of equivalent properties of a sequence of tournaments that we call quasi-carousel properties and that, in a similar fashion as quasi-random properties, force the sequence to converge to a specific limit homomorphism. Several quasi-carousel properties, when compared to quasi-random properties, suggest that quasi-random sequences and quasi-carousel sequences are the furthest possible from each other within the class of almost balanced sequences. / Alexander A. Razborov (2007) desenvolveu a teoria de álgebras de flags para calcular a densidade assintótica mínima de triângulos em um grafo em função de sua densidade de arestas. A teoria das álgebras de flags, contudo, pode ser usada para estudar densidades assintóticas de diversos objetos combinatórios. Nesta dissertação, apresentamos dois resultados originais obtidos na teoria de torneios através de técnicas de demonstração de álgebras de flags. O primeiro resultado compreende a minimização da densidade assintótica de torneios transitivos em uma sequência de torneios, a qual provamos ocorrer se e somente se a sequência é quase aleatória. Como subprodutos, obtemos também novas caracterizações de quase aleatoriedade e diversos outros elementos da álgebra de flags cuja densidade é minimizada se e somente se a sequência é quase aleatória. O segundo resultado compreende uma classe de propriedades equivalentes sobre uma sequência de torneios que chamamos de propriedades quase carrossel e que, de uma forma similar às propriedades quase aleatórias, forçam que a sequência convirja para um homomorfismo limite específico. Várias propriedades quase carrossel, quando comparadas às propriedades quase aleatórias, sugerem que sequências quase aleatórias e sequências quase carrossel estão o mais distantes possível umas das outras na classe de sequências quase balanceadas.

Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of its edge density. The theory of flag algebras, however, can be used to study the asymptotic density of several combinatorial objects. In this dissertation, we present two original results obtained in the theory of tournaments through application of flag algebra proof techniques. The first result concerns minimization of the asymptotic density of transitive tournaments in a sequence of tournaments, which we prove to occur if and only if the sequence is quasi-random. As a byproduct, we also obtain new quasi-random characterizations and several other flag algebra elements whose density is minimized if and only if the sequence is quasi-random. The second result concerns a class of equivalent properties of a sequence of tournaments that we call quasi-carousel properties and that, in a similar fashion as quasi-random properties, force the sequence to converge to a specific limit homomorphism. Several quasi-carousel properties, when compared to quasi-random properties, suggest that quasi-random sequences and quasi-carousel sequences are the furthest possible from each other within the class of almost balanced sequences. / Alexander A. Razborov (2007) desenvolveu a teoria de álgebras de flags para calcular a densidade assintótica mínima de triângulos em um grafo em função de sua densidade de arestas. A teoria das álgebras de flags, contudo, pode ser usada para estudar densidades assintóticas de diversos objetos combinatórios. Nesta dissertação, apresentamos dois resultados originais obtidos na teoria de torneios através de técnicas de demonstração de álgebras de flags. O primeiro resultado compreende a minimização da densidade assintótica de torneios transitivos em uma sequência de torneios, a qual provamos ocorrer se e somente se a sequência é quase aleatória. Como subprodutos, obtemos também novas caracterizações de quase aleatoriedade e diversos outros elementos da álgebra de flags cuja densidade é minimizada se e somente se a sequência é quase aleatória. O segundo resultado compreende uma classe de propriedades equivalentes sobre uma sequência de torneios que chamamos de propriedades quase carrossel e que, de uma forma similar às propriedades quase aleatórias, forçam que a sequência convirja para um homomorfismo limite específico. Várias propriedades quase carrossel, quando comparadas às propriedades quase aleatórias, sugerem que sequências quase aleatórias e sequências quase carrossel estão o mais distantes possível umas das outras na classe de sequências quase balanceadas.

O Traicitié de la forme et devis comme on fait les tournois (Paris, Bibliothèque nationale de France, ms. Français 2695) escrito por volta de 1460 pelo duque René dAnjou (1409-1480) merece destaque por sintetizar em um único trabalho práticas da cultura de corte principesca tardo-medieval e pela originalidade em combinar material textual e iconográfico para transmitir a mensagem pretendida pelo autor. Optamos pelo trabalho com o códice em questão devido à difusão de documentos através dos meios eletrônicos, pela singularidade da obra e carência de edições modernas. Manuscritos medievais são objetos foco de diferentes campos de pesquisa, o que nos leva a restringir o escopo do nosso trabalho à análise textual a partir da nossa transcrição paleográfica. O objetivo desse trabalho será examinar a dupla funcionalidade do ms. Fr. 2695 por meio da análise do discurso. Mediante o exame qualitativo e quantitativo do corpus lexical, e da comparação com fontes externas, investigaremos primeiramente a função do códice em registrar a prática do torneio para estabelecer como seria o combate idealizado pelo duque e quão longe estaria da prática corrente. Em seguida, procuraremos decifrar o influxo de escritos corteses, cavaleirescos e principescos no interior do tratado para determinar a construção ideológica, de maneira a persuadir o leitor a adotar um determinado comportamento frente à sociedade. / The Traicitié de la forme et devis comme on fait les tournois (Paris, Bibliothèque nationale de France, ms. Français 2695) written around 1460 by the Duke René d\'Anjou (1409-1480) is noteworthy for synthesizing in a single work practices from princely court culture of the Late Middle Ages and the originality of combining textual and iconographic material in order to convey a message intended by the author. We opted for working with the codex in question due to the dissemination of documents by electronic means, by the uniqueness of the work and lack of modern editions. Medieval manuscripts are objects focus of different research fields, which leads us to narrow the scope of our work to textual analysis from our paleographic transcription. The aim of this study is to examine the dual functionality of the ms. Fr. 2695 through discourse analysis. Through qualitative and quantitative examination of the lexical corpus, and the comparison with external sources, first we will investigate the function of the codex to record the practice of the tournament, and then establish how the fight would be devised by the Duke and how far was from current practice. Second, we will try to decipher the influence of courtly, knightly and princely literature within the treatise in order to determine the ideological construction to persuade the reader to adopt a certain behavior in society.