Extremal and probabilistic problems in order types (2018)
- Authors:
- Autor USP: SALES, MARCELO TADEU DE SÁ OLIVEIRA - IME
- Unidade: IME
- Sigla do Departamento: MAT
- Subjects: GEOMETRIA COMBINATÓRIA; COMBINATÓRIA; MÉTODOS PROBABILÍSTICOS
- Keywords: Combinatorial geometry; Combinatorics; O-tipos; Order types; Probabilistic method
- Agências de fomento:
- Language: Inglês
- Abstract: 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
- Imprenta:
- Data da defesa: 15.06.2018
-
ABNT
SALES, Marcelo Tadeu de Sá Oliveira. Extremal and probabilistic problems in order types. 2018. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45131/tde-25042019-000504/. Acesso em: 10 jan. 2026. -
APA
Sales, M. T. de S. O. (2018). Extremal and probabilistic problems in order types (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45131/tde-25042019-000504/ -
NLM
Sales MT de SO. Extremal and probabilistic problems in order types [Internet]. 2018 ;[citado 2026 jan. 10 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45131/tde-25042019-000504/ -
Vancouver
Sales MT de SO. Extremal and probabilistic problems in order types [Internet]. 2018 ;[citado 2026 jan. 10 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45131/tde-25042019-000504/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
