Resultados de Ramsey e de densidade para grafos pseudo-aleatórios esparsos (2002)
- Authors:
- Autor USP: DONADELLI JÚNIOR, JAIR - IME
- Unidade: IME
- Sigla do Departamento: MAP
- DOI: 10.11606/T.45.2002.tde-20210729-125441
- Assunto: TEORIA DOS GRAFOS
- Language: Português
- Abstract: 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 paragrafo resultante é O(n). Esse resultado está relacionado com uma conjectura recente de Igor Pak
- Imprenta:
- Data da defesa: 04.03.2002
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
DONADELLI JUNIOR, Jair. Resultados de Ramsey e de densidade para grafos pseudo-aleatórios esparsos. 2002. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2002. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-125441/. Acesso em: 07 maio 2026. -
APA
Donadelli Junior, J. (2002). Resultados de Ramsey e de densidade para grafos pseudo-aleatórios esparsos (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-125441/ -
NLM
Donadelli Junior J. Resultados de Ramsey e de densidade para grafos pseudo-aleatórios esparsos [Internet]. 2002 ;[citado 2026 maio 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-125441/ -
Vancouver
Donadelli Junior J. Resultados de Ramsey e de densidade para grafos pseudo-aleatórios esparsos [Internet]. 2002 ;[citado 2026 maio 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-125441/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
