Empacotamento e contagem em digrafos: cenários aleatórios e extremais (2016)
- Authors:
- Autor USP: PARENTE, ROBERTO FREITAS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/T.45.2017.tde-24052017-183349
- Subjects: CONFIGURAÇÕES COMBINATÓRIAS; TEORIA DOS GRAFOS; COMBINATÓRIA; ÁLGEBRA
- Keywords: Álgebra de flags; Arborescence; Arborescência; Combinatória extremal; Digrafos aleatórios; Extremal combinatorics; Flag algebras; Random digraphs; Torneios; Tournament
- Agências de fomento:
- Language: Português
- Abstract: Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido
- Imprenta:
- Data da defesa: 27.10.2016
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
PARENTE, Roberto Freitas. Empacotamento e contagem em digrafos: cenários aleatórios e extremais. 2016. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2016. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-24052017-183349/. Acesso em: 16 abr. 2026. -
APA
Parente, R. F. (2016). Empacotamento e contagem em digrafos: cenários aleatórios e extremais (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-24052017-183349/ -
NLM
Parente RF. Empacotamento e contagem em digrafos: cenários aleatórios e extremais [Internet]. 2016 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-24052017-183349/ -
Vancouver
Parente RF. Empacotamento e contagem em digrafos: cenários aleatórios e extremais [Internet]. 2016 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-24052017-183349/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
