Counting restricted orientations of random graphs

Autor(es)

Collares, Mauricio ^[1] ; Kohayakawa, Yoshiharu ^[2] ; Morris, Robert ^[3] ; Mota, Guilherme O. ^[4]

Afiliação do(s) autor(es)

^[1] Univ Fed Minas Gerais, Dept Matemat, Belo Horizonte, MG - Brazil

^[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil

^[3] IMPA, Rio De Janeiro - Brazil

^[4] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: RANDOM STRUCTURES & ALGORITHMS; JAN 2020.
• Citações Web of Science: 0

Resumo

We count orientations of G(n,p) avoiding certain classes of oriented graphs. In particular, we study Tr(n,p), the number of orientations of the binomial random graph G(n,p) in which every copy of Kr is transitive, and Sr(n,p), the number of orientations of G(n,p) containing no strongly connected copy of Kr. We give the correct order of growth of logTr(n,p) and logSr(n,p) up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota, and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• 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