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...
| Autor principal: | |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado em: |
Wiley
2022
|
| _version_ | 1826310399126929408 |
|---|---|
| author | Riordan, O |
| author_facet | Riordan, O |
| author_sort | Riordan, O |
| collection | OXFORD |
| description | <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> |
| first_indexed | 2024-03-07T07:51:46Z |
| format | Journal article |
| id | oxford-uuid:6a61505c-906a-4c44-85b4-8cd6e5d08da4 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:51:46Z |
| publishDate | 2022 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:6a61505c-906a-4c44-85b4-8cd6e5d08da42023-07-24T07:52:11ZRandom cliques in random graphs and sharp thresholds for F-factorsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6a61505c-906a-4c44-85b4-8cd6e5d08da4EnglishSymplectic ElementsWiley2022Riordan, O<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> |
| spellingShingle | Riordan, O Random cliques in random graphs and sharp thresholds for F-factors |
| title | Random cliques in random graphs and sharp thresholds for F-factors |
| title_full | Random cliques in random graphs and sharp thresholds for F-factors |
| title_fullStr | Random cliques in random graphs and sharp thresholds for F-factors |
| title_full_unstemmed | Random cliques in random graphs and sharp thresholds for F-factors |
| title_short | Random cliques in random graphs and sharp thresholds for F-factors |
| title_sort | random cliques in random graphs and sharp thresholds for f factors |
| work_keys_str_mv | AT riordano randomcliquesinrandomgraphsandsharpthresholdsforffactors |