• 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
 
 
Disertación de Maestría
DOI
10.11606/D.45.2011.tde-22032012-150640
Documento
Autor
Nombre completo
Roberto Freitas Parente
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2011
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Hoppen, Carlos
Sampaio, Rudini Menezes
Título en portugués
Quantidade de orientações de grafos livres de circuitos direcionados cíclicos
Palabras clave en portugués
Grafos aleatórios
Lema da regularidade esparso
Orientações proibidas
Resumen en 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 en inglés
The number of orintations with no directed cycle of given length.
Palabras clave en inglés
forbidden orientations.
Random graphs
sparse regularity lemma
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2012-04-04
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.