Dois resultados em combinatória contemporânea (2013)
- Authors:
- Autor USP: MOTA, GUILHERME OLIVEIRA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- 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
-
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: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457. Acesso em: 10 fev. 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 http://www.teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457 -
NLM
Mota GO. Dois resultados em combinatória contemporânea [Internet]. 2013 ;[citado 2026 fev. 10 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457 -
Vancouver
Mota GO. Dois resultados em combinatória contemporânea [Internet]. 2013 ;[citado 2026 fev. 10 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457 - Counting Ck -free orientations of G(n, p)
- Counting orientations of graphs with no strongly connected tournaments
- Combinatória
- Árvores Ramsey-restritas mínimas
- Counting orientations of random graphs with no directed k-cycles
- Counting orientations of graphs with no strongly connected tournaments
- Some results on irregular decomposition of graphs
- Decomposing split graphs into locally irregular graphs
- A counting lemma for sparse pseudorandom hypergraphs
- Covering 3-edge-colored random graphs with monochromatic trees
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
