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; 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
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