HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Pairwise Intersections and Forbidden Configurations

Abstract : 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+b-1})$ 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [7 references]

https://hal.inria.fr/hal-01184383
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:38:47 AM
Last modification on : Friday, December 18, 2020 - 5:30:03 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:04:39 AM

### File

dmAE0104.pdf
Publisher files allowed on an open archive

### Citation

Richard P. Anstee, Peter Keevash. Pairwise Intersections and Forbidden Configurations. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.17-20, ⟨10.46298/dmtcs.3426⟩. ⟨hal-01184383⟩

Record views