The Library
Erdős–Ko–Rado for random hypergraphs : asymptotics and stability
Tools
Tools
Tools
Gauy, Marcelo M., Han, Hiep and Oliveira, Igor C. (2017) Erdős–Ko–Rado for random hypergraphs : asymptotics and stability. Combinatorics, Probability and Computing, 26 (3). pp. 406-422. doi:10.1017/S0963548316000420
|
PDF
WRAP-Erdős–Ko–Rado-random-hypergraphs-asymptotics-stability-Oliveira-2017.pdf - Accepted Version - Requires a PDF viewer. Download (762Kb) | Preview |
Official URL: http://dx.doi.org/10.1017/S0963548316000420
Abstract
We investigate the asymptotic version of the Erdo˝s-Ko-Rado theorem for the random kuniform hypergraph Hk(n,p). For 2 ≤ k(n) ≤ n/2, let N =(n k)and D =(n−k k). We show thatwith probability tending to 1 as n →∞, the largest intersecting subhypergraph of Hk(n,p) hassize (1 + o(1))pk nN, for any p ≫ n k ln2(n k)D−1. This lower bound on p is asymptotically bestpossible for k = Θ(n). For this range of k and p, we are able to show stability as well. A different behavior occurs when k = o(n). In this case, the lower bound on p is almost optimal. Further, for the small interval D−1 ≪ p ≤ (n/k)1−εD−1, the largest intersecting subhypergraph of Hk(n,p) has size Θ(ln(pD)ND−1), provided that k ≫√nlnn. Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in Hk(n,p), for essentially all values of p and k.
| Item Type: | Journal Article | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||||||||||||||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Hypergraphs, Graph theory, Asymptotic expansions, Combinatorial analysis | ||||||||||||||||||||||||||||||
| Journal or Publication Title: | Combinatorics, Probability and Computing | ||||||||||||||||||||||||||||||
| Publisher: | Cambridge University Press | ||||||||||||||||||||||||||||||
| ISSN: | 0963-5483 | ||||||||||||||||||||||||||||||
| Official Date: | May 2017 | ||||||||||||||||||||||||||||||
| Dates: |
|
||||||||||||||||||||||||||||||
| Volume: | 26 | ||||||||||||||||||||||||||||||
| Number: | 3 | ||||||||||||||||||||||||||||||
| Page Range: | pp. 406-422 | ||||||||||||||||||||||||||||||
| DOI: | 10.1017/S0963548316000420 | ||||||||||||||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||||||||||||||
| Publisher Statement: | This article has been published in a revised form in Combinatorics, Probability and Computing http://doi.org/10.1017/S0963548316000420. This version is free to view and download for private research and study only. Not for re-distribution, re-sale or use in derivative works. © Cambridge University Press 2017 | ||||||||||||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
