• 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
 
 
Master's Dissertation
DOI
10.11606/D.45.2011.tde-22032012-150640
Document
Author
Full name
Roberto Freitas Parente
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2011
Supervisor
Committee
Kohayakawa, Yoshiharu (President)
Hoppen, Carlos
Sampaio, Rudini Menezes
Title in Portuguese
Quantidade de orientações de grafos livres de circuitos direcionados cíclicos
Keywords in Portuguese
Grafos aleatórios
Lema da regularidade esparso
Orientações proibidas
Abstract in Portuguese
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.
Title in English
The number of orintations with no directed cycle of given length.
Keywords in English
forbidden orientations.
Random graphs
sparse regularity lemma
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2012-04-04
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2022. All rights reserved.