DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Pairwise Intersections and Forbidden Configurations

Richard P. Anstee, Peter Keevash


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

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional