• 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
 
 
Mémoire de Maîtrise
DOI
10.11606/D.45.2011.tde-22032012-150640
Document
Auteur
Nom complet
Roberto Freitas Parente
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2011
Directeur
Jury
Kohayakawa, Yoshiharu (Président)
Hoppen, Carlos
Sampaio, Rudini Menezes
Titre en portugais
Quantidade de orientações de grafos livres de circuitos direcionados cíclicos
Mots-clés en portugais
Grafos aleatórios
Lema da regularidade esparso
Orientações proibidas
Resumé en portugais
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.
Titre en anglais
The number of orintations with no directed cycle of given length.
Mots-clés en anglais
forbidden orientations.
Random graphs
sparse regularity lemma
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2012-04-04
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2022. Tous droits réservés.