Random cliques in random graphs and sharp thresholds for F-factors
<p>We show that for each r ≥ 4, in a density range extending up to, and slightly beyond, the threshold for a Kr-factor, the copies of Kr in the random graph G(n, p) are randomly distributed, in the (one-sided) sense that the hypergraph that they form contains a copy of a binomial random...
| Tác giả chính: | |
|---|---|
| Định dạng: | Journal article |
| Ngôn ngữ: | English |
| Được phát hành: |
Wiley
2022
|
| Tóm tắt: | <p>We show that for each r ≥ 4, in a density range extending up to, and slightly beyond, the threshold for a Kr-factor, the copies of Kr in the random graph G(n, p) are randomly distributed, in the (one-sided) sense that the hypergraph that they form contains a copy of a binomial random hypergraph with almost exactly the right density. Thus Jeff Kahn’s recent asymptotically sharp bound for the threshold in Shamir’s hypergraph matching problem implies a corresponding bound for the threshold for G(n, p) to contain a Kr-factor. The case r = 3 is more difficult, and has been settled by Annika Heckel. We also prove a corresponding result for K (t) r -factors in random t-uniform hypergraphs, as well as (in some cases weaker) generalizations replacing Kr by certain other (hyper)graphs.</p> |
|---|