{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:43:16Z","timestamp":1740123796213,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"the J\u00e1nos Bolyai Research Fellowship of the Hungarian Academy of Sciences"},{"name":"National Research, Development and Innovation Office","award":["K 116769"],"award-info":[{"award-number":["K 116769"]}]},{"name":"National Research, Development and Innovation Office","award":["K 116769"],"award-info":[{"award-number":["K 116769"]}]},{"name":"National Research, Development and Innovation Office","award":["K 116769"],"award-info":[{"award-number":["K 116769"]}]},{"name":"National Research, Development and Innovation Office","award":["SNN 116095"],"award-info":[{"award-number":["SNN 116095"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2020,7]]},"abstract":"Abstract<\/jats:title>A subfamily$\\{F_{1},F_{2},\\dots ,F_{|P|}\\}\\subseteq \\mathcal {F}$<\/jats:tex-math>{<\/mml:mo>F<\/mml:mi><\/mml:mrow>1<\/mml:mn><\/mml:mrow><\/mml:msub>,<\/mml:mo>F<\/mml:mi><\/mml:mrow>2<\/mml:mn><\/mml:mrow><\/mml:msub>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo>F<\/mml:mi><\/mml:mrow>|<\/mml:mo>P<\/mml:mi>|<\/mml:mo><\/mml:mrow><\/mml:msub>}<\/mml:mo>\u2286<\/mml:mo>F<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>of sets is a copy of a posetP<\/jats:italic>in$\\mathcal {F}$<\/jats:tex-math>F<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>if there exists a bijection$\\phi :P\\rightarrow \\{F_{1},F_{2},\\dots ,F_{|P|}\\}$<\/jats:tex-math>\u03d5<\/mml:mi>:<\/mml:mo>P<\/mml:mi>\u2192<\/mml:mo>{<\/mml:mo>F<\/mml:mi><\/mml:mrow>1<\/mml:mn><\/mml:mrow><\/mml:msub>,<\/mml:mo>F<\/mml:mi><\/mml:mrow>2<\/mml:mn><\/mml:mrow><\/mml:msub>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo>F<\/mml:mi><\/mml:mrow>|<\/mml:mo>P<\/mml:mi>|<\/mml:mo><\/mml:mrow><\/mml:msub>}<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>such that whenever$x \\le _{P} x^{\\prime }$<\/jats:tex-math>x<\/mml:mi>\u2264<\/mml:mo><\/mml:mrow>P<\/mml:mi><\/mml:mrow><\/mml:msub>x<\/mml:mi><\/mml:mrow>\u2032<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>holds, then so does$\\phi (x)\\subseteq \\phi (x^{\\prime })$<\/jats:tex-math>\u03d5<\/mml:mi>(<\/mml:mo>x<\/mml:mi>)<\/mml:mo>\u2286<\/mml:mo>\u03d5<\/mml:mi>(<\/mml:mo>x<\/mml:mi><\/mml:mrow>\u2032<\/mml:mi><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For a family$\\mathcal {F}$<\/jats:tex-math>F<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>of sets, let$c(P,\\mathcal {F})$<\/jats:tex-math>c<\/mml:mi>(<\/mml:mo>P<\/mml:mi>,<\/mml:mo>F<\/mml:mi>)<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>denote the number of copies ofP<\/jats:italic>in$\\mathcal {F}$<\/jats:tex-math>F<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and we say that$\\mathcal {F}$<\/jats:tex-math>F<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>isP<\/jats:italic>-free if$c(P,\\mathcal {F})=0$<\/jats:tex-math>c<\/mml:mi>(<\/mml:mo>P<\/mml:mi>,<\/mml:mo>F<\/mml:mi>)<\/mml:mo>=<\/mml:mo>0<\/mml:mn><\/mml:math><\/jats:alternatives><\/jats:inline-formula>holds. For any two posetsP<\/jats:italic>,Q<\/jats:italic>let us denote byL<\/jats:italic>a<\/jats:italic>(n<\/jats:italic>,P<\/jats:italic>,Q<\/jats:italic>) the maximum number of copies ofQ<\/jats:italic>over allP<\/jats:italic>-free families$\\mathcal {F} \\subseteq 2^{[n]}$<\/jats:tex-math>F<\/mml:mi>\u2286<\/mml:mo>2<\/mml:mn><\/mml:mrow>[<\/mml:mo>n<\/mml:mi>]<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, i.e.$\\max \\limits \\{c(Q,\\mathcal {F}): \\mathcal {F} \\subseteq 2^{[n]}, c(P,\\mathcal {F})=0 \\}$<\/jats:tex-math>max<\/mml:mi>{<\/mml:mo>c<\/mml:mi>(<\/mml:mo>Q<\/mml:mi>,<\/mml:mo>F<\/mml:mi>)<\/mml:mo>:<\/mml:mo>F<\/mml:mi>\u2286<\/mml:mo>2<\/mml:mn><\/mml:mrow>[<\/mml:mo>n<\/mml:mi>]<\/mml:mo><\/mml:mrow><\/mml:msup>,<\/mml:mo>c<\/mml:mi>(<\/mml:mo>P<\/mml:mi>,<\/mml:mo>F<\/mml:mi>)<\/mml:mo>=<\/mml:mo>0<\/mml:mn>}<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This generalizes the well-studied parameterL<\/jats:italic>a<\/jats:italic>(n<\/jats:italic>,P<\/jats:italic>) =L<\/jats:italic>a<\/jats:italic>(n<\/jats:italic>,P<\/jats:italic>,P<\/jats:italic>1<\/jats:sub>) whereP<\/jats:italic>1<\/jats:sub>is the one element poset, i.e.L<\/jats:italic>a<\/jats:italic>(n<\/jats:italic>,P<\/jats:italic>) is the largest possible size of aP<\/jats:italic>-free family. The quantityL<\/jats:italic>a<\/jats:italic>(n<\/jats:italic>,P<\/jats:italic>) has been determined (precisely or asymptotically) for many posetsP<\/jats:italic>, and in all known cases an asymptotically best construction can be obtained by taking as many middle levels as possible without creating a copy ofP<\/jats:italic>. In this paper we consider the first instances of the problem of determiningL<\/jats:italic>a<\/jats:italic>(n<\/jats:italic>,P<\/jats:italic>,Q<\/jats:italic>). We find its value whenP<\/jats:italic>andQ<\/jats:italic>are small posets, like chains, forks, theN<\/jats:italic>poset and diamonds. Already these special cases show that the extremal families are completely different from those in the originalP<\/jats:italic>-free cases: sometimes not middle or consecutive levels maximizeL<\/jats:italic>a<\/jats:italic>(n<\/jats:italic>,P<\/jats:italic>,Q<\/jats:italic>) and sometimes the extremal family is not the union of levels. Finally, we determine (up to a polynomial factor) the maximum number of copies of complete multi-level posets ink<\/jats:italic>-Sperner families. The main tools for this are the profile polytope method and two extremal set system problems that are of independent interest: we maximize the number ofr<\/jats:italic>-tuples$A_{1},A_{2},\\dots , A_{r} \\in \\mathcal {A}$<\/jats:tex-math>A<\/mml:mi><\/mml:mrow>1<\/mml:mn><\/mml:mrow><\/mml:msub>,<\/mml:mo>A<\/mml:mi><\/mml:mrow>2<\/mml:mn><\/mml:mrow><\/mml:msub>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo>A<\/mml:mi><\/mml:mrow>r<\/mml:mi><\/mml:mrow><\/mml:msub>\u2208<\/mml:mo>A<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>over all antichains$\\mathcal {A}\\subseteq 2^{[n]}$<\/jats:tex-math>A<\/mml:mi>\u2286<\/mml:mo>2<\/mml:mn><\/mml:mrow>[<\/mml:mo>n<\/mml:mi>]<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>such that (i)$\\cap _{i=1}^{r}A_{i}=\\emptyset $<\/jats:tex-math>\u2229<\/mml:mo><\/mml:mrow>i<\/mml:mi>=<\/mml:mo>1<\/mml:mn><\/mml:mrow>r<\/mml:mi><\/mml:mrow><\/mml:msubsup>A<\/mml:mi><\/mml:mrow>i<\/mml:mi><\/mml:mrow><\/mml:msub>=<\/mml:mo>\u2205<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, (ii)$\\cap _{i=1}^{r}A_{i}=\\emptyset $<\/jats:tex-math>\u2229<\/mml:mo><\/mml:mrow>i<\/mml:mi>=<\/mml:mo>1<\/mml:mn><\/mml:mrow>r<\/mml:mi><\/mml:mrow><\/mml:msubsup>A<\/mml:mi><\/mml:mrow>i<\/mml:mi><\/mml:mrow><\/mml:msub>=<\/mml:mo>\u2205<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$\\cup _{i=1}^{r}A_{i}=[n]$<\/jats:tex-math>\u222a<\/mml:mo><\/mml:mrow>i<\/mml:mi>=<\/mml:mo>1<\/mml:mn><\/mml:mrow>r<\/mml:mi><\/mml:mrow><\/mml:msubsup>A<\/mml:mi><\/mml:mrow>i<\/mml:mi><\/mml:mrow><\/mml:msub>=<\/mml:mo>[<\/mml:mo>n<\/mml:mi>]<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s11083-019-09511-5","type":"journal-article","created":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T07:02:36Z","timestamp":1581318156000},"page":"389-410","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Generalized Forbidden Subposet Problems"],"prefix":"10.1007","volume":"37","author":[{"given":"D\u00e1niel","family":"Gerbner","sequence":"first","affiliation":[]},{"given":"Bal\u00e1zs","family":"Keszegh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1651-2487","authenticated-orcid":false,"given":"Bal\u00e1zs","family":"Patk\u00f3s","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,10]]},"reference":[{"key":"9511_CR1","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.jctb.2016.03.004","volume":"121","author":"N Alon","year":"2016","unstructured":"Alon, N., Shikhelman, N.: Many T-copies in H-free graphs. J. Combinatorial Theory, Ser. B 121, 146\u2013172 (2016)","journal-title":"J. Combinatorial Theory, Ser. B"},{"key":"9511_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0097-3165(73)90086-1","volume":"15","author":"B Bollob\u00e1s","year":"1973","unstructured":"Bollob\u00e1s, B.: Sperner systems consisting of pairs of complementary subsets. Journal of Combinatorial Theory, Series A 15, 363\u2013366 (1973)","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"1","key":"9511_CR3","doi-asserted-by":"publisher","first-page":"P142","DOI":"10.37236\/231","volume":"16","author":"B Bukh","year":"2009","unstructured":"Bukh, B.: Set families with a forbidden subposet. Electronic Journal of Combinatorics 16(1), P142 (2009)","journal-title":"Electronic Journal of Combinatorics"},{"key":"9511_CR4","doi-asserted-by":"publisher","first-page":"40","DOI":"10.5614\/ejgta.2013.1.1.4","volume":"1","author":"P Burcsi","year":"2013","unstructured":"Burcsi, P., Nagy, D.: The method of double chains for largest families with excluded subposets. Electronic Journal of Graph Theory and Applications 1, 40\u201349 (2013)","journal-title":"Electronic Journal of Graph Theory and Applications"},{"key":"9511_CR5","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.jcta.2005.01.002","volume":"111","author":"A DeBonis","year":"2005","unstructured":"DeBonis, A., Katona, G.O.H., Swanepoel, K.: Largest family without A \u222a B \u2282 C \u2229 D. J. Combin. Theory Ser. A 111, 331\u2013336 (2005)","journal-title":"J. Combin. Theory Ser. A"},{"key":"9511_CR6","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1090\/S0002-9904-1945-08454-7","volume":"51","author":"P Erd\u00f6s","year":"1945","unstructured":"Erd\u00f6s, P. : On a lemma of Littlewood and Offord. Bull. Am. Math. Soc. 51, 898\u2013902 (1945)","journal-title":"Bull. Am. Math. Soc."},{"key":"9511_CR7","doi-asserted-by":"crossref","unstructured":"Engel, K.: Sperner Theory. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574719"},{"key":"9511_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF02579153","volume":"4","author":"PL Erd\u00f6s","year":"1984","unstructured":"Erd\u00f6s, P.L., Frankl, P., Katona, G.O.H.: Intersecting Sperner families and their convex hulls. Combinatorica 4, 21\u201334 (1984)","journal-title":"Combinatorica"},{"key":"9511_CR9","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF02579438","volume":"5","author":"PL Erd\u00f6s","year":"1985","unstructured":"Erd\u00f6s, P.L., Frankl, P., Katona, G.O.H.: Extremal hypergraph problems and convex hulls. Combinatorica 5, 11\u201326 (1985)","journal-title":"Combinatorica"},{"key":"9511_CR10","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF01788086","volume":"2","author":"PL Erd\u00f6s","year":"1986","unstructured":"Erd\u00f6s, P.L., Frankl, P., Katona, G.O.H.: Convex hulls of more-part Sperner families. Graphs and Combinatorics 2, 123\u2013134 (1986)","journal-title":"Graphs and Combinatorics"},{"key":"9511_CR11","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0195-6698(85)80033-0","volume":"6","author":"P Frankl","year":"1985","unstructured":"Frankl, P., Katona, G.O.H.: Polytopes determined by hypergraph classes. European J. Combin. 6, 233\u2013243 (1985)","journal-title":"European J. Combin."},{"key":"9511_CR12","unstructured":"Gerbner, D., Methuku, A., Nagy, D.T., Patk\u00f3s, B., Vizer, M.: On the number of containments in P-free families. arXiv:1804.01606"},{"key":"9511_CR13","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1137\/060666366","volume":"22","author":"D Gerbner","year":"2008","unstructured":"Gerbner, D., Patk\u00f3s, B.: L-chain profile vectors. SIAM J. Discrete Math. 22, 185\u2013193 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9511_CR14","doi-asserted-by":"crossref","unstructured":"Gerbner, D., Patk\u00f3s, B.: Extremal Finite Set Theory. 1st Edition CRC Press (2018)","DOI":"10.1201\/9780429440809-1"},{"key":"9511_CR15","doi-asserted-by":"crossref","unstructured":"Griggs, J.R., Li, W.-T.: Progress on poset-free families of subsets. In: Recent Trends in Combinatorics, pp. 317\u2013338 (2016)","DOI":"10.1007\/978-3-319-24298-9_14"},{"key":"9511_CR16","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.jcta.2011.09.002","volume":"119","author":"JR Griggs","year":"2012","unstructured":"Griggs, J.R., Lu, L.: On families of subsets with a forbidden subposet. J. Combinatorial Theory (Ser. A) 119, 310\u2013322 (2012)","journal-title":"J. Combinatorial Theory (Ser. A)"},{"key":"9511_CR17","unstructured":"Guo, J.-Y., Chang, F.-H., Chen, H.-B., Li, W.-T.: Families of Subsets Without a Given Poset in the Interval Chains. arXiv:1605.00373"},{"key":"9511_CR18","volume-title":"A Theorem of Finite Sets","author":"G Katona","year":"1966","unstructured":"Katona, G.: A Theorem of Finite Sets. Theory of Graphs, Proc. Coll. Held at Tihany, Hungary (1966)"},{"key":"9511_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF02018457","volume":"3","author":"GOH Katona","year":"1973","unstructured":"Katona, G.O.H.: Two application of Sperner type theorems (For search theory and truth functions). Period. Math. Hungar. 3, 19\u201326 (1973)","journal-title":"Period. Math. Hungar."},{"key":"9511_CR20","first-page":"177","volume-title":"Convex Hulls of Hypergraph Classes, Proc. of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983","author":"GOH Katona","year":"1984","unstructured":"Katona, G.O.H.: Convex Hulls of Hypergraph Classes, Proc. of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983, pp 177\u2013190. Univ. Novi Sad, Novi Sad (1984)"},{"key":"9511_CR21","first-page":"84","volume-title":"Extremal problems with excluded subgraphs in the n-cube, Graph Theory, Lagow Lecture Notes in Math. 1018","author":"GOH Katona","year":"1983","unstructured":"Katona, G.O.H., Tarj\u00e1n, T.: Extremal problems with excluded subgraphs in the n-cube, Graph Theory, Lagow Lecture Notes in Math. 1018, pp 84\u201393. Springer, Berlin (1983)"},{"key":"9511_CR22","doi-asserted-by":"crossref","unstructured":"Kruskal, J.B.: The number of simplices in a complex. Math. Optimization Tech, pp. 251\u2013278 (1963)","DOI":"10.1525\/9780520319875-014"},{"key":"9511_CR23","doi-asserted-by":"publisher","first-page":"4.29","DOI":"10.37236\/4803","volume":"22","author":"A Methuku","year":"2015","unstructured":"Methuku, A., Tompkins, C.: Exact forbidden subposet results using chain decompositions of the cycle. Electron. J. Combin. 22, 4.29 (2015)","journal-title":"Electron. J. Combin."},{"issue":"2","key":"9511_CR24","first-page":"275","volume":"46","author":"B Patk\u00f3s","year":"2009","unstructured":"Patk\u00f3s, B.: The distance of $\\mathcal {F}$-free families. Stud. Sci. Math. Hung. 46(2), 275\u2013286 (2009)","journal-title":"Stud. Sci. Math. Hung."},{"key":"9511_CR25","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. Z. 27, 544\u2013548 (1928)","journal-title":"Math. Z."}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-019-09511-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11083-019-09511-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-019-09511-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T03:15:46Z","timestamp":1665803746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11083-019-09511-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,10]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["9511"],"URL":"https:\/\/doi.org\/10.1007\/s11083-019-09511-5","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"type":"print","value":"0167-8094"},{"type":"electronic","value":"1572-9273"}],"subject":[],"published":{"date-parts":[[2020,2,10]]},"assertion":[{"value":"5 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}