Tese de Doutorado
Documento
Tese de Doutorado
Autor
Nome completo
Rudini Menezes Sampaio
E-mail
Unidade da USP
Instituto de Matemática e Estatística
Área do Conhecimento
Data de Defesa
2008-11-18
Imprenta
São Paulo, 2008
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Hoppen, Carlos
Kira, Elisabeti
Moreira, Carlos Gustavo Tamm de Araujo
Oliveira, Roberto Imbuzeiro Moraes Felinto de
Título em português
Limites de seqüências de permutações de inteiros
Palavras-chave em português
densidade de subpermutações, Lema da regularidade, objeto limite, permutações, quase-aleatoriedade, sequências convergentes, testabilidade
Resumo em português
Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações.
Título em inglês
Limits of permutation sequences
Palavras-chave em inglês
convergent sequences, density of subpermutations, limit object, permutations, quasirandomness, Regularity lemma, testability
Resumo em inglês
We introduce the concept of convergent sequence of permutations and we prove the existence of a limit object for these sequences. We also introduce a new and more general model of random permutation based on these limit objects and we introduce a new metric for permutations. We also prove that sequences of random permutations are convergent and we prove the equivalence between this notion of convergence and convergence in this new metric. We also show some applications for samplig and quasirandomness. We also prove a characterization for testable parameters of permutations.
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso: Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2011-05-12
Trabalhos decorrentes
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.