Richard P. Anstee ; Peter Keevash

Pairwise Intersections and Forbidden Configurations
dmtcs:3426 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3426
Pairwise Intersections and Forbidden Configurations
Authors: Richard P. Anstee ^{1}; Peter Keevash ^{2}
NULL##NULL
Richard P. Anstee;Peter Keevash
1 Department of Mathematics [Vancouver]
2 Department of Applied & Computational Mathematics
Let $f_m(a,b,c,d)$ denote the maximum size of a family $\mathcal{F}$ of subsets of an $m$element set for which there is no pair of subsets $A,B \in \mathcal{F}$ with $A \cap B \geq a$, $\bar{A} \cap B \geq b$, $A \cap \bar{B} \geq c$, and $\bar{A} \cap \bar{B} \geq d$. By symmetry we can assume $a \geq d$ and $b \geq c$. We show that $f_m(a,b,c,d)$ is $\Theta (m^{a+b1})$ if either $b > c$ or $a,b \geq 1$. We also show that $f_m(0,b,b,0)$ is $\Theta (m^b)$ and $f_m(a,0,0,d)$ is $\Theta (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.