• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2011.tde-22032012-150640
Documento
Autor
Nome completo
Roberto Freitas Parente
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2011
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Hoppen, Carlos
Sampaio, Rudini Menezes
Título em português
Quantidade de orientações de grafos livres de circuitos direcionados cíclicos
Palavras-chave em português
Grafos aleatórios
Lema da regularidade esparso
Orientações proibidas
Resumo em português
Seja H' uma orientação do grafo H. Alon e Yuster [The number of orientations having no fixed tounament, Combinatória, 26 (2006), no. 1, 1-6] propuseram o problema de determinar ou estimar D(n,m,H'), a quantidade máxima de orientações livres de H' de um grafo com n vértices e m arestas. Se substituirmos o máximo pelo 'máximo essencial', ou seja, consideramos o máximo sobre quase todos os grafos de n vértices e com m arestas, em oposição à todos deles, o problema é mais acessível. Mostramos que esse máximo essencial é 2^o(m) se H' é o circuito direcionado cíclico C'_l de tamanho l (l >= 3), se m >> n^{1+1/(l-1)}. Por outro lado, o mínimo essencial é 2^(1-o(1))m, se m << n^{1+1/(l-1)}. O método de prova nos dá resultado da mesma natureza para grafos orientados bipartidos H' que contém circuito direcionado cícliclo.
Título em inglês
The number of orintations with no directed cycle of given length.
Palavras-chave em inglês
forbidden orientations.
Random graphs
sparse regularity lemma
Resumo em inglês
Let H' b an orientation of graph H. Alon and Yuster [The number of orientations having no fixed tounament, Combinatória, 26 (2006), no. 1, 1-6] proposed the problem of determining or estimating D(n,m,H'), the maximum number of H'-free orientations a graph with n vertices and m edges may have. If we replace the maximum by 'essential maximum', that is, if we are allowed to consider the maximum over the mojority of n-vertex graphs with m edges, as opposed to all of them, the problem becomes more accessible. We show that this essential maximum is 2^o(m) if H' is the directed cycle C'_l of length l (l>= 3), as long as m >> n^{1+1/(l-1)}. On the other hand, the corresponding essential minimum is 2^(1-o(1)) if m << n^{1+1/(l-1). The proof method yields results of the same nature for oriented bipartite graphs H' that contain a directed cycle.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2012-04-04
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2023. Todos os direitos reservados.