DIRECTED GRAPHS WITH LOWER ORIENTATION RAMSEY THRESHOLDS

Autor(es)

Barros, Gabriel Ferreira ; Cavalar, Bruno Pasqualotto ; Kohayakawa, Yoshiharu ; Mota, Guilherme Oliveira ; Naia, Tassio

• Tipo de documento: Artigo Científico
• Fonte: RAIRO-OPERATIONS RESEARCH; v. 58, n. 4, p. 13-pg., 2024-09-09.

Resumo

We investigate the threshold p((H) over right arrow) = p((H) over right arrow)(n) for the Ramsey-type property G(n, p) -> (sic)H, where G(n, p) is the binomial random graph and G -> (H) over right arrow indicates that every orientation of the graph G contains the oriented graph (sic) H as a subdigraph. Similarly to the classical Ramsey setting, the upper bound p((H) over right arrow) <= Cn(-1/m2((H) over right arrow)) is known to hold for some constant C = C((H) over right arrow), where m(2)((H) over right arrow) denotes the maximum 2-density of the underlying graph H of (H) over right arrow. While this upper bound is indeed the threshold for some (H) over right arrow, this is not always the case. We obtain examples arising from rooted products of orientations of sparse graphs (such as forests, cycles and, more generally, subcubic {K-3, K-3,K-3}-free graphs) and arbitrarily rooted transitive triangles. (AU)

• Processo FAPESP: 18/05557-7 - Complexidade computacional e combinatória extremal
• Beneficiário: Bruno Pasqualotto Cavalar
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
• Processo FAPESP: 20/16570-4 - Problemas em Teoria de Ramsey, grafos aleatórios e imersões
• Beneficiário: Tássio Naia dos Santos
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 19/04375-5 - Problemas em Teoria de Ramsey, grafos aleatórios e imersões
• Beneficiário: Tássio Naia dos Santos
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado