{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T16:50:30Z","timestamp":1781196630020,"version":"3.54.1"},"reference-count":10,"publisher":"Cambridge University Press (CUP)","issue":"1-2","license":[{"start":{"date-parts":[[2012,2,2]],"date-time":"2012-02-02T00:00:00Z","timestamp":1328140800000},"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":[[2012,3]]},"abstract":"<jats:p>A family<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char>of sets is said to be<jats:italic>intersecting<\/jats:italic>if<jats:italic>A<\/jats:italic>\u2229<jats:italic>B<\/jats:italic>\u2260 \u2205 for all<jats:italic>A<\/jats:italic>,<jats:italic>B<\/jats:italic>\u2208<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char>. It is a well-known and simple fact that an intersecting family of subsets of [<jats:italic>n<\/jats:italic>] = {1, 2, .\u00a0.\u00a0.,<jats:italic>n<\/jats:italic>} can contain at most 2<jats:sup><jats:italic>n<\/jats:italic>\u22121<\/jats:sup>sets. Katona, Katona and Katona ask the following question. Suppose instead<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char>\u2282<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char2\"\/><\/jats:private-char>[<jats:italic>n<\/jats:italic>] satisfies |<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char>| = 2<jats:sup><jats:italic>n<\/jats:italic>\u22121<\/jats:sup>+<jats:italic>i<\/jats:italic>for some fixed<jats:italic>i<\/jats:italic>&gt; 0. Create a new family<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char><jats:sub><jats:italic>p<\/jats:italic><\/jats:sub>by choosing each member of<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char>independently with some fixed probability<jats:italic>p<\/jats:italic>. How do we choose<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char>to maximize the probability that<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000472_char1\"\/><\/jats:private-char><jats:sub><jats:italic>p<\/jats:italic><\/jats:sub>is intersecting? They conjecture that there is a nested sequence of optimal families for<jats:italic>i<\/jats:italic>= 1, 2,.\u00a0.\u00a0., 2<jats:sup><jats:italic>n<\/jats:italic>\u22121<\/jats:sup>. In this paper, we show that the families [<jats:italic>n<\/jats:italic>]<jats:sup>(\u2265<jats:italic>r<\/jats:italic>)<\/jats:sup>= {<jats:italic>A<\/jats:italic>\u2282 [<jats:italic>n<\/jats:italic>]: |<jats:italic>A<\/jats:italic>| \u2265<jats:italic>r<\/jats:italic>} are optimal for the appropriate values of<jats:italic>i<\/jats:italic>, thereby proving the conjecture for this sequence of values. Moreover, we show that for intermediate values of<jats:italic>i<\/jats:italic>there exist optimal families lying between those we have found. It turns out that the optimal families we find simultaneously maximize the number of intersecting subfamilies of each possible order.<\/jats:p><jats:p>Standard compression techniques appear inadequate to solve the problem as they do not preserve intersection properties of subfamilies. Instead, our main tool is a novel compression method, together with a way of \u2018compressing subfamilies\u2019, which may be of independent interest.<\/jats:p>","DOI":"10.1017\/s0963548311000472","type":"journal-article","created":{"date-parts":[[2012,3,19]],"date-time":"2012-03-19T15:20:59Z","timestamp":1332170459000},"page":"301-313","source":"Crossref","is-referenced-by-count":7,"title":["Compressions and Probably Intersecting Families"],"prefix":"10.1017","volume":"21","author":[{"given":"PAUL A.","family":"RUSSELL","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2012,2,2]]},"reference":[{"key":"S0963548311000472_ref9","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1525\/9780520319875-014","volume-title":"Mathematical Optimization Techniques","author":"Kruskal","year":"1963"},{"key":"S0963548311000472_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(74)90012-0"},{"key":"S0963548311000472_ref10","unstructured":"[10] Leader I. B. (1999) personal communication."},{"key":"S0963548311000472_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(91)90021-8"},{"key":"S0963548311000472_ref4","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/12.1.313"},{"key":"S0963548311000472_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(81)90009-1"},{"key":"S0963548311000472_ref8","unstructured":"[8] Katona G. O. H. , Katona G. Y. and Katona Z. (2005) Probably intersecting families. Talk by G. O. H. Katona at the 12th International Conference on Random Structures and Algorithms, Pozna\u0144 2005."},{"key":"S0963548311000472_ref7","first-page":"187","volume-title":"Theory of Graphs: Proc. Colloq. Tihany 1966","author":"Katona","year":"1968"},{"key":"S0963548311000472_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01897141"},{"key":"S0963548311000472_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0008-4"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,5]],"date-time":"2022-01-05T01:24:38Z","timestamp":1641345878000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000472\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,2]]},"references-count":10,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["S0963548311000472"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000472","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,2]]}}}