| Full text | |
| Author(s): |
Chang, Yulin
[1]
;
Han, Jie
[2]
;
Kohayakawa, Yoshiharu
[3]
;
Morris, Patrick
[4, 5]
;
Mota, Guilherme Oliveira
[3]
Total Authors: 5
|
| Affiliation: | [1] Shandong Univ, Data Sci Inst, Jinan - Peoples R China
[2] Beijing Inst Technol, Sch Math & Stat, Beijing - Peoples R China
[3] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
[4] Free Univ Berlin, Berlin - Germany
[5] Berlin Math Sch, Berlin - Germany
Total Affiliations: 5
|
| Document type: | Journal article |
| Source: | RANDOM STRUCTURES & ALGORITHMS; v. 60, n. 2 JUL 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
We determine, up to a multiplicative constant, the optimal number of random edges that need to be added to a k-graph H with minimum vertex degree omega(nk-1) to ensure an F-factor with high probability, for any F that belongs to a certain class F of k-graphs, which includes, for example, all k-partite k-graphs, K4(3)- and the Fano plane. In particular, taking F to be a single edge, this settles a problem of Krivelevich, Kwan, and Sudakov. We also address the case in which the host graph H is not dense, indicating that starting from certain such H is essentially the same as starting from an empty graph (namely, the purely random model). (AU) | |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research 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 |