Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Counting restricted orientations of random graphs

Texto completo
Autor(es):
Collares, Mauricio [1] ; Kohayakawa, Yoshiharu [2] ; Morris, Robert [3] ; Mota, Guilherme O. [4]
Número total de Autores: 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
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 56, n. 4, p. 1016-1030, JUL 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 T-r(n, p), the number of orientations of the binomial random graph G(n, p) in which every copy of K-r is transitive, and S-r(n, p), the number of orientations of G(n, p) containing no strongly connected copy of K-r. We give the correct order of growth of log T-r(n, p) and log S-r(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
Linha de fomento: 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
Linha de fomento: Auxílio à Pesquisa - Apoio a Jovens Pesquisadores