{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T15:39:13Z","timestamp":1649173153799},"reference-count":7,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"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":[[2008,7]]},"abstract":"<jats:p>If <jats:italic>G<\/jats:italic> is a graph with vertex set [<jats:italic>n<\/jats:italic>] then <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548308009206_inline1\"><jats:alt-text>$\\mathcal{A}\\subseteq 2^{[n]}$<\/jats:alt-text><\/jats:inline-graphic> is <jats:italic>G-intersecting<\/jats:italic> if, for all <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548308009206_inline2\"><jats:alt-text>$A,B\\in \\mathcal{A}$<\/jats:alt-text><\/jats:inline-graphic>, either <jats:italic>A<\/jats:italic> \u2229 <jats:italic>B<\/jats:italic> \u2260 \u2205 or there exist <jats:italic>a<\/jats:italic> \u2208 <jats:italic>A<\/jats:italic> and <jats:italic>b<\/jats:italic> \u2208 <jats:italic>B<\/jats:italic> such that <jats:italic>a<\/jats:italic> ~<jats:sub><jats:italic>G<\/jats:italic><\/jats:sub><jats:italic>b<\/jats:italic>.<\/jats:p><jats:p>The question of how large a <jats:italic>k<\/jats:italic>-uniform <jats:italic>G<\/jats:italic>-intersecting family can be was first considered by Bohman, Frieze, Ruszink\u00f3 and Thoma [2], who identified two natural candidates for the extrema depending on the relative sizes of <jats:italic>k<\/jats:italic> and <jats:italic>n<\/jats:italic> and asked whether there is a sharp phase transition between the two. Our first result shows that there is a sharp transition and characterizes the extremal families when <jats:italic>G<\/jats:italic> is a matching. We also give an example demonstrating that other extremal families can occur.<\/jats:p><jats:p>Our second result gives a sufficient condition for the largest <jats:italic>G<\/jats:italic>-intersecting family to contain almost all <jats:italic>k<\/jats:italic>-sets. In particular we show that if <jats:italic>C<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is the <jats:italic>n<\/jats:italic>-cycle and <jats:italic>k<\/jats:italic> &gt; \u03b1<jats:italic>n<\/jats:italic> + <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>), where \u03b1 = 0.266.\u00a0.\u00a0. is the smallest positive root of (1 \u2212 <jats:italic>x<\/jats:italic>)<jats:sup>3<\/jats:sup>(1 + <jats:italic>x<\/jats:italic>) = 1\/2, then the largest <jats:italic>C<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>-intersecting family has size <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548308009206_inline3\"><jats:alt-text>$(1-o(1))\\binom{n}{k}$<\/jats:alt-text><\/jats:inline-graphic>.<\/jats:p><jats:p>Finally we consider the non-uniform problem, and show that in this case the size of the largest <jats:italic>G<\/jats:italic>-intersecting family depends on the matching number of <jats:italic>G<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548308009206","type":"journal-article","created":{"date-parts":[[2008,7,17]],"date-time":"2008-07-17T10:27:45Z","timestamp":1216290465000},"page":"559-575","source":"Crossref","is-referenced-by-count":0,"title":["<i>G<\/i>-Intersection Theorems for Matchings and Other Graphs"],"prefix":"10.1017","volume":"17","author":[{"given":"J. ROBERT","family":"JOHNSON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOHN","family":"TALBOT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"S0963548308009206_ref7","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548308009206_ref6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1093\/qmath\/12.1.313","article-title":"Intersection theorems for systems of finite sets","volume":"12","author":"Er\u0151os","year":"1961","journal-title":"Quart. J. Math. Oxford Ser. 2"},{"key":"S0963548308009206_ref4","volume-title":"Combinatorics","author":"Bollob\u00e1s","year":"1986"},{"key":"S0963548308009206_ref1","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"S0963548308009206_ref2","first-page":"376","article-title":"G-intersecting families","volume":"10","author":"Bohman","year":"2000","journal-title":"Combin. Probab. Comput."},{"key":"S0963548308009206_ref5","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF02579438","article-title":"Extremal hypergraph problems and convex hulls","volume":"5","author":"Er\u0151os","year":"1985","journal-title":"Combinatorica"},{"key":"S0963548308009206_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00761-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548308009206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T19:18:43Z","timestamp":1554491923000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548308009206\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["S0963548308009206"],"URL":"https:\/\/doi.org\/10.1017\/s0963548308009206","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]}}}