{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T09:51:06Z","timestamp":1763977866494},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,12,1]],"date-time":"2014-12-01T00:00:00Z","timestamp":1417392000000},"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":[[2015,7]]},"abstract":"<jats:p>A central result in extremal set theory is the celebrated theorem of Sperner from 1928, which gives the size of the largest family of subsets of [<jats:italic>n<\/jats:italic>] not containing a 2-chain, <jats:italic>F<\/jats:italic><jats:sub>1<\/jats:sub> \u2282 <jats:italic>F<\/jats:italic><jats:sub>2<\/jats:sub>. Erd\u0151s extended this theorem to determine the largest family without a <jats:italic>k<\/jats:italic>-chain, <jats:italic>F<\/jats:italic><jats:sub>1<\/jats:sub> \u2282 <jats:italic>F<\/jats:italic><jats:sub>2<\/jats:sub> \u2282 .\u00a0.\u00a0. \u2282 <jats:italic>F<jats:sub>k<\/jats:sub><\/jats:italic>. Erd\u0151s and Katona, followed by Kleitman, asked how many chains must appear in families with sizes larger than the corresponding extremal bounds.<\/jats:p><jats:p>In 1966, Kleitman resolved this question for 2-chains, showing that the number of such chains is minimized by taking sets as close to the middle level as possible. Moreover, he conjectured the extremal families were the same for <jats:italic>k<\/jats:italic>-chains, for all <jats:italic>k<\/jats:italic>. In this paper, making the first progress on this problem, we verify Kleitman's conjecture for the families whose size is at most the size of the <jats:italic>k<\/jats:italic> + 1 middle levels. We also characterize all extremal configurations.<\/jats:p>","DOI":"10.1017\/s0963548314000273","type":"journal-article","created":{"date-parts":[[2014,12,1]],"date-time":"2014-12-01T06:39:02Z","timestamp":1417415942000},"page":"585-608","source":"Crossref","is-referenced-by-count":16,"title":["Sperner's Theorem and a Problem of Erd\u0151s, Katona and Kleitman"],"prefix":"10.1017","volume":"24","author":[{"given":"SHAGNIK","family":"DAS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WENYING","family":"GAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,12,1]]},"reference":[{"key":"S0963548314000273_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90140-X"},{"key":"S0963548314000273_ref11","first-page":"60","article-title":"Problem 28","volume":"10","author":"Mantel","year":"1907","journal-title":"Wiskundige Opgaven"},{"key":"S0963548314000273_ref6","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1215\/ijm\/1255631811","article-title":"On a theorem of Rademacher\u2013Tur\u00e1n","volume":"6","author":"Erd\u0151s","year":"1962","journal-title":"Illinois J. Math."},{"key":"S0963548314000273_ref9","first-page":"84","volume-title":"Lecture Notes in Mathematics","author":"Katona","year":"1983"},{"key":"S0963548314000273_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(88)90034-9"},{"key":"S0963548314000273_ref5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1945-08454-7"},{"key":"S0963548314000273_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574719"},{"key":"S0963548314000273_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01171114"},{"key":"S0963548314000273_ref10","unstructured":"Kleitman D. (1966) A conjecture of Erd\u0151s\u2013Katona on commensurable pairs among subsets of an n-set. In Theory of Graphs: Proc. Colloq. Tihany, pp. 215\u2013218."},{"key":"S0963548314000273_ref7","first-page":"459","article-title":"On the number of complete subgraphs contained in certain graphs","volume":"7","author":"Erd\u0151s","year":"1962","journal-title":"Magy. Tud. Acad. Mat. Kut. Int. K\u00f6zl."},{"key":"S0963548314000273_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.09.025"},{"key":"S0963548314000273_ref2","unstructured":"Das S. , Gan W. and Sudakov B. (2014) The minimum number of disjoint pairs in set systems and related problems. Combinatorica, to appear."},{"key":"S0963548314000273_ref3","first-page":"1","article-title":"Supersaturation in the Boolean lattice","volume":"14A","author":"Dove","year":"2014","journal-title":"Integers"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T18:52:02Z","timestamp":1555786322000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000273\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,1]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["S0963548314000273"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000273","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,1]]}}}