{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T16:58:15Z","timestamp":1771606695468,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ELKH Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,2]]},"abstract":"Abstract<\/jats:title>Let $$n \\ge 2k \\ge 4$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n k<\/mml:mi>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be integers, $${[n]\\atopwithdelims ()k}$$<\/jats:tex-math>\n \n \n \n [<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n k<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the collection of k<\/jats:italic>-subsets of $$[n] = \\{1, \\ldots , n\\}$$<\/jats:tex-math>\n \n [<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n =<\/mml:mo>\n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n n<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Two families $${\\mathcal {F}}, {\\mathcal {G}} \\subset {[n]\\atopwithdelims ()k}$$<\/jats:tex-math>\n \n F<\/mml:mi>\n ,<\/mml:mo>\n G<\/mml:mi>\n \u2282<\/mml:mo>\n \n \n \n [<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n k<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are said to be cross-intersecting<\/jats:italic> if $$F \\cap G \\ne \\emptyset $$<\/jats:tex-math>\n \n F<\/mml:mi>\n \u2229<\/mml:mo>\n G<\/mml:mi>\n \u2260<\/mml:mo>\n \u2205<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all $$F \\in {\\mathcal {F}}$$<\/jats:tex-math>\n \n F<\/mml:mi>\n \u2208<\/mml:mo>\n F<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$G \\in {\\mathcal {G}}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n \u2208<\/mml:mo>\n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. A family is called non-trivial if the intersection of all its members is empty. The best possible bound $$|{\\mathcal {F}}| + |{\\mathcal {G}}| \\le {n \\atopwithdelims ()k} - 2 {n - k\\atopwithdelims ()k} + {n - 2k \\atopwithdelims ()k} + 2$$<\/jats:tex-math>\n \n \n |<\/mml:mo>\n F<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n |<\/mml:mo>\n G<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n \n n<\/mml:mi>\n k<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n -<\/mml:mo>\n 2<\/mml:mn>\n \n \n \n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n k<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n +<\/mml:mo>\n \n \n \n n<\/mml:mi>\n -<\/mml:mo>\n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n k<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is established under the assumption that $${\\mathcal {F}}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $${\\mathcal {G}}$$<\/jats:tex-math>\n G<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are non-trivial and cross-intersecting. For the proof a strengthened version of the so-called shifting technique<\/jats:italic> is introduced. The most general result is Theorem 4.1.<\/jats:p>","DOI":"10.1007\/s00493-023-00060-5","type":"journal-article","created":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T11:02:43Z","timestamp":1698318163000},"page":"15-35","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Maximum of the Sum of the Sizes of Non-trivial Cross-Intersecting Families"],"prefix":"10.1007","volume":"44","author":[{"given":"P.","family":"Frankl","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,12]]},"reference":[{"key":"60_CR1","unstructured":"Alon, N.: Ph. D. Thesis, Hebrew University, Jerusalem (1983)"},{"key":"60_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1006\/jcta.1996.0092","volume":"76","author":"R Ahlswede","year":"1996","unstructured":"Ahlswede, R., Khachatrian, L.H.: The complete nontrivial-intersection theorem for systems of finite sets. J. Combin. Theory Ser. A 76, 121\u2013138 (1996)","journal-title":"J. Combin. Theory Ser. A"},{"key":"60_CR3","volume-title":"Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science","author":"L Babai","year":"1992","unstructured":"Babai, L., Frankl, P.: Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science. Dept. of Computer Science, University of Chicago, Chicago (1992)"},{"issue":"1","key":"60_CR4","doi-asserted-by":"publisher","first-page":"N9","DOI":"10.37236\/884","volume":"15","author":"P Borg","year":"2008","unstructured":"Borg, P.: Intersecting and cross-intersecting families of labeled sets. Electron. J. Combin. 15(1), N9 (2008)","journal-title":"Electron. J. Combin."},{"key":"60_CR5","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0097-3165(74)90013-2","volume":"17","author":"DE Daykin","year":"1972","unstructured":"Daykin, D.E.: Erd\u0151s-Ko-Rado from Kruskal-Katona. J. Combin. Theory Ser. A 17, 254\u2013255 (1972)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"12","key":"60_CR6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1093\/qmath\/12.1.313","volume":"2","author":"P Erd\u0151s","year":"1961","unstructured":"Erd\u0151s, P., Ko, C., Rado, R.: Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. 2(12), 313\u2013320 (1961)","journal-title":"Quart. J. Math. Oxford Ser."},{"key":"60_CR7","first-page":"365","volume":"18","author":"P Frankl","year":"1978","unstructured":"Frankl, P.: The Erd\u0151s-Ko-Rado Theorem is true for $$n = ckt$$. Coll. Math. Soc. J\u00e1nos Bolyai 18, 365\u2013375 (1978)","journal-title":"Coll. Math. Soc. J\u00e1nos Bolyai"},{"key":"60_CR8","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/0097-3165(78)90003-1","volume":"24","author":"P Frankl","year":"1978","unstructured":"Frankl, P.: On intersecting families of finite sets. J. Combin. Theory Ser. A 24, 146\u2013161 (1978)","journal-title":"J. Combin. Theory Ser. A"},{"key":"60_CR9","unstructured":"Frankl, P.: The shifting technique in extremal set theory. In: Surveys in Combinatorics 1987. LMS Lecture Note Series 123, Cambridge University Press, pp. 81\u2013110 (1987)"},{"key":"60_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.2140\/moscow.2019.8.97","volume":"8","author":"P Frankl","year":"2019","unstructured":"Frankl, P.: A proof of the Hilton-Milner Theorem without computation. Moscow J. Combin. Number Theory 8, 97\u2013101 (2019)","journal-title":"Moscow J. Combin. Number Theory"},{"issue":"1","key":"60_CR11","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0097-3165(86)90121-4","volume":"41","author":"P Frankl","year":"1986","unstructured":"Frankl, P., F\u00fcredi, Z.: Non-trivial intersecting families. J. Combin. Theory Ser. A 41(1), 150\u2013153 (1986)","journal-title":"J. Combin. Theory Ser. A"},{"key":"60_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/j.ejc.2017.01.004","volume":"62","author":"P Frankl","year":"2017","unstructured":"Frankl, P., Kupavskii, A.: A size-sensitive inequality for cross-intersecting families. Eur. J. Combin. 62, 263\u2013271 (2017)","journal-title":"Eur. J. Combin."},{"key":"60_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0097-3165(92)90054-X","volume":"61","author":"P Frankl","year":"1992","unstructured":"Frankl, P., Tokushige, N.: Some best possible inequalities concerning cross-intersecting families. J. Combin. Theory Ser. A 61, 87\u201397 (1992)","journal-title":"J. Combin. Theory Ser. A"},{"key":"60_CR14","doi-asserted-by":"crossref","unstructured":"Frankl, P., Wang, J.: A product version of the Hilton\u2013Milner Theorem. J. Combin. Theory Ser. A 200, November 2023, 105791","DOI":"10.1016\/j.jcta.2023.105791"},{"key":"60_CR15","unstructured":"Frankl, P., Wang, J.: Improved bounds on exact stability results of the Erd\u0151s\u2013Ko\u2013Rado theorem, to appear"},{"issue":"18","key":"60_CR16","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1093\/qmath\/18.1.369","volume":"2","author":"AJW Hilton","year":"1967","unstructured":"Hilton, A.J.W., Milner, E.C.: Some intersection theorems for systems of finite sets. Quart. J. Math. Oxford 2(18), 369\u2013384 (1967)","journal-title":"Quart. J. Math. Oxford"},{"issue":"6","key":"60_CR17","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1016\/j.disc.2018.03.010","volume":"341","author":"G Hurlbert","year":"2018","unstructured":"Hurlbert, G., Kamat, V.: New injective proofs of the Erd\u0151s-Ko-Rado and Hilton-Milner theorems. Discrete Math. 341(6), 1749\u20131754 (2018)","journal-title":"Discrete Math."},{"key":"60_CR18","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.jcta.2017.11.006","volume":"155","author":"A Kupavskii","year":"2018","unstructured":"Kupavskii, A., Zakharov, D.: Regular bipartite graphs and intersecting families. J. Combin. Theory Ser. A 155, 180\u2013189 (2018)","journal-title":"J. Combin. Theory Ser. A"},{"key":"60_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF02582941","volume":"1","author":"M M\u00f6rs","year":"1985","unstructured":"M\u00f6rs, M.: A generalization of a theorem of Kruskal. Graphs Combin. 1, 167\u2013183 (1985)","journal-title":"Graphs Combin."},{"key":"60_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0097-3165(86)90025-7","volume":"43","author":"L Pyber","year":"1986","unstructured":"Pyber, L.: A new generalization of the Erd\u0151s-Ko-Rado Theorem. J. Combin. Theory Ser. A 43, 85\u201390 (1986)","journal-title":"J. Combin. Theory Ser. A"},{"key":"60_CR21","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BF01171114","volume":"27","author":"E Sperner","year":"1928","unstructured":"Sperner, E.: Ein Satz \u00fcber Untermengen einer endlichen Menge. Math. Zeitschrift 27, 544\u2013548 (1928)","journal-title":"Math. Zeitschrift"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00060-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00060-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00060-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,24]],"date-time":"2024-02-24T23:04:11Z","timestamp":1708815851000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00060-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["60"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00060-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,12]]},"assertion":[{"value":"9 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}