| Full text | |
| Author(s): |
Total Authors: 4
|
| Affiliation: | [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
Total Affiliations: 4
|
| Document type: | Journal article |
| Source: | RANDOM STRUCTURES & ALGORITHMS; JAN 2020. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Research Grants - Young Investigators Grants |