کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654945 | 1632841 | 2006 | 14 صفحه PDF | دانلود رایگان |

Let fm(a,b,c,d)fm(a,b,c,d) denote the maximum size of a family FF of subsets of an mm-element set for which there is no pair of subsets A,B∈FA,B∈F with |A∩B|≥a,|Ā∩B|≥b,|A∩B̄|≥c,and|Ā∩B̄|≥d. By symmetry we can assume a≥da≥d and b≥cb≥c. We show that fm(a,b,c,d)fm(a,b,c,d) is Θ(ma+b−1)Θ(ma+b−1) if either b>cb>c or a,b≥1a,b≥1. We also show that fm(0,b,b,0)fm(0,b,b,0) is Θ(mb)Θ(mb) and fm(a,0,0,d)fm(a,0,0,d) is Θ(ma)Θ(ma). The asymptotic results are as m→∞m→∞ for fixed non-negative integers a,b,c,da,b,c,d. This can be viewed as a result concerning forbidden configurations and is further evidence for a conjecture of Anstee and Sali. Our key tool is a strong stability version of the Complete Intersection Theorem of Ahlswede and Khachatrian, which is of independent interest.
Journal: European Journal of Combinatorics - Volume 27, Issue 8, November 2006, Pages 1235–1248