Supersaturation and stability for forbidden subposet problems.

DOI10.1016/J.JCTA.2015.07.004zbMATH Open1322.06002arXiv1406.1887OpenAlexW1826102021MaRDI QIDQ490923FDOQ490923

Authors: Balázs Patkós 

Publication date: 21 August 2015

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We address a supersaturation problem in the context of forbidden subposets. A family $mathcalF$ of sets is said to contain the poset $P$ if there is an injection $i:PightarrowmathcalF$ such that $pl{e}_{P}q$ implies $i(p)subseti(q)$. The poset on four elements $a,b,c,d$ with $a,blec,d$ is called butterfly. The maximum size of a family $mathcalFsubseteq{2}^{[n]}$ that does not contain a butterfly is $$ as proved by De Bonis, Katona, and Swanepoel. We prove that if $mathcalFsubseteq{2}^{[n]}$ contains $Sigma(n,2)+E$ sets, then it has to contain at least $$ copies of the butterfly provided $Ele{2}^{n^{1-varepsilon}}$ for some positive $varepsilon$. We show by a construction that this is asymptotically tight and for small values of $E$ we show that the minimum number of butterflies contained in $mathcalF$ is exactly $$.

Full work available at URL: https://arxiv.org/abs/1406.1887

Recommendations

• Saturation for the butterfly poset
• Supersaturation, counting, and randomness in forbidden subposet problems
• Forbidden subposet problems for traces of set families
• On families of subsets with a forbidden subposet
• Exact forbidden subposet results using chain decompositions of the cycle

zbMATH Keywords

stabilityforbidden subposetsnumbers of butterfliessupersaturation

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Combinatorial inequalities (05A20) Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• Logarithmic order of free distributive lattice
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs with maximal number of adjacent pairs of edges
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On generalized graphs
• On a lemma of Littlewood and Offord
• The minimum number of disjoint pairs in set systems and related problems
• Supersaturated graphs and hypergraphs
• A short proof of Sperner's lemma
• Set families with a forbidden subposet
• Largest family without \(A \cup B \subseteq C \cap D\)
• Title not available (Why is that?)
• On families of subsets with a forbidden subposet
• Generalization of Sperner’s Theorem on the Number of Subsets of a Finite Set
• Diamond-free families
• On a problem of Kleitman and West
• Title not available (Why is that?)
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Title not available (Why is that?)
• On a theorem of Rademacher-Turán
• Simple hypergraphs with maximal number of adjacent pairs of edges
• On the minimum number of disjoint pairs in a family of finite sets
• Set systems with few disjoint pairs
• Set families with a forbidden induced subposet
• Supersaturation in the Boolean lattice
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

Cited In (7)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Exact forbidden subposet results using chain decompositions of the cycle
• Saturation for the butterfly poset
• Supersaturation in posets and applications involving the container method
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Supersaturation, counting, and randomness in forbidden subposet problems
• The saturation spectrum for antichains of subsets

This page was built for publication: Supersaturation and stability for forbidden subposet problems.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490923)