Abstract
A subfamily \(\{F_{1},F_{2},\dots ,F_{|P|}\}\subseteq \mathcal {F}\) of sets is a copy of a poset P in \(\mathcal {F}\) if there exists a bijection \(\phi :P\rightarrow \{F_{1},F_{2},\dots ,F_{|P|}\}\) such that whenever \(x \le _{P} x^{\prime }\) holds, then so does \(\phi (x)\subseteq \phi (x^{\prime })\). For a family \(\mathcal {F}\) of sets, let \(c(P,\mathcal {F})\) denote the number of copies of P in \(\mathcal {F}\), and we say that \(\mathcal {F}\) is P-free if \(c(P,\mathcal {F})=0\) holds. For any two posets P, Q let us denote by La(n, P, Q) the maximum number of copies of Q over all P-free families \(\mathcal {F} \subseteq 2^{[n]}\), i.e. \(\max \limits \{c(Q,\mathcal {F}): \mathcal {F} \subseteq 2^{[n]}, c(P,\mathcal {F})=0 \}\). This generalizes the well-studied parameter La(n, P) = La(n, P, P1) where P1 is the one element poset, i.e. La(n, P) is the largest possible size of a P-free family. The quantity La(n, P) has been determined (precisely or asymptotically) for many posets P, and in all known cases an asymptotically best construction can be obtained by taking as many middle levels as possible without creating a copy of P. In this paper we consider the first instances of the problem of determining La(n, P, Q). We find its value when P and Q are small posets, like chains, forks, the N poset and diamonds. Already these special cases show that the extremal families are completely different from those in the original P-free cases: sometimes not middle or consecutive levels maximize La(n, P, Q) 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 in k-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 of r-tuples \(A_{1},A_{2},\dots , A_{r} \in \mathcal {A}\) over all antichains \(\mathcal {A}\subseteq 2^{[n]}\) such that (i) \(\cap _{i=1}^{r}A_{i}=\emptyset \), (ii) \(\cap _{i=1}^{r}A_{i}=\emptyset \) and \(\cup _{i=1}^{r}A_{i}=[n]\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Shikhelman, N.: Many T-copies in H-free graphs. J. Combinatorial Theory, Ser. B 121, 146–172 (2016)
Bollobás, B.: Sperner systems consisting of pairs of complementary subsets. Journal of Combinatorial Theory, Series A 15, 363–366 (1973)
Bukh, B.: Set families with a forbidden subposet. Electronic Journal of Combinatorics 16(1), P142 (2009)
Burcsi, P., Nagy, D.: The method of double chains for largest families with excluded subposets. Electronic Journal of Graph Theory and Applications 1, 40–49 (2013)
DeBonis, A., Katona, G.O.H., Swanepoel, K.: Largest family without A ∪ B ⊂ C ∩ D. J. Combin. Theory Ser. A 111, 331–336 (2005)
Erdös, P. : On a lemma of Littlewood and Offord. Bull. Am. Math. Soc. 51, 898–902 (1945)
Engel, K.: Sperner Theory. Cambridge University Press (1997)
Erdös, P.L., Frankl, P., Katona, G.O.H.: Intersecting Sperner families and their convex hulls. Combinatorica 4, 21–34 (1984)
Erdös, P.L., Frankl, P., Katona, G.O.H.: Extremal hypergraph problems and convex hulls. Combinatorica 5, 11–26 (1985)
Erdös, P.L., Frankl, P., Katona, G.O.H.: Convex hulls of more-part Sperner families. Graphs and Combinatorics 2, 123–134 (1986)
Frankl, P., Katona, G.O.H.: Polytopes determined by hypergraph classes. European J. Combin. 6, 233–243 (1985)
Gerbner, D., Methuku, A., Nagy, D.T., Patkós, B., Vizer, M.: On the number of containments in P-free families. arXiv:1804.01606
Gerbner, D., Patkós, B.: L-chain profile vectors. SIAM J. Discrete Math. 22, 185–193 (2008)
Gerbner, D., Patkós, B.: Extremal Finite Set Theory. 1st Edition CRC Press (2018)
Griggs, J.R., Li, W.-T.: Progress on poset-free families of subsets. In: Recent Trends in Combinatorics, pp. 317–338 (2016)
Griggs, J.R., Lu, L.: On families of subsets with a forbidden subposet. J. Combinatorial Theory (Ser. A) 119, 310–322 (2012)
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
Katona, G.: A Theorem of Finite Sets. Theory of Graphs, Proc. Coll. Held at Tihany, Hungary (1966)
Katona, G.O.H.: Two application of Sperner type theorems (For search theory and truth functions). Period. Math. Hungar. 3, 19–26 (1973)
Katona, G.O.H.: Convex Hulls of Hypergraph Classes, Proc. of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983, pp 177–190. Univ. Novi Sad, Novi Sad (1984)
Katona, G.O.H., Tarján, T.: Extremal problems with excluded subgraphs in the n-cube, Graph Theory, Lagow Lecture Notes in Math. 1018, pp 84–93. Springer, Berlin (1983)
Kruskal, J.B.: The number of simplices in a complex. Math. Optimization Tech, pp. 251–278 (1963)
Methuku, A., Tompkins, C.: Exact forbidden subposet results using chain decompositions of the cycle. Electron. J. Combin. 22, 4.29 (2015)
Patkós, B.: The distance of \(\mathcal {F}\)-free families. Stud. Sci. Math. Hung. 46(2), 275–286 (2009)
Sperner, E.: Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27, 544–548 (1928)
Funding
Open access funding provided by MTA Alfréd Rényi Institute of Mathematics (MTA RAMKI).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Gerbner, D., Keszegh, B. & Patkós, B. Generalized Forbidden Subposet Problems. Order 37, 389–410 (2020). https://doi.org/10.1007/s11083-019-09511-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-019-09511-5