{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T15:52:02Z","timestamp":1769010722734,"version":"3.49.0"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2017,3,29]],"date-time":"2017-03-29T00:00:00Z","timestamp":1490745600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,5]]},"abstract":"<jats:p>We investigate the asymptotic version of the Erd\u0151s\u2013Ko\u2013Rado theorem for the random <jats:italic>k<\/jats:italic>-uniform hypergraph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>(<jats:italic>n, p<\/jats:italic>). For 2\u2a7d<jats:italic>k<\/jats:italic>(<jats:italic>n<\/jats:italic>) \u2a7d <jats:italic>n<\/jats:italic>\/2, let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_inline2\"\/><jats:tex-math>$N=\\binom{n}k$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_inline3\"\/><jats:tex-math>$D=\\binom{n-k}k$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We show that with probability tending to 1 as <jats:italic>n<\/jats:italic> \u2192 \u221e, the largest intersecting subhypergraph of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> has size\n<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_eqnU1\"\/><jats:tex-math>$$(1+o(1))p\\ffrac kn N$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>\nfor any\n<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_eqnU2\"\/><jats:tex-math>$$p\\gg \\ffrac nk\\ln^2\\biggl(\\ffrac nk\\biggr)D^{-1}.$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>\nThis lower bound on <jats:italic>p<\/jats:italic> is asymptotically best possible for <jats:italic>k<\/jats:italic> = \u0398(<jats:italic>n<\/jats:italic>). For this range of <jats:italic>k<\/jats:italic> and <jats:italic>p<\/jats:italic>, we are able to show stability as well.<\/jats:p><jats:p>A different behaviour occurs when <jats:italic>k<\/jats:italic> = <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>). In this case, the lower bound on <jats:italic>p<\/jats:italic> is almost optimal. Further, for the small interval <jats:italic>D<\/jats:italic><jats:sup>\u22121<\/jats:sup> \u226a <jats:italic>p<\/jats:italic> \u2a7d (<jats:italic>n<\/jats:italic>\/<jats:italic>k<\/jats:italic>)<jats:sup>1\u2212\u03f5<\/jats:sup><jats:italic>D<\/jats:italic><jats:sup>\u22121<\/jats:sup>, the largest intersecting subhypergraph of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>(<jats:italic>n<\/jats:italic>, <jats:italic>p<\/jats:italic>) has size \u0398(ln(<jats:italic>pD<\/jats:italic>)<jats:italic>ND<\/jats:italic><jats:sup>\u22121<\/jats:sup>), provided that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_inline4\"\/><jats:tex-math>$k \\gg \\sqrt{n \\ln n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><jats:p>Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000420_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>, for essentially all values of <jats:italic>p<\/jats:italic> and <jats:italic>k<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548316000420","type":"journal-article","created":{"date-parts":[[2017,3,29]],"date-time":"2017-03-29T02:48:55Z","timestamp":1490755735000},"page":"406-422","source":"Crossref","is-referenced-by-count":3,"title":["Erd\u0151s\u2013Ko\u2013Rado for Random Hypergraphs: Asymptotics and Stability"],"prefix":"10.1017","volume":"26","author":[{"given":"MARCELO M.","family":"GAUY","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HI\u00caP","family":"H\u00c0N","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"IGOR C.","family":"OLIVEIRA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,3,29]]},"reference":[{"key":"S0963548316000420_ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"S0963548316000420_ref6","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"S0963548316000420_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20477"},{"key":"S0963548316000420_ref7","article-title":"On the stability of the Erd\u0151s\u2013Ko\u2013Rado theorem","author":"Bollob\u00e1s","journal-title":"J. Combin. Theory Ser. A"},{"key":"S0963548316000420_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20496"},{"key":"S0963548316000420_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2318-9"},{"key":"S0963548316000420_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"S0963548316000420_ref16","unstructured":"Hoffman A. (1970) On eigenvalues and colorings of graphs. In Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin), pp. 79\u201391."},{"key":"S0963548316000420_ref14","unstructured":"Hamm A. and Kahn J. On Erd\u0151s\u2013Ko\u2013Rado for random hypergraphs I. Submitted."},{"key":"S0963548316000420_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"S0963548316000420_ref8","unstructured":"Conlon D. and Gowers W. Combinatorial theorems in sparse random sets. Submitted DOI 10.4007\/annals.2016.184.2.2."},{"key":"S0963548316000420_ref9","article-title":"Removal and stability for Erd\u0151s\u2013Ko\u2013Rado","author":"Das","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548316000420_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0478-3"},{"key":"S0963548316000420_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548316000420_ref24","unstructured":"Schacht M. Extremal results for random discrete structures. Submitted DOI 10.4007\/annals.2016.184.2.1."},{"key":"S0963548316000420_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90273-X"},{"key":"S0963548316000420_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/15M1012992"},{"key":"S0963548316000420_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90204-7"},{"key":"S0963548316000420_ref13","unstructured":"Friedgut E. and Regev O. Manuscript."},{"key":"S0963548316000420_ref4","article-title":"Transference for the Erd\u0151s\u2013Ko\u2013Rado theorem","author":"Balogh","journal-title":"Forum of Math. Sigma"},{"key":"S0963548316000420_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009804"},{"key":"S0963548316000420_ref11","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/12.1.313"},{"key":"S0963548316000420_ref15","unstructured":"Hamm A. and Kahn J. On Erd\u0151s\u2013Ko\u2013Rado for random hypergraphs II. Submitted."},{"key":"S0963548316000420_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990253"},{"key":"S0963548316000420_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2015.01.003"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548316000420","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T19:00:00Z","timestamp":1555527600000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548316000420\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,29]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["S0963548316000420"],"URL":"https:\/\/doi.org\/10.1017\/s0963548316000420","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,29]]}}}