Disertación de Maestría
DOI
Documento
Autor
Nombre completo
Marcelo Tadeu de Sá Oliveira Sales
Dirección Electrónica
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2018
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Mandel, Arnaldo
Moreira, Carlos Gustavo Tamm de Araujo
Título en inglés
Extremal and probabilistic problems in order types
Palabras clave en inglés
Combinatorial geometry
Combinatorics
Order types
Probabilistic method
Resumen en 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 en portugués
Problemas extremais e probabilísticos em o-tipos
Palabras clave en portugués
Combinatória
Geometria combinatória
Métodos probabilísticos
O-tipos
Resumen en 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.

ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2019-04-30