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
- 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
-
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: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-24052017-183349/. Acesso em: 07 out. 2024. -
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 http://www.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 2024 out. 07 ] Available from: http://www.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 2024 out. 07 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-24052017-183349/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
