[hal-01184383] Pairwise Intersections and Forbidden Configurations

Let f_m(a,b,c,d) denote the maximum size of a family \mathcalF of subsets of an m-element set for which there is no pair of subsets A,B∈\mathcalF with |A ∩ B|≥a, |<bar>A</bar> ∩ B|≥b, |A ∩ <bar>B</bar>| ≥c, and |<bar>A</bar> ∩ <bar>B</bar>|≥d.\par By symmetry we can assume a ≥d and b ≥c. We show that f_m(a,b,c,d) is Θ (m^a+b-1) if either b>c or a,b≥1. We also show that f_m(0,b,b,0) is Θ (m^b) and f_m(a,0,0,d) is Θ (m^a). 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.

from HAL : Dernières publications http://ift.tt/1DQQQNx