• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2019.tde-25042019-000504
Documento
Autor
Nome completo
Marcelo Tadeu de Sá Oliveira Sales
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2018
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Mandel, Arnaldo
Moreira, Carlos Gustavo Tamm de Araujo
Título em inglês
Extremal and probabilistic problems in order types
Palavras-chave em inglês
Combinatorial geometry
Combinatorics
Order types
Probabilistic method
Resumo em inglês
A configuration is a finite set of points in the plane. Two configurations have the same order type if there exists a bijection between them that preserves the orientation of every ordered triple. A configuration A contains a copy of a configuration B if some subset of A has the same order type of B and we denote this by B \subset A. For a configuration B and a integer N, the extremal number ex(N,B)=max{|A|: B ot \subset A \subset [N]^2} is the maximum size of a subset of [N]^2 without a copy of B. We give an upper bound for general and convex cases. A random N-set is a set obtained by randomly choosing N points uniformly and independently in the unit square. A configuration is n-universal if contains all order types in general position of size n. We obtain the threshold for the n-universal property up to a log log factor, that is, we obtain integers N_0 and N_1 with log log N_1=O(log log N_0) such that if N >> N_1 (N << N_0), then a random N-set is n-universal with probability tending to 1 (tending to 0). We also determine a bound for the probability of obtaining a random set without a copy of a fixed configuration.
Título em português
Problemas extremais e probabilísticos em o-tipos
Palavras-chave em português
Combinatória
Geometria combinatória
Métodos probabilísticos
O-tipos
Resumo em português
Uma configuração é um conjunto finito de pontos no plano. Duas configurações possuem o mesmo o-tipo se existe uma bijeção entre elas que preserva a orientação de toda tripla orientada. Uma configuração A contém uma cópia da configuração B se algum subconjunto de A possui o mesmo o-tipo que B e denotamos este fato por B \subset A. Para uma configuração B e um inteiro N, o número extremal ex(N,B)=max{|A|: B ot \subset A \subset [N]^2} é o maior tamanho de um subconjunto de [N]^2 sem uma cópia de B. Neste trabalho, determinamos cotas superiores para o caso geral e para o caso convexo. Um N-conjunto aleatório é um conjunto obtido escolhendo N pontos uniformemente e independentemente ao acaso do quadrado unitário. Uma configuração é n-universal se contém todos os o-tipos de tamanho n. Determinamos o limiar da propriedade de um N-conjunto aleatório ser n-universal a menos de erros da ordem de log log, isto é, determinamos inteiros N_0 e N_1 com log log N_0=O(log log N_1) tais que se N >> N_1 (N << N_0), então o N-conjunto aleatório é n-universal com probabilidade tendendo a 1 (tendendo a 0). Também obtivemos cotas para a probabilidade de um conjunto aleatório não possuir determinado o-tipo.
 
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
2019-04-30
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.