| 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; v. 56, n. 4, p. 1016-1030, JUL 2020. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| 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 |