Menu



Exportar registro bibliográfico

Metrics:

Tese

Dois resultados em combinatória contemporânea (2013)

  • Authors:
  • Autor USP: MOTA, GUILHERME OLIVEIRA - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • DOI: 10.11606/T.45.2013.tde-31102013-110457
  • Assunto: COMBINATÓRIA
  • Agências de fomento:
  • Language: Português
  • Abstract: Dois problemas combinatórios são estudados: (i) determinar a quantidade de cópias de um hipergrafo fixo em um hipergrafo uniforme pseudoaleatório, e (ii) estimar números de Ramsey de ordem dois e três para grafos com largura de banda pequena e grau máximo limitado. Apresentamos um lema de contagem para estimar a quantidade de cópias de um hipergrafo k-uniforme linear livre de conectores (conector é uma generalização de triângulo, para hipergrafos) que estão presentes em um hipergrafo esparso pseudoaleatório G. Considere um hipergrafo k-uniforme linear H que é livre de conectores e um hipergrafo k-uniforme G com n vértices. Seja d_H=\max\{\delta(J): J\subset H\} e D_H=\min\{k d_H,\Delta(H)\}. Estabelecemos que, se os vértices de G não possuem grau grande, famílias pequenas de conjuntos de k-1 elementos de V(G) não possuem vizinhança comum grande, e a maioria dos pares de conjuntos em {V(G)\choose k-1} possuem a quantidade ``correta'' de vizinhos, então a quantidade de imersões de H em G é (1+o(1))n^{|V(H)|}p^{|E(H)|}, desde que p\gg n^{1/D_H} e |E(G)|={n\choose k}p. Isso generaliza um resultado de Kohayakawa, Rödl e Sissokho [Embedding graphs with bounded degree in sparse pseudo\-random graphs, Israel J. Math. 139 (2004), 93--137], que provaram que, para p dado como acima, esse lema de imersão vale para grafos, onde H é um grafo livre de triângulos. Determinamos assintoticamente os números de Ramsey de ordem dois e três para grafos bipartidos com largura de banda pequena e grau máximo limitado. Mais especificamente, determinamos assintoticamente o número de Ramsey de ordem dois para grafos bipartidos com largura de banda pequena e grau máximo limitado, e o número de Ramsey de ordem três para tais grafos, com a suposição adicional de que ambas as classes do grafo bipartido têm aproximadamente o mesmo tamanho.
  • Imprenta:
  • Data da defesa: 30.08.2013
    • Acesso à fonteAcesso à fonteDOI

    Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).

    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:

    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

    • ABNT

      MOTA, Guilherme Oliveira. Dois resultados em combinatória contemporânea. 2013. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2013. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457. Acesso em: 16 abr. 2026.

    • APA

      Mota, G. O. (2013). Dois resultados em combinatória contemporânea (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457

    • NLM

      Mota GO. Dois resultados em combinatória contemporânea [Internet]. 2013 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457

    • Vancouver

      Mota GO. Dois resultados em combinatória contemporânea [Internet]. 2013 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2026