Master's Dissertation
DOI
Document
Author
Full name
Marcelo Tadeu de Sá Oliveira Sales
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2018
Supervisor
Committee
Kohayakawa, Yoshiharu (President)
Mandel, Arnaldo
Moreira, Carlos Gustavo Tamm de Araujo
Title in English
Extremal and probabilistic problems in order types
Keywords in English
Combinatorial geometry
Combinatorics
Order types
Probabilistic method
Abstract in English
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.
Title in Portuguese
Problemas extremais e probabilísticos em o-tipos
Keywords in Portuguese
Combinatória
Geometria combinatória
Métodos probabilísticos
O-tipos
Abstract in Portuguese
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.