کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655143 | 1632936 | 2015 | 18 صفحه PDF | دانلود رایگان |
We address a supersaturation problem in the context of forbidden subposets. A family FF of sets is said to contain the poset P if there is an injection i:P→Fi:P→F such that p≤Pqp≤Pq implies i(p)⊂i(q)i(p)⊂i(q). The poset on four elements a,b,c,da,b,c,d with a,b≤c,da,b≤c,d is called a butterfly. The maximum size of a family F⊆2[n]F⊆2[n] that does not contain a butterfly is (n⌊n/2⌋)+(n⌊n/2⌋+1) as proved by De Bonis, Katona, and Swanepoel. We prove that if F⊆2[n]F⊆2[n] contains (n⌊n/2⌋)+(n⌊n/2⌋+1)+E sets, then it has to contain at least (1−o(1))E(⌈n/2⌉+1)(⌈n/2⌉2) copies of the butterfly provided E≤2o(n)E≤2o(n). We show that this is asymptotically tight and for small values of E we show that the minimum number of butterflies contained in FF is exactly E(⌈n/2⌉+1)(⌈n/2⌉2).
Journal: Journal of Combinatorial Theory, Series A - Volume 136, November 2015, Pages 220–237