• 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
 
 
Doctoral Thesis
DOI
https://doi.org/10.11606/T.45.2002.tde-20210729-125441
Document
Author
Full name
Jair Donadelli Junior
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2001
Supervisor
Title in Portuguese
Resultados de Ramsey e de densidade para grafos pseudo-aleatórios esparsos
Keywords in Portuguese
Teoria Dos Grafos
Abstract in Portuguese
Neste trabalho estudamos problemas do tipo ramsey e do tipo densidade para grafos e grafos orientados esparsos. Começamos dedicando o primeiro capítulo a uma das principais ferramentas no ataque aos problemas: o Lema de Regularidade de Szemerédi. Na seqüência, provamos uma generalização de um lema de contagem devido a Kohayakawa e Kreuter (1997). Com esse resultado, aplicamos um método inventado por Furedi para provar que quase certamente Gp ->1/2+B Cl para qualquer B>0, onde Gp é o grafo orientado aleatório binomial de ordem n e densidade p = e(Gp)/n2 = An-1+1/(l-1), e A = A(B) > 0 é uma constante suficientemente grande e G ->1/2+B Cl significa que todo subgrafo J C G com e(J)> ou = (1/2+B) e (G) contém o circuito Cl. Como conseqüência disso obtemos uma família infinita de contra-exemplos para uma generalização de uma conjectura de Woodall. Depois, usamos o lema de contagem de circuitos para mostrar que para todo grafo H de uma família apropriada de grafos 2-conexos e para todo n suficientemente grande, existem grafos In tais que In -> (Cl, H) e In é minimal com respeito a essa propriedade. O símbolo In -> (Cl, H) significa que para qualquer 2-coloração de E(In) com as cores vermelha e azul, ou teremos uma cópia monocromática vermelha de Cl ou uma cópia monocromática azul de H contida em In. Finalmente, demonstramos que para qualquer grafo H, se subdividimos suas arestas s vezes, onde C1 log n < ou = s < ou = C2n, então o número de ramsey para aresta para grafo resultante é O(n). Esse resultado está relacionado com uma conjectura recente de Igor Pak
Title in English
not available
Abstract in English
not available
 
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
2021-07-29
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2021. All rights reserved.