Return to search

Convergent Sequences of Discrete Structures and Testability / SequÃncias Convergentes de Estruturas Discretas e Testabilidade

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / In this work, we studied the recent theory of convergent graph
sequences and its extensions to permutation and partially ordered sets with fix dimension. Weâve conjectured a lemma of weak regularity on intervals that, if this conjecture is true, we can extend this theory to ordered graphs, which are graphs such that there is a total order on its vertices. We show some interesting relations on permutation and partially ordered sets with ordered graphs. Then, we obtain another proof to the existence of limit objects for all convergent permutation sequences. We also proved that all hereditary property of either permutation or ordered graph is testable. / Neste trabalho, estudamos a teoria recente de convergÃncia de
sequÃncias de grafos e suas extensÃes para permutaÃÃes e ordens parciais de dimensÃo fixa. Conjecturamos um lema de regularidade fraca de grafos em intervalos que, se for verdadeira, nos possibilita estender essa teoria para grafos ordenados, que sÃo grafos tais que existe uma ordem total entre os vÃrtices. Mostramos algumas relaÃÃes interessantes de permutaÃÃes e ordens parciais com grafos ordenados. Com isso, conseguimos uma prova alternativa para a existÃncia de objetos limites de qualquer sequÃncia convergente de permutaÃÃes. Provamos tambÃm que toda propriedade hereditÃria de permutaÃÃes ou grafos ordenados à testÃvel.

Identiferoai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:5126
Date27 February 2012
CreatorsAntonio Josefran de Oliveira Bastos
ContributorsRudini Menezes Sampaio, JuvÃncio Santos Nobre, Fabricio Siqueira Benevides
PublisherUniversidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0018 seconds