HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

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

Identifiers

Collections

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⟩

Share

Metrics

Record views

66

Files downloads

482